二叉查找树

每个节点包含四个属性：

1.值域key

2.父节点p

3.左孩子left

4.右孩子right

性质：

对任一节点k，均有

（1）key[left(k)]<=key[k]

（2）key[right(k)]>=key[k]

如下图：

按顺序遍历二叉查找树：采用中序遍历

java实现案例：按给定值查询二叉查找树，以及查找二叉查找树中的最大元素（即最右边的节点）：

public class Main {
    public  static void main(String[] args) {
         Scanner cin=new Scanner(System.in);
         int []tree= {3,1,5,0,2,4,6};
         System.out.println("元素2在二叉查找树中的位置为"+treeSearch(tree,0,2));
         System.out.println("二叉查找树中的最大元素为"+treeMaxSearch(tree,0));
    }
    public static int left(int i) {
        return 2*i+1;
    }
    public static int right(int i) {
        return 2*(i+1);
    }
    public static int treeMaxSearch(int a[],int i) {
        if(left(i)>a.length-1&&right(i)>a.length-1)
            return a[i];
        else {
                return treeMaxSearch(a,right(i));
        }
    }
    public static int treeSearch(int a[],int i,int k) {
        if((left(i)>a.length-1&&right(i)>a.length-1)||a[i]==k)
            return i;
        else {
            if(a[i]>k)
                return treeSearch(a,left(i),k);
            else
                return treeSearch(a,right(i),k);
        }
    }
}

另一种查找方式：查找大于某个值的最小节点（TREE-SUCCESSOR)

在二叉查找树中插入一个节点

删除二叉查找树中的一个节点x：

分为三种情况：

1.该节点没有孩子，则：

y=p[x];

if(left[y]==x)

     left[y]=NULL;

else

     right[y]=NULL;

2.若该节点有一个孩子，则可以通过在其子节点和父节点之间建立一条链来删除该节点

3.若该节点既有左孩子又有右孩子，则首先需要利用TREE-SUCCESSOR()函数找到第一个比该节点的值大的节点y，然后删除x的后继z，用y替换x，然后将z作为y的孩子

过程如下：