数据结构笔记--二叉查找树概述以及java代码实现

简介: 一些概念:   二叉查找树的重要性质:对于树中的每一个节点X,它的左子树任一节点的值均小于X,右子树上任意节点的值均大于X.   二叉查找树是java的TreeSet和TreeMap类实现的基础.   由于树的递归定义,二叉查找树的代码实现也基本上都是使用递归的函数,二叉查找树的平均深度是O(logN).

一些概念:

  二叉查找树的重要性质:对于树中的每一个节点X,它的左子树任一节点的值均小于X,右子树上任意节点的值均大于X.

  二叉查找树是java的TreeSet和TreeMap类实现的基础.

  由于树的递归定义,二叉查找树的代码实现也基本上都是使用递归的函数,二叉查找树的平均深度是O(logN).

  因为二叉查找树要求所有的节点都可以进行排序.所以编写时代码时需要一个Comparable泛型接口,当需要对类中的对象进行排序的时候,就需要实现这个泛型接口,里边定义了一个public int compareTo(Object o)方法,接受一个Object作为参数,java中String,Integer等类都实现了这个接口.

java代码实现:

  remove方法:在查找树的代码实现中,最难得是删除,因为这涉及到三种情况:

    被删除节点是树叶节点(没有子树):最简单,直接删除,将该节点置为null即可

    被删除节点有一个子节点(左子树或右子树):是该节点的父节点指向该节点的子节点(左或右).见图1

    被删除节点有两个子节点:用其右子树中的最小值代替该节点上的值,删除其右子树上的最小值.见图2.

  

  1 package com.wang.tree;
  2 
  3 public class BinarySearchTree<T extends Comparable<T>>{
  4 
  5     
  6     private static class Node<T>{
  7         private T data;
  8         private Node<T> left;
  9         private Node<T> right;
 10         
 11         public Node(T data){
 12             this(data,null,null);
 13         }
 14         public Node(T data, Node<T> left, Node<T> right) {
 15             this.data = data;
 16             this.left = left;
 17             this.right = right;
 18         }
 19     }
 20     
 21     //私有变量 根节点root
 22     private Node<T> root;
 23     
 24     //无参构造函数,根节点为null
 25     public BinarySearchTree(){
 26         root=null;
 27     }
 28     
 29     //清空二叉查找树
 30     public void makeEmpty(){
 31         root=null;
 32     }
 33     //判断树是否为空
 34     public boolean isEmpty(){
 35         
 36         return root==null;
 37     }
 38     //查找集合中是否有元素value,有返回true
 39     public boolean contains(T value){
 40         
 41         return contains(value,root);
 42     }
 43     
 44     private boolean contains(T value, Node<T> t) {
 45         
 46         if(t==null){
 47             return false;
 48         }
 49         int result=value.compareTo(t.data);
 50         if(result<0){
 51             return contains(value,t.left);
 52         }else if(result>0){
 53             return contains(value,t.right);
 54         }else{
 55             return true;
 56         }
 57     }
 58 
 59     //查找集合中的最小值
 60     public T findMin(){
 61         
 62         return  findMin(root).data;
 63     }
 64     private Node<T> findMin(Node<T> t) {
 65         if(t==null){
 66             return null;
 67         }else if(t.left==null){
 68             return t;
 69         }
 70         
 71         
 72         return findMin(t.left);
 73     }
 74 
 75     //查找集合中的最大值
 76     public T findMax(){
 77         
 78         return findMax(root).data;
 79     }
 80     
 81     private Node<T> findMax(Node<T> t) {
 82         if(t!=null){
 83             while(t.right!=null){
 84                 t=t.right;
 85             }
 86         }
 87         
 88         return t;
 89     }
 90 
 91     //插入元素
 92     public void insert(T value){
 93         
 94         root =insert(value,root);
 95     }
 96 
 97     private Node<T> insert(T value, Node<T> t) {
 98         if(t==null){
 99             return new Node(value,null,null);
100         }
101         int result=value.compareTo(t.data);
102         if(result<0){
103             t.left=insert(value,t.left);
104         }else if(result>0){
105             t.right=insert(value,t.right);
106         }
107         return t;
108     }
109     //移除元素
110     public void remove(T value){
111         root=remove(value,root);
112         
113         
114     }
115 
116     private Node<T> remove(T value, Node<T> t) {
117         if(t==null){
118             return t;
119         }
120         
121         int result=value.compareTo(t.data);
122         if(result<0){
123             t.left=remove(value,t.left);
124         }else if(result>0){
125             t.right=remove(value,t.right);
126         }else if(t.left!=null&&t.right!=null){//如果被删除节点有两个儿子
127             //1.当前节点值被其右子树的最小值代替
128             t.data=findMin(t.right).data;
129             //将右子树的最小值删除
130             t.right=remove(t.data, t.right);
131         }else{
132             //如果被删除节点是一个叶子 或只有一个儿子
133             t=(t.left!=null)?t.left:t.right;
134         }
135         
136         return t;
137     }
138     
139     //中序遍历打印
140     public void printTree(){
141         printTree(root);
142     }
143 
144     private void printTree(Node<T> t) {
145         
146         if(t!=null){
147             printTree(t.left);
148             System.out.println(t.data);
149             printTree(t.right);
150         }
151     }
152 }

  测试代码:

package com.wang.tree;

public class TestBST {

    public static void main(String[] args) {
        
        BinarySearchTree<Integer> bst=new BinarySearchTree<>();
        bst.insert(5);
        bst.insert(7);
        bst.insert(3);
        bst.insert(1);
        bst.insert(9);
        bst.insert(6);
        bst.insert(4);
        System.out.println("最小值:"+bst.findMin());
        System.out.println("最大值:"+bst.findMax());
        System.out.println("查找元素9是否存在:"+bst.contains(9));
        System.out.println("查找元素8是否存在:"+bst.contains(8));
        System.out.println("遍历二叉树");
        bst.printTree();
    }
}

打印结果:

最小值:1
最大值:9
查找元素9是否存在:true
查找元素8是否存在:false
遍历二叉树
1
3
4
5
6
7
9

 

相关文章
|
9天前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
9天前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
1天前
|
Java 数据处理 开发者
Java中的Lambda表达式:简化你的代码之路
【8月更文挑战第66天】Lambda表达式在Java 8中首次引入,它为Java开发者提供了一种更简洁、更灵活的编程方式。本文将通过简单易懂的语言和实际代码示例,引导你理解Lambda表达式的基本概念、语法结构以及如何在Java项目中应用它来简化代码。无论你是Java新手还是有经验的开发者,这篇文章都将帮助你更好地掌握这一强大的工具。
28 11
|
4天前
|
存储 安全 Java
Java 数据结构类型总结
在 Java 中,常用的数据结构包括基础数据结构(如数组和字符串)、集合框架(如 Set、List 和 Map 接口的多种实现)、特殊数据结构(如栈、队列和双端队列)、链表(单链表、双链表和循环链表)以及图和树等。这些数据结构各有特点和适用场景,选择时需考虑性能、内存和操作需求。集合框架提供了丰富的接口和类,便于处理对象集合。
|
7天前
|
Java
java小工具util系列4:基础工具代码(Msg、PageResult、Response、常量、枚举)
java小工具util系列4:基础工具代码(Msg、PageResult、Response、常量、枚举)
21 5
|
5天前
|
Java 开发者
探索Java中的Lambda表达式:简化你的代码之旅##
【8月更文挑战第62天】 Java 8的发布为开发者带来了诸多新特性,其中最引人注目的无疑是Lambda表达式。这一特性不仅让代码变得更加简洁,还极大地提升了开发的效率。本文将通过实际示例,展示如何利用Lambda表达式来优化我们的代码结构,同时探讨其背后的工作原理和性能考量。 ##
|
8天前
|
Java API 开发者
探索Java中的Lambda表达式:简化代码,提升效率
【9月更文挑战第27天】在Java 8中引入的Lambda表达式为编程带来了革命性的变化。通过简洁的语法和强大的功能,它不仅简化了代码编写过程,还显著提升了程序的执行效率。本文将深入探讨Lambda表达式的本质、用法和优势,并结合实例演示其在实际开发中的应用。无论你是Java新手还是资深开发者,都能从中获得启发,优化你的代码设计。
|
9天前
|
存储 Java 索引
使用java代码实现左右括号查找
使用java代码实现左右括号查找
|
6天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
下一篇
无影云桌面