常见数据结构之二叉树

作者: 老羊_肖恩 | 来源:发表于2017-11-14 14:41 被阅读220次

二叉树的定义

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。
满二叉树：一棵深度为k，且有2^k-1个节点称之为满二叉树；
完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
平衡二叉树：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树.jpg

二叉树的遍历

先序遍历。根节点->左子树->右子树。

中序遍历。左子树->根节点->右子树。

后序遍历。左子树->右子树->根节点。

层次遍历。根据层次遍历的顺序，每一层都是从左到右的遍历输出。

//先序遍历  
   public void theFirstTraversal(Node root) {  
        printNode(root);  
        if (root.getLeftNode() != null) {  //使用递归进行遍历左孩子  
            theFirstTraversal(root.getLeftNode());  
        }  
        if (root.getRightNode() != null) {  //递归遍历右孩子  
            theFirstTraversal(root.getRightNode());  
        }  
    }  
//中序遍历  
    public void theInOrderTraversal(Node root) { 
        if (root.getLeftNode() != null) {  
            theInOrderTraversal(root.getLeftNode());  
        }  
        printNode(root);  
        if (root.getRightNode() != null) {  
            theInOrderTraversal(root.getRightNode());  
        }  
    }
//后序遍历  
    public void thePostOrderTraversal(Node root) {  //后序遍历  
        if (root.getLeftNode() != null) {  
            thePostOrderTraversal(root.getLeftNode());  
        }  
        if(root.getRightNode() != null) {  
            thePostOrderTraversal(root.getRightNode());  
        }  
        printNode(root);  
    } 

//层次遍历
  public void levelIterator(BiTree root)  
  {  
      if(root == null)  
      {  
          return ;  
      }  
      LinkedList<BiTree> queue = new LinkedList<BiTree>();  
      BiTree current = null;  
      queue.offer(root);//将根节点入队  
      while(!queue.isEmpty())  
      {  
          current = queue.poll();//出队队头元素并访问  
          System.out.print(current.val +"-->");  
          if(current.left != null)//如果当前节点的左节点不为空入队  
          {  
              queue.offer(current.left);  
          }  
          if(current.right != null)//如果当前节点的右节点不为空，把右节点入队  
          {  
              queue.offer(current.right);  
          }  
      }  
        
  }

常见的二叉树

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉检索树。其定义如下：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

二叉排序树.gif

查找过程：

（1）若根结点的关键字值等于查找的关键字，成功。
（2）否则，若小于根结点的关键字值，递归查左子树。
（3）若大于根结点的关键字值，递归查右子树。
（4）若子树为空，查找不成功。

插入节点：

（1）首先执行查找算法，找出被插结点的父亲结点。
（2）判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
（3）若二叉树为空。则首先单独生成根结点。
注意：新插入的结点总是叶子结点。

删除节点：

在二叉排序树删去一个结点，分三种情况讨论：
1.若p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。
2.若p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点f的左子树（当p是左子树）或右子树（当p是右子树）即可，作此修改也不破坏二叉排序树的特性。
3.若p结点的左子树和右子树均不空。在删去p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：
其一是令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树，s为p左子树的最右下的结点，而p的右子树为s的右子树；
其二是令p的直接前驱（或直接后继）替代p，然后再从二叉排序树中删去它的直接前驱（或直接后继）－即让f的左子树(如果有的话)成为p左子树的最左下结点(如果有的话)，再让f成为p的左右结点的父结点。

private void deleteNode(BinarySortTree p){
    //TODOAuto-generatedmethodstub
    if(p!=null)
    {
        //如果结点有左子树
        /*1。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子
        作为r的父亲的右孩子。
        2。若p没有左子树，直接用p的右孩子取代它。
        */
        if(p.lChild!=null)
        {
            BinarySortTree r=p.lChild;
            BinarySortTree prev=p.lChild;
                while(r.rChild!=null)
               {
                    prev=r;
                    r=r.rChild;
                }
                p.data=r.data;
            //若r不是p的左子树,p的左子树不变，r的左子树作为r的父结点的右孩子结点
            if(prev!=r)
            {
                prev.rChild=r.lChild;
             }
            else
            {
             //若r是p的左子树，则p的左子树指向r的左子树
            p.lChild=r.lChild;
            }
        }
        else
        {
            p=p.rChild;
        }
    }
}

平衡二叉树

平衡二叉树（Self-balancing binary search tree），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
平衡二叉搜索树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

AVL树

AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。
AVL树特点：
1. 本身首先是一棵二叉搜索树。
2. 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
AVL树操作
1.旋转
AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。
假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a（即a是离插入点最近，且平衡因子绝对值超过1的祖先结点），则失去平衡后进行进行的规律可归纳为下列四种情况：
(1) 单向右旋平衡处理LL：由于在a的左子树根结点的左子树上插入结点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行一次右旋转操作；
(2) 单向左旋平衡处理RR：由于在a的右子树根结点的右子树上插入结点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行一次左旋转操作；
(3) 双向旋转（先左后右）平衡处理LR：由于在a的左子树根结点的右子树上插入结点，a的平衡因子由1增至2，致使以a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。
(4) 双向旋转（先右后左）平衡处理RL：由于在a的右子树根结点的左子树上插入结点，a的平衡因子由-1变为-2，致使以a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

2.插入
向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。　
在平衡的的二叉排序树Balanced BST上插入一个新的数据元素e的递归算法可描述如下：　
若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1；若e的关键字和BBST的根结点的关键字相等，则不进行；若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：BBST的根结点的平衡因子为-1（右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变； BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1； BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

删除
从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。

查找
在AVL树中查找同在一般BST完全一样的进行，所以耗费 O(log n) 时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查询而改变。（这是与伸展树查找相对立的，它会因为查找而变更树结构。）