【数据结构】树：二叉树、遍历二叉树与线索二叉树等树的定义与解析、二叉树遍历实现（递归、迭代）C++

迈不过友情╰ 2021-12-10 13:23 244阅读 0赞

\#笔记整理  
今天复习总结了一下数据结构中树相关的知识点。  
先记录一些主要的，慢慢补充。

## 树（tree） ##

**树**是n (n>=0)个结点的有限集。  
树是以分支关系定义的层次结构，是一类重要的非线性结构。  
**特性：**  
在任意一棵非空树中

1.  有且仅有一个特定的称为根（root）的结点；
2.  当  n > 1 n > 1 n>1 时，其余结点可分为 m （ m > 0 ） m（m>0） m（m>0）个互不相交的有限集 T 1 ， T 2 ， … ， T m T\_1，T\_2，…，T\_m T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的**子树（subtree）**。

**度（degree）**：结点拥有的子树数。  
度为0的结点称为 **叶子（leaf）** 或 **终端结点**。  
度不为0的结点称为**非终端结点**或**分支结点**。除根结点之外，分支结点也称为**内部结点**。  
树的度是树内各结点的度的最大值。

**结点的层次（level）** 从根开始定义起，根为第一层，根的孩子为第二层。

**树的深度（depth）** 或高度：树中结点的最大层次称为树的深度。

### 森林（forest） ###

森林是m（m>=0）棵互不相交的树的集合。  
对树中每个结点而言，其子树的集合即为**森林。**

### 二叉树 ###

满足以下两个条件的树形结构叫做 **二叉树（Binary Tree）**：  
（1） 每个结点的度都不大于2；  
（2） 每个结点的孩子结点次序不能任意颠倒。  
由此定义可以看出，一个二叉树中的每个结点只能含有0、 1或2个孩子，而且每个孩子有左右之分。把位于左边的孩子叫做**左孩子**，位于右边的孩子叫做**右孩子**。

**性质1：** 二叉树的第 i 层上至多有  2 i − 1 2^\{i-1\} 2i−1 个结点 （ i > = 1 ) （i>=1) （i>=1)；  
**性质2：** 深度为k的二叉树至多有  ( 2 k ) − 1 (2^k) - 1 (2k)−1 个结点 （ k > = 1 ） （k>=1） （k>=1）；  
**性质3：** 对任何一棵二叉树 T，若其终端结点数为 n 0 n\_0 n0，度为2的结点数为 n 2 n\_2 n2，则  n 0 = n 2 + 1 n\_0 = n\_2 + 1 n0=n2\+1；

在继续介绍其他性质之前，先介绍一下满二叉树和完全二叉树：

一棵深度为 k 且有  ( 2 k ) − 1 (2^k)-1 (2k)−1个结点的二叉树称为**满二叉树**。  
在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从1至 n 的结点一一对应时，称为 **完全二叉树**（不同资料定义不同），如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
**满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。**

![在这里插入图片描述][20190712183939334.png]

#### 二叉树的存储结构 ####

二叉树的存储结构有两种： **顺序存储结构和链式存储结构**。

###### 顺序存储结构： ######

编号从小到大的顺序就是结点存放在连续存储单元的先后次序。  
如下图，使用顺序存储结构存储完全二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][2019071218422670.png]

而当非完全二叉树用顺序存储结构进行存储时：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]

**可见：非完全二叉树不适合进行顺序存储。**

###### 链式存储结构 ######

二叉树的链式存储结构可分为 **二叉链表** 和 **三叉链表**。

**二叉链表每个结点的结构：**  
![在这里插入图片描述][20190712184356840.png]  
二叉链表示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]

**三叉链表每个结点结构：（每个结点有三个指针域）**  
![在这里插入图片描述][20190712184428659.png]  
三叉链表示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 5]

#### 遍历二叉树和线索二叉树 ####

##### 遍历二叉树（traversing binary tree） #####

按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。遍历可认为是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。  
它是最基本的运算，是二叉树中所有其它运算的基础。

假如以L、D、R分别表示遍历左子树、访问根节点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。  
若限定只能先左后右，则只有前3种情况，分别称为**先序遍历**、**中序遍历**和**后序遍历**。

**三种遍历方法的递归定义**  
先序（先根）遍历（DLR）操作过程：  
若二叉树为空， 则空操作， 否则  
(1) 访问根结点；  
(2) 按先序遍历左子树；  
(3) 按先序遍历右子树。

中序（中根）遍历（LDR）操作过程：  
若二叉树为空，则空操作，否则：  
(1) 按中序遍历左子树；  
(2) 访问根结点；  
(3) 按中序遍历右子树。

后序（后根）遍历（LRD）操作过程：  
若二叉树为空， 则空操作， 否则：  
(1) 按后序遍历左子树；  
(2) 按后序遍历右子树；  
(3) 访问根结点。

**遍历实现代码：**

// 先序遍历二叉树，递归算法
    void preOrderTraverse(BiTree root){
        
        if(root != NULL){
        
            cout << root->data << ' ';       // 访问根结点
            preOrderTraverse(root->left);    // 先序遍历根的左子树
            preOrderTraverse(root->right);   // 先序遍历根的右子树
        }
    }
    
    // 先序遍历二叉树，非递归算法，迭代实现
    void preOrderTraverse2(BiTree root){
        
        stack<BiTreeNode *> s;               // 存储二叉树结点的栈
        BiTreeNode *t  = root;
        s.push(NULL);                        // 先压入一个空指针作为标记
        while(t != NULL){
        
            cout << t->data << ' ';          // 访问当前节点
            if(t->right != NULL){
                    // 先把右孩子压入栈（先处理左子树）
                s.push(t->right);
            }
            if(t->left != NULL){
        
                t = t->left;                 // t 指向其左孩子
            }else{
                                   // 左孩子为空
                t = s.top();                 // 获得栈顶元素即右孩子指针
                s.pop();
            }
        }
    }
    
    
    // 中序遍历二叉树，递归算法
    void inOrderTraverse(BiTree root){
        
        if(root != NULL){
        
            inOrderTraverse(root->left);     // 中序遍历根的左子树
            cout << root->data << ' ';       // 访问根结点
            inOrderTraverse(root->right);    // 中序遍历根的右子树
        }
    }
    
    // 中序遍历二叉树，非递归算法，迭代实现
    void inOrderTraverse2(BiTree root){
        
        stack<BiTreeNode *> s;               // 存储二叉树结点的栈
        BiTreeNode *t  = root;
    
        while(t != NULL || !s.empty()){
        
            if(t != NULL){
        
                s.push(t);                   // 将 t 压入栈，先访问其左子树
                t = t->left;
            }else{
                                   // 若 t 为空
                t = s.top();                 // 取出 栈顶元素，即树或子树的根结点
                s.pop();
                cout << t->data << ' ';      // 访问当前结点
                t = t->right;                // 指向其右孩子
            }
        }
    }
    
    
    // 后序遍历二叉树递归算法
    void postOrderTraverse(BiTree root){
        
        if(root != NULL){
        
            postOrderTraverse(root->left);    // 后序遍历根的左子树
            postOrderTraverse(root->right);   // 后序遍历根的右子树
            cout << root->data << ' ';        // 访问根结点
        }
    }
    
    // 后序遍历非递归算法需要使用的结构体
    enum Tags {
        Left, Right};                  // 枚举类型标志位，stackNode使用
    typedef struct {
        
        BiTreeNode *p;                        // 结点指针
        Tags flag;                            // 标志位
    }stackNode;
    
    // 后序遍历二叉树，非递归算法，迭代实现
    void postOrderTraverse2(BiTree root){
        
        stack<stackNode > s;                  // 存储二叉树结点的栈
        stackNode sNode;                      // 栈元素
        BiTreeNode *t  = root;
    
        while(t != NULL || !s.empty()){
        
            while(t != NULL){
                         // t 非空，入栈根结点，继续向左，找到最左的根结点的左孩子（空指针）
                sNode.p = t;
                sNode.flag = Left;            // 设置标志位为 Left，表示其出栈时已访问过左子树
                s.push(sNode);
                t = t->left;
            }
            sNode = s.top();
            s.pop();
            t = sNode.p;
            if(sNode.flag == Left){
                   // 已访问过左子树
                sNode.flag = Right;           // 标志位设为 Right，表示其出栈时已访问过左子树
                s.push(sNode);
                t = t->right;
            }else{
                                    // 已访问过右子树
                cout << t->data << ' ';
                t = NULL;                     // 设置 t 为空，以便继续出栈
            }
        }
    }

[github源码][github]

##### 线索二叉树 #####

线索二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实质上是对一个非线性结构进行线性化操作，使每个结点（除首尾结点外）在线性序列中**有且仅有一个直接前驱和直接后继**。

线索二叉树规定：  
若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指向其前驱；  
若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指向其后继。  
因此需要增加两个标志域，作为结点是否含有左右孩子的标志：  
![在这里插入图片描述][20190712184920752.png]  
![在这里插入图片描述][20190712184925360.png]  
总的来说，指向前驱和后继结点的指针叫做**线索**。 以这种结构组成的二叉链表作为二叉树的存储结构，叫做**线索链表**。对二叉树以某种次序进行遍历并且加上线索的过程叫做**线索化**。线索化了的二叉树称为**线索二叉树**。

线索二叉树示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 6]  
  
  
  
其他常用的树还有二叉排序树、平衡二叉树、红黑树、B-树、B-树、键树等等，这几类树其实属于查收表，由于还没复习到，先简单介绍一下：

**二叉排序树（Binary Sort Tree）：** 又称 **二叉查找树（Binary Search Tree）**，树中任何一个结点，其左子树上所有结点的值均小于该结点的值，其右子树上所有结点的值均大于该结点的值。

**平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree）：** 又称为AVL树。它要么是空树，要么具有下列性质：

*  它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
 *  若将二叉树上结点的平衡因子BF（Balance Factor）定义为该结点的左子树的深度减去右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0、1。

**B-树：** 一种平衡的多路查找树，它在文件系统中很有用，每个非终端结点里包含了关键字信息。  
**B+树：** 是应文件系统需要而出现的一种B-树的变型树。  
**键树（Digital Search Trees）：** 又称 **数字查找树**，是一棵度 >= 2 的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。

部分内容来源：

1.  《数据结构（C语言版）》----严蔚敏
2.  《数据结构》课堂教学ppt ---- 刘立芳
3.  《数据结构算法与解析（STL版）》 ---- 高一凡

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211210/449eaf40cf8e403f87b938705adabd0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211210/dd54ca4def5842d7a681a97fddf3d52e.png
[20190712183939334.png]: /images/20211210/6f075b0d6ec54106be579f9b835fc5b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211210/82c83b0e27f34ef69f3089e75caf183b.png
[2019071218422670.png]: /images/20211210/579a8e0429e04e489bea596a15ab026d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211210/dd606018daab4456bedd133fe0fe3cff.png
[20190712184356840.png]: /images/20211210/18a1cacdf93b4f31b819e5a5025e757e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]: /images/20211210/b30ab6e8cd394b0baf0595d28c698987.png
[20190712184428659.png]: /images/20211210/87e354e7bf224483bdfe970a06b413e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 5]: /images/20211210/4ac46de6f3464ab7906a2b312d37173e.png
[github]: https://github.com/yohstone/data-structure/blob/master/binary_tree.cpp
[20190712184920752.png]: /images/20211210/82c966245ce043a48e44a4971b2ac5ef.png
[20190712184925360.png]: /images/20211210/ae055c36c00a4fe8a1b4f7e655a22970.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 6]: /images/20211210/d1c41b6b264843418fbd3da3556cefdf.png