二叉树知识点总结

- 日理万妓 2022-07-11 15:57 286阅读 0赞

二叉树是一种比较重要的数据结构，这里对一些常见的二叉树的基础知识做一个总结，具体的代码实现放到下一篇博文

首选对二叉树进行一个分类，二叉树分为以下的几种:

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
    (2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
    (3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

对于二叉树来说，有遍历的方式有下面的几种:

1.深度遍历

1.1前序遍历

根节点->左子树->右子树

1.2中序遍历

左子树>根节点->右子树

1.3后序遍历

左子树->右子树->根节点

2.广度遍历

2.1按照二叉树的层次进行遍历

EX:前、中、后序遍历下面的二叉树:

![Center][]

前序遍历:

A  B D e g h C f

中序遍历:

D B g e h A C f

后序遍历:

D g h e B f  C A

层次遍历:

A   B C D e f g h

然后是各种遍历方式实现的伪代码，

前序遍历:

void preorder_traverse(const struct bi_tree *tree) 
    {
        if (tree) {
            /* 访问根节点*/
            access(tree->data);
    
            if (tree->left) {
                /* 访问左节点 */
                preorder_traverse(tree->left);
            }
    
            if (tree->right) {
                /* 访问右节点 */
                preorder_traverse(tree->right);
            }
        }
    }

中序遍历:

void midorder_traverse(const struct bi_tree *tree)
    {
        if (tree->left) {
            midorder_traverse(tree->left);
        }
        access(tree->data);
        if (tree->right) {
            midorder_traverse(tree->right);
        }
    }

后序遍历:

void lastorder_traverse(const struct bi_tree *tree)
    {
        if (tree->left) {
            lastorder_traverse(tree->left);
        }
        if (tree->right) {
            lastorder_traverse(tree->right);
        }
        access(tree->data);
    }

斯国一 ![得意][proud.gif]，当然还有非递归实现的方式，这里就不再赘述了。

AVL平衡二叉搜索树  
定义：平衡二叉树或为空树,或为如下性质的二叉排序树:  
  （1）左右子树深度之差的绝对值不超过1;  
  （2）左右子树仍然为平衡二叉树.  
平衡因子BF=左子树深度－右子树深度.  
平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。  
如图所示为平衡树和非平衡树示意图：

![Center 1][]  
  
下面整理一下二叉查找树（BST树）以及他的变形——红黑树（RBT树）的相关知识

首选给出BST树的定义:

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；BST树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；

否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变BST树结（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

对BST树进行 中序遍历就可以得到升序排列的数组。

1.对BST树进行遍历的伪代码如下:

INORDER-TREE-WALK(x)
    if x!=NIL
    then INORDER-TREE-WALK（left[x]）
    print key[x]
    INORDER-TREE-WALK（right[x]）

查询二叉查找树(就是查询二叉查找树中的某一个关键字,比方说这里要查找的就是关键字k,如果关键字不存在，那么直接返回NIL)

TREE-SEARCH(x,k)
    if x=NIL or k=key[x]
     then return x
    if k<key[x]
     then return TREE-SEARCH(left[x],k)//小于去左子树找
    else return TREE-SEARCH(right[x],k)//大于去右子树找

查找二叉树中的最小关键字以及最大关键字

查找最大关键字:

TREE-MAXIMUM(x)
    while left[x]!=NIL
          do x<-left[x]
    return x

查找最小关键字:

TREE-MINIMUM(x)
    while left[x]!=NIL
             do x<-left[x]
    return x

查找后继节点:

TREE-SUCCESSOR(x)
    if right[x]!=NIL
    then return TREE-MINIMUM(right[x])//右子树非空,那么后继就是右子树的左节点
    y<-p[x]//最低祖先节点
    while y!=NIL and x=right[y]//y节点不为空并且x在y节点的右子树上
        do x<-y
        y<-p[y]//继续查找上一级的父节点
    return y

插入操作:

TREE-INSERT(T,z)
    y<-NIL
    x<-root[T]//x指针从根节点开始
    while x!=NIL
        do y<-x//y指向x的父节点
        if key[z]<key[x]
            then x<-left[x]
    	else x<-right[x]
    p[z]<-y//x 是插入z的位置，这里先找到z的父节点
    if y=NIL//如果z插入到根节点
    then root[T]<-z
    else if key[z]<key[y]//小于父节点
    then left[y]<-z//插入到左子树
    else right[y]<-z//插入到右子树

删除操作:如果z没有子女，修改父节点p\[z\],使得NIL为其子女；如果节点z只有一个子女，则可以在子节点和父节点连起来删除z。最后，如果节点z有两个子女，先删除z的后继y，再用y的内容来替代z的内容。

TREE-DELETE(T,z)
    if left[z]=NIL or right[z]=NIL
    then y<-z
    else y<-TREE-SUCCESSOR(z)
    if left[y]!=NIL
    then x<-left[y]
    else x<- right[y]
    if x!=NIL
    then p[x]<-p[y]
    if p[y]=NIL
    then root[T]<-x
    else if y=left[p[y]]
    then left[p[y]]<-x

对于前面的几种操作，时间复杂度都是O(h)，h为树高。

下面对红黑树的内容做一个总结，他能够保证在最坏情况下面，基本的动态集合操作时间为O(lgn)

红黑树:

红黑树是一种二叉查找树，它是一种平衡的查找树，他能够保证在最坏的情况下动态的集合操作时间为O(lgn)

红黑树每个节点包含五个域：color，key，left，right，parent

红黑树满足下面的几个条件:

1）每个结点要么是红的，要么是黑的。  
2）根结点是黑的。  
3）每个叶结点，即空结点（NIL）是黑的。  
4）如果一个结点是红的，那么它的俩个儿子都是黑的。

5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

一颗有n个内节点的红黑树的高度至多为2lg(n+1)

ex:

对红黑树进行操作的时候，难免会破坏掉原有的结构，这是需要对二叉树进行一些变换，比方说下面讲到的二叉树的旋转操作。

下面是树的左旋和右旋的示意图:

左旋:

![Center 2][]

右旋:

![Center 3][]

然后左右旋的伪代码:

左旋:

LEFT-ROTATE(T,x)
    y<-right[x]  //设置y相对于x节点的位置
    right[x]<-left[y]//将y的左子树连接到x节点的右子树位置上
    p[left[y]]<-x
    p[y]<-p[x]//将x的父节点连接到y节点上边
    if p[x]=nil[t]//如果x节点直接是父节点
    then root[t]<-y
    else if x=left[p[x]]//x节点在其父节点的左子树上
     then left[p[x]]<-y//那么就将y添加到父节点的左子树上边
     else right[p[x]]<-y
    left[y]<-x//将x节点添加到y节点的左子树上
    p[x]<-y

右旋:

RIGHT-ROTATE(T,y)
    x<-left[y]
    left[y]<-right[x]
    p[right[x]]<-y
    p[y]<-p[x]
    if p[y]=nil[t]
    then root[t]<-x
    else if y=left[p[y]]
    then left[p[y]]<-x
    else right[p[y]]<-x
    right[x]<-y
    p[y]<-x

对于树的旋转，能保持不变的只有原树的搜索性质，而原树的红黑性质则不能保持，在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。

下面再来整理一下对红黑树进行插入操作的步骤：

RB-INSERT(T,z)
    y<-nil[T]
    x<-root[T]
    while x!=nil[T]
    do y<-x
    if key[z]<key[x]
    then x<-left[x]
    else x<-right[x]
    p[z]<-y
    if y=nil[T]
       then root[T]<-z
       else if key[z]<key[y]
       then left[y]<-z
       else  right[y]<-z
    left[z]<-nil[T]
    right[z]<-nil[T]
    color[z]<-RED
    RB-INSERT-FIXUP(T,z)
    RB-INSERT-FIXUP(T,z)
    while color[p[z]]=RED
    do if p[z]=left[p[p[z]]]
           then y<-right[p[p[z]]]
              if color[y]=RED
              then color[p[z]]<-BLACK
              color[y]<-BLACK
              color[p[p[z]]]<-RED
              z<-p[p[z]]
              else if z=right[p[z]]
                 then z<-p[z]
                 LEFT-ROTATE(T,z)
           color[p[z]]<-BLACK
           color[p[p[z]]]<-RED
           RIGHT-ROTATE(T,p[p[z]])
        else()
    color[root[T]]<-BLACK

具体可以看一下下面的图例（原文地址:http://www.cnblogs.com/deliver/p/5392768.html）  
节点插入有以下的几种的情况:  
1.当树还没有节点，插入一个新节点，根据限制2，当然是黑色咯~

![Center 4][]

2.给一个节点插入子节点，尽量把插入节点置成红色，因为置成黑色绝对要违反限制5。当看完“删除”就会发现黑色深度差导致的调整绝对要比颜色不符的调整要麻烦，所以我们会尽量避开。  
2.1 当父节点是黑色的，子节点只要置成红色，不违反1-4，也不影响父节点的两个子树的黑色深度，既不违反5。

![Center 5][]

2.2 当父节点是红色的。考虑到“调整深度差比较麻烦”，我们还是先把子节点置成红色，之后开始调整树。红黑树插入调整的关键是要考虑叔叔节点。  
在总结一下我们的问题：就是要解决“父”节点和“子”节点连续红色的问题，我们称之为“双红问题”。

![Center 6][]

G改成红色，P、U改成黑色。  
由于P和U的子节点都是黑色的，所以变色后也不会违反限制4。而且也不会违反限制5。  
这样做有个红第二招：左旋、右旋：主要的作用就是较深的子树让出一些深度给较浅的子树黑树的删除（准备知识）问题，就是G变成红色，但G的父节点也可能是红色的，如果这样，其实又是一个双红问题。

![Center 7][]  
  
  
2.2.2 黑叔  
  
  
乍看之下，天然的黑叔问题是不存在的，但是红叔问题不是可能会转化成双红问题，这时就可能出现黑叔的情况。  
  
  
黑叔要旋转，有两种情况  
  
  
case 1：右旋，再交换P和G的颜色

![Center 8][]

case 2：之后按case1右旋即可

![Center 9][]

三、红黑树的删除（准备知识）  
  
  
    由于删除比较复杂，先写准备知识垫一垫。  
  
  
1 旋转

第一招：把弯的变成直的

![Center 10][]  
  
第二招：左旋、右旋：主要的作用就是较深的子树让出一些深度给较浅的子树

![Center 11][]

2 一般查找二叉树删除节点  
  
  
    删除的方案有很多，但一般都会选下面这种，因为对整棵树各个分支深度的影响较小。  
  
  
    a.当被删除节点n是叶子节点，直接删除  
  
  
    b.当被删除节点n只有一个孩子，删除n，用孩子替代该节点的位置  
  
  
    c.当被删除结点n存在左右孩子时，真正的删除点应该是n的中序遍在前驱，或者说是左子树最大的节点，之后n的值替换为真正删除点的值。这就把c归结为a，b的问题。

![Center 12][]

3 由2可知，所有的删除问题都可以转化成删除叶子节点或单支节点（只有一个孩子）的问题

四、红黑树的删除

1 当删除节点n是红色的叶子节点，直接删除节点n，不影响红黑树平衡性质

![Center 13][]  
  
2 当删除节点n是红色的单支节点。不可能出现，如果孩子是红色，违反限制4；如果孩子是黑色的，违反限制  
![Center 14][]

3 当删除节点n是黑色的叶子节点，由于有岗哨的存在，可以转化为问题4  
4 当删除节点n是黑色的单支节点，既n有一个黑色的子节点。  
如下图，先说明一下记号，删表示被删除节点n，子表示其子节点，父，兄都很好理解了。黑色和红色表示真实的颜色，青色表示不确定的颜色。  
首先我们很大胆地直接删掉节点n，让子接替他的位置。

![Center 15][]

我们瞻前顾后地看一下，首先红黑树的删除问题的所有情况都讨论到了，但是有一个问题，就是4中这样删除会使“父”节点左子树的黑色深度比右子树少1。  
  
  
所以下面我们要解决的不是删除问题，而是一个红黑树的调整选转问题。要求是这样的，父节点的左孩子有一个黑色的节点，而且父节点的左子树黑色深度比右子树小1，要求调整它，使之满足红黑树限制。由于这个问题源于黑节点n有黑的子节点，我们称其为“双黑问题”。

4.1 红兄  
  
  
x的兄弟w为红色，则w的儿子必然全黑，w父亲p也为黑。  
改变p与w的颜色，同时对p做一次左旋，这样就将情况1转变为情况2,3,4的一种

![Center 16][]

4.2,4.3.4.4统称为黑兄问题  
  
  
4.2 黑兄二黑侄 又分为4.2.1和4.2.2

![Center 17][]

4.2.1 黑兄二黑侄红父  
p变成黑色，w变成红色，解决问题

![Center 18][]

4.2.2 黑兄二黑侄黑父

![Center 19][]

因为x子树相对于其兄弟w子树少一个黑色节点，可以将w置为红色，这样，x子树与w子树黑色节点一致，保持了平衡。  
  
  
如果p有兄弟，它的黑色深度就会比兄弟小1，这样4.2.2又转化成为了一个双黑问题，规约为1-4的情况。  
  
  
4.3 黑兄左红侄右黑侄  
w为黑色，w左孩子红色，右孩子黑色。  
交换w与左孩子的颜色，对w进行右旋。转换为情况4

![Center 20][]

[Center]: /images/20220711/c3558a4b4dd1425c8aeb52213aef691c.png
[proud.gif]: /images/20220711/2311e3de9846471cab0ac1b3abf371cd.png
[Center 1]: /images/20220711/edb287691d104ef9832d0859c78fb229.png
[Center 2]: /images/20220711/d2773bcc89c042b2a57c9d76570e420b.png
[Center 3]: /images/20220711/030911e3cd4144959848c78307e912d3.png
[Center 4]: /images/20220711/7570118c7caf4f86baf39bb607b83321.png
[Center 5]: /images/20220711/aee130df05ca4e4087a8329fe8dfca82.png
[Center 6]: /images/20220711/f70debfee2034a1fa77242c0128c9eaa.png
[Center 7]: /images/20220711/4040ff69b15447a69ceb90d0aaf1609a.png
[Center 8]: /images/20220711/b971c09db25747b9a4461b8cded234f4.png
[Center 9]: /images/20220711/c6101039875e4632b993204779a00d61.png
[Center 10]: /images/20220711/90398fed77cf4131af3fa4b8cbc973ba.png
[Center 11]: /images/20220711/e2c34b8a065044fabd7abd0e674a8d38.png
[Center 12]: /images/20220711/5b2d68f30ec94672a4568fabfd771640.png
[Center 13]: /images/20220711/566bd8e31ddc4e7faf634154969e51ae.png
[Center 14]: /images/20220711/91c559092fa844f59fb4c2a55a8ef813.png
[Center 15]: /images/20220711/17f79275d3b64aff88fe1f5da6b185bb.png
[Center 16]: /images/20220711/9268bf0c465247c0b054081ae38797e8.png
[Center 17]: /images/20220711/152f1c60aed545b898ee2cee1b72bdda.png
[Center 18]: /images/20220711/3d0d97ab29a447979519ac89f2c2d344.png
[Center 19]: /images/20220711/783f326bc5374df2868a284efb14289d.png
[Center 20]: /images/20220711/7caaa392b9784a5eb8a09ceeaecc71ef.png