数据结构之二叉树(一)

二叉树查找树

二叉查找树的性质是,对于树中的每个节点X,它的左子树中的所有项都小于右节点中的所有项.

二叉树节点的定义

// AnyType extends Comparable
private static class BinaryNode<AnyType> {
    AnyType element;
    BinaryNode left;
    BinartNode right;
    ...
}

二叉查找树架构

class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
   BinaryNode<AnyType> root;  // 根节点
   //  insert/remove/contains/findXXX... 等方法
}

contains方法

boolean contains(AnyType x, BinaryNode<AnyType> t) {
    if ( t == null ) renturn false;
    int cmp = t.compareTo( t.element );
    if ( cmp > 0 ) return contains( x, t.right );
    if ( cmp < 0 ) return contains( x, t.left );
    if ( cmp == 0 ) return ture;
}

findMin和findMax

min就是查找最左的节点,max就是查找最右的节点.

insert方法

基本思路与contains方法相同,查找出节点应该存在的地方,如果存在就什么事情也不做或者覆盖.

BinaryNode insert(AnyType x ,BinaryNode t) {
    if (t == null) 
       return new BinaryNode(x) ...// 把插入的元素作为新的root节点并返回

    int cmp = x compareTo t.element

    if cmp>0
        ...// 向右节点递归插入
    if cmp<0
        ...// 向左节点递归插入
    else
        ;// 重复元素
    return t;
}

remove方法

相对来说,删除元素的方法比较复杂一些,再删除一个节点的时候会有以下几种情况:

1. 是叶子节点

   因为没有子节点,那么可以直接删除.

2. 有一个子节点

   调整父节点的链接直接指向子节点,以绕过该节点.

3. 有两个子节点

   一种删除策略是用右子树中的最小节点的data替代该节点,并递归的删除那个最小节点(或者以同样的方法处理左子树中的最大节点).

   BinaryNode remove(AnyType x,BinaryNode t){
       if (t==null)
           // 没找到不做任何事
       int cmp = x companreTo t.element;
       if cmp>0
           ... //递归remove右子树
       if cmp<0
           ... //递归remove左子树
       
       if t.left notNull && t.reght notNull // 两个子节点
           t.data = findMin (t.right)  // 找到右子树中最小项,并返回该项的data
           t.right = remove(t.data,t.right) //从右子树中删除节点,并更新右子树的root
       else //一个子节点
           t = t.left != null ? t.left :t.right //将父节点直接指向改节点的唯一子节点
   
       return t
   
   }