庄周梦蝶

一 树、二叉树和二叉查找树

1。树的概念：

递归定义：

1） 一个空结构是一个空树

2）如果t1,...,tk是分离的树，那么以t1,...,tk的根为子节点的根结构也是树

3）只有按照1，2规则产生的结构才是树

树的概念更多用于分层结构，比如数据库管理系统的分层模型。

2。二叉树（binary tree）：所有节点都有两个子节点（可以为空），并且每个子节点都指明为左子节点还是右子节点

1）完全二叉数，满足第i层，有2的i-1次方个子节点此条件的二叉树

2）对于所有非空二叉树，如果它的中间子节点恰好有两个非空子女，那么叶的数目m大于中间节点的数目k，并且m=k+1

3。二叉查找树（binary search tree)

1）概念：对于树中的每个节点n，其左子节点中保存的所有数值都小于n保存的数值，右子节点保存的数值都大于n保存的数值。

2）二叉查找树可以实现更为优越的查找性能，主要实现方式有数组和链表结构，相比较而言，链表实现更为容易，因为数组实现删除和添加功能需要移动数组元素（如填补删除空位等）

二。二叉树的实现

首先设计一个节点（设计一个整型的二叉树，通用型通理）：

此类简单明了，一个信息值，两个引用（左右子树）。

public   class  IntBSTNode  {
  protected   int  key;

  protected  IntBSTNode left, right;

  public  IntBSTNode()  {
  left  =  right  =   null ;
 }

  public  IntBSTNode( int  el)  {
   this (el,  null ,  null );
 }

  public  IntBSTNode( int  el, IntBSTNode left, IntBSTNode right)  {
  key  =  el;
  left  =  left;
  right  =  right;
 }
}

由此类而实现一个完整二叉搜索树：

public   class  IntBST  {
  protected  IntBSTNode root;

  protected   void  visit(IntBSTNode p)  {
  System.out.print(p.key  +   "   " );
 }

  public  IntBST()  {
  root  =   null ;
 }

第一步，实现二叉树的搜索，查找过程简单明了，对每一个节点将要查找的键与当前节点的数值比较，如果键小于该数，就进入节点的左子树继续比较，反之进入右子树继续此比较过程。

public  IntBSTNode search( int  el)  {
   return  search(root, el);
 }

  protected  IntBSTNode search(IntBSTNode p,  int  el)  {
   while  (p  !=   null )
    if  (el  ==  p.key)
     return  p;
    else   if  (el  <  p.key)
    p  =  p.left;
    else
    p  =  p.right;
   return   null ;
 }

此查找过程最坏情况，树成为链表O(n)=(n-1)/2，最好情况：O(n)=lg(n+1)-2。经过计算可知，一般树的平均比较次数更接近于最好情况。

第二步，实现二叉树的遍历，树的遍历就是访问树的所有节点，且每个节点被访问一次。N个节点的树有N！种不同的遍历。我们只考虑两种情况的遍历

1）广度优先遍历，是从最底层（或最高层）开始逐层向上（或向下），而在同层自左向右（或者相反）访问每一个子节点，因此共有四种情况。考虑自顶向下，自左向右的情况，利用队列实现如下：

public   void  breadthFirst()  {
  IntBSTNode p  =  root;
  Queue queue  =   new  Queue();
   if  (p  !=   null )  {
   queue.enqueue(p);
    while  ( ! queue.isEmpty())  {
    p  =  (IntBSTNode) queue.dequeue();
    visit(p);
     if  (p.left  !=   null )
     queue.enqueue(p.left);
     if  (p.right  !=   null )
     queue.enqueue(p.right);
   }
  }
 }

2） 深度优先遍历，此种遍历关心3个任务：

V——访问一个节点

L——遍历左子树

R——遍历右子树

因此有3！=6种此类遍历，我们关心其中3种：

VLR——先序遍历树

LVR——中序遍历树

LRV——后序遍历树

如果用递归来实现这3种遍历非常容易理解，如下：

public   void  preorder()  {
  preorder(root);
 }

// 先序

protected   void  preorder(IntBSTNode p)  {
   if  (p  !=   null )  {
   visit(p);
   preorder(p.left);
   preorder(p.right);
  }
 }

  public   void  inorder()  {
  inorder(root);
 }

// 中序

protected   void  inorder(IntBSTNode p)  {
   if  (p  !=   null )  {
   inorder(p.left);
   visit(p);
   inorder(p.right);
  }
 }

  public   void  postorder()  {
  postorder(root);
 }

// 后序

protected   void  postorder(IntBSTNode p)  {
   if  (p  !=   null )  {
   postorder(p.left);
   postorder(p.right);
   visit(p);
  }
 }

同样，我们知道，递归调用总可以被迭代方式取代，只不过不是这么容易理解了，在此不再列出。

第三步。插入操作，此算法很简单，不详细讲解，简单来讲就是找到合适的位置连接即可

public void insert(int el) {
        IntBSTNode p = root, prev = null;
        while (p != null) { // find a place for inserting new node;
            prev = p;
            if (p.key < el)
                p = p.right;
            else
                p = p.left;
        }
        if (root == null) // tree is empty;
            root = new IntBSTNode(el);
        else if (prev.key < el)
            prev.right = new IntBSTNode(el);
        else
            prev.left = new IntBSTNode(el);
    }

   
第四步。节点的删除。
1）归并删除法，当被删除节点没有或者只有一个子树的时候很简单，当有两个子树存在的时候，情况稍微复杂。归并删除法就是将节点的两棵子树合并成一棵树，然后连接到节点的父节点上。归并子树的原则，寻找左子树中key最大的节点，并将其作为右子树的父节点。相反，也可以寻找右子树的key最小的节点，作为左子树的父节点。我们以第一种情况为例：

public void deleteByMerging(int el) {
        IntBSTNode tmp, node, p = root, prev = null;
        while (p != null && p.key != el) { // find the node p
            prev = p; // with element el;
            if (p.key < el)
                p = p.right;
            else
                p = p.left;
        }
        node = p;
        if (p != null && p.key == el) {
            if (node.right == null) // node has no right child: its left
                node = node.left; // child (if any) is attached to its parent;
            else if (node.left == null) // node has no left child: its right
                node = node.right; // child is attached to its parent;
            else { // be ready for merging subtrees;
                tmp = node.left; // 1. move left
                while (tmp.right != null)
                    // 2. and then right as far as
                    tmp = tmp.right; // possible;
                tmp.right = // 3. establish the link between the
                node.right; // the rightmost node of the left
                // subtree and the right subtree;
                node = node.left; // 4.
            }
            if (p == root)
                root = node;
            else if (prev.left == p)
                prev.left = node;
            else
                prev.right = node;
        } else if (root != null)
            System.out.println("key " + el + " is not in the tree");
        else
            System.out.println("the tree is empty");
    }

2）复制删除法：归并删除法带来的问题是可能改变树的高度。另一种删除法也就是复制删除法，将待删除节点的key用它的前驱节点的key来代替，某一节点的前驱节点就是该节点左子树中key最大的节点。如下实现：
   

 public void deleteByCopying(int el) {
        IntBSTNode node, p = root, prev = null;
        while (p != null && p.key != el) { // find the node p
            prev = p; // with element el;
            if (p.key < el)
                p = p.right;
            else
                p = p.left;
        }
        node = p;
        if (p != null && p.key == el) {
            if (node.right == null) // node has no right child;
                node = node.left;
            else if (node.left == null) // no left child for node;
                node = node.right;
            else {
                IntBSTNode tmp = node.left; // node has both children;
                IntBSTNode previous = node; // 1.
                while (tmp.right != null) { // 2. find the rightmost
                    previous = tmp; // position in the
                    tmp = tmp.right; // left subtree of node;
                }
                node.key = tmp.key; // 3. overwrite the reference
                if (previous == node) // of the key being deleted;
                    previous.left = tmp.left; // 4.
                else
                    previous.right = tmp.left; // 5.
            }
            if (p == root)
                root = node;
            else if (prev.left == p)
                prev.left = node;
            else
                prev.right = node;
        } else if (root != null)
            System.out.println("key " + el + " is not in the tree");
        else
            System.out.println("the tree is empty");
    }

4。树的平衡：如果树中任何节点的两个子树的高度差或者是0或者为1，那么这样的二叉树就是高度平衡的。如何平衡一棵树？
1）简单算法：将树中的所有数据中序遍历，放进一个数组，此数组已经排序，然后折半插入

 public void balance(int data[], int first, int last) {
        if (first <= last) {
            int middle = (first + last) / 2;
            System.out.print(data[middle] + " ");
            insert(data[middle]);
            balance(data, first, middle - 1);
            balance(data, middle + 1, last);
        }
    }

   
2）DSW算法：
基本原理是通过树的右旋转得到树的主干，然后再进行左旋转得到平衡树