Fork me on GitHub

二叉搜索树

发表于 | 更新于 | 分类于

基本概念

二叉搜索树(BST)又叫二叉查找树，二叉排序树。二叉搜索树就是一棵二叉树，但是它又具有搜索树的特征：

  • 每个结点都比它的左结点大，比右结点小。
  • 每个结点的左右子树都是一课二叉搜索树。
  • 对一棵二叉搜索树进行中序遍历结果是从小到大排序的结果。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**结点数据结构*/
 static class BinaryNode<T>
	{
		T data;
		BinaryNode<T> left;
		BinaryNode<T> right;
		public BinaryNode(T data) {
			this(data,null,null);
		}
		public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
			this.data =data;
			this.left = left;
			this.right =right;
		}
		public BinaryNode()
		{
			data =null;
			this.left = left;
			this.right =right;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**查找指定的元素,默认从
    * 根结点出开始查询*/
   public boolean contains(T t)
   {
	  return contains(t, rootTree);
	   
   }
 /**从某个结点出开始查找元素*/
   public boolean contains(T t, BinaryNode<T> node)
   {
      if(node==null)
        return false;//结点为空，查找失败
      int result = t.compareTo(node.data);
       if(result>0)
          return contains(t,node.right);//递归查询右子树
      else if(result<0)
          return contains(t, node.left);//递归查询左子树  
      else
          return true;
   }
    /**
       这里我提供一个对二叉树最大值
       最小值的搜索*/
 
 
 /**找到二叉查找树中的最小值*/
   public T findMin()
   {
	  if(isEmpty())
	  {
		  System.out.println("二叉树为空");
		  return null;
	  }else
	   return findMin(rootTree).data;
	   
   }
   /**找到二叉查找树中的最大值*/
   public T findMax()
   {
	   if(isEmpty())
		  {
			  System.out.println("二叉树为空");
			  return null;
		  }else
		   return findMax(rootTree).data;
   }
 
/**查询出最小元素所在的结点*/
   public BinaryNode<T> findMin(BinaryNode<T> node)
   {
       if(node==null)
           return null;
       else if(node.left==null)
           return node;
       return findMin(node.left);//递归查找
   }
   /**查询出最大元素所在的结点*/
   public BinaryNode<T> findMax(BinaryNode<T> node)
   {
       if(node!=null)
       {
           while(node.right!=null)
               node=node.right;
       }
       return node;       
   }