树

树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。

在任意一棵非空树中：

（1）有且仅有一个特定的称为根（Root）的结点；

（2）当 n＞1 时，其余结点可分为 m（m＞0）个互不相交的有限集 T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

• 树的定义也是一种递归定义。
• 根结点是唯一的，不可能存在多个根结点
• 子树的个数没有限制，但它们一定是互不相交的。

结点分类

• 树的结点包含一个数据元素及若干指向其子树的分支。

• 结点拥有的子树数称为结点的度（Degree）。

• 度为 0 的结点称为叶结点（Leaf）或终端结点；

• 度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。

• 树的度是树内各结点的度的最大值。

结点间关系

• 结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）

• 同一个双亲的孩子之间互称兄弟（Sibling）。

• 结点的祖先是从根到该结点所经分支上的所有结点

• 以某结点为根的子树中的任一结点都称为该结点的子孙。

其他相关概念

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

• 双亲在同一层的结点互为堂兄弟

• 树中结点的最大层次称为树的深度（Depth）或高度

• 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

• 森林（Forest）是 m（m≥0）棵互不相交的树的集合。

树的存储结构

双亲表示法、孩子表示法、孩子兄弟表示法。

双亲表示法

以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。

#define MAX_TREE_SIZE 100

typedef int TElemType;

/// 双亲表示法结点结构
typedef struct PTNode
{
    TElemType data;///< 结点的数据信息
    int parent;///< 双亲的下标
}PTNode;

/// 树的结构体
typedef struct
{
    PTNode nodes[MAX_TREE_SIZE];///< 结点数组
    int r;///< 根的位置
    int n;///< 结点数
}PTree;

已知结点找其双亲的时间复杂度为 \(O(1)\) ，但是找结点的孩子需要遍历完整个结构。

多重链表表示法

• 每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。

• 树的每个结点的度，也就是它的孩子个数是不同的。有两种解决方案：

方案一 指针域的个数等于树的度

• 树的度是树各个结点度的最大值。指针域的个数等于树的度，这样每个结点的指针域都是够用的。

• 树中各结点的度相差很大时，会浪费空间，因为有很多结点的指针域是空的。

方案二 指针域的个数等于该节点的度

• 空间利用率是很高，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。

孩子表示法（邻接表）

• 把每个结点的孩子结点排列起来，以单链表作存储结构，做该结点的孩子链表

• 有 n 个结点，就有 n 个孩子链表，如果是叶结点则它的孩子链表为空。

• n 个头指针组成一个线性表，采用顺序存储结构，存放进一个一维数组中

• 该结构有两种结点：

/// 孩子结点
typedef struct CTNode
{
    int child;          ///< 存储孩子结点在表头数组的下标
    struct CTNode* next;///< 指向双亲结点的下一个孩子
} *ChildPtr;

/// 表头结点
typedef struct
{
    TElemType data;      	///< 该结点的数据信息
    ChildPtr firstchild;	///< 孩子结点的头指针
}CTBox;

/// 树
typedef struct
{
    CTBox nodes[MAX_TREE_SIZE];///< 结点数组
    int r;///< 根的位置
    int n;///< 结点数
}CTree;

该方法的问题是，如果要找结点的双亲，需要遍历整棵树才行。

孩子兄弟表示法

• 结点的第一个孩子如果存在就是唯一的。

• 结点的右兄弟如果存在也是唯一的（❗❗❗右兄弟不是堂兄弟）。

• 设置结点，除了数据域存储结点数据外，还设置两个指针域 firstchild 和 rightsib。

  • firstchild 指向该结点的第一个孩子。
  • rightsib 指向该结点的右兄弟。

可见这种存储结构与广义表的存储结构有点类似。

/// 树的孩子兄弟表示法
typedef struct CSNode
{
    TElemType data;     ///< 该结点的数据信息
    struct CSNode* firstchild;  ///< 指向第一个孩子结点的指针
    struct CSNode* rightsib;    ///< 指向该结点右兄弟的指针
}CSNode, *CSTree;

• 这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过fistchild找到此结点的长子，然后再通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到要找的孩子。
• 但是对于找双亲还是有缺陷，可以再增加一个 parent 指针域来解决快速查找双亲的问题。
• 孩子兄弟表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。这样就可以充分利用二叉树的特性和算法来处理这棵树了。

二叉树

二叉树（Binary Tree）是 n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点

• 每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

特殊二叉树

斜树

• 斜树就是斜着长的树。

  • 所有的结点都只有左子树的二叉树叫左斜树。
  • 所有结点都是只有右子树的二叉树叫右斜树。

• 斜树结点的个数等于二叉树的深度。

• 斜树的结构与线性表几乎相似，线性表结构就可以理解为是树的一种极其特殊的表现形式。

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

完全二叉树

对一棵具有 n 个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

完全二叉树的性质

• 叶子结点只能出现在最下两层。
• 最下层的叶子一定集中在左部连续位置。
• 倒数二层，若有叶子结点，一定都在右部连续位置。
• 如果结点度为 1，则该结点只有左孩子，即不存在只有右子树的情况。
• 同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

性质 1

• 在二叉树的第 \(i\) 层上至多有 \(2^{i-1}\) 个结点；

性质 2

• 深度为 k （即层数为 k）的二叉树至多有 \(2^k-1\) 个结点；

第一层最多 1 个结点，第二层最多 2 个结点，... 第 k 层最多 \(2^{k-1}\) 个结点，由等比数列求和公式，深度为 k 的树的结点最大个数为：

性质 3

• 设树的终端结点数（即叶子结点数）为 \(n_0\)，度为 1 的结点数为 \(n_1\)，度为 2 的结点数为 \(n_2\)
• 结点总数 \(n=n_0 + n_1 + n_2\)
• 分支线程总数：\(n-1=n_0+n_1+n_2-1\)，分支线程总数还等于 \(n_1+2n_2\) ，得 \(n_0 = n_2 + 1\)

性质 4

• 具有 n 个结点的完全二叉树的深度为 \(\lfloor\log_2n\rfloor+1\) （或 \(\lceil\log_2n\rceil\)）

证明，设具有 n 个结点的完全二叉树的深度为 k，对于深度为 k 的满二叉树，它的结点数为 \(2^k-1\) ，对于深度为 \(k-1\) 的满二叉树，结点数为 \(2^{k-1}-1\) 。则有：

因此，二叉树的深度为 \(\lfloor\log_2n\rfloor+1\) ，或写成 \(\lceil\log_2n\rceil\)

性质 5

• 性质5：如果对一棵有n个结点的完全二叉树（其深度为⌊log2n⌋+1）的结点按层序编号（从第1层到第⌊log2n⌋+1层，每层从左到右），对任一结点i（1≤i≤n）有：
  • 如果 \(i=1\)，则结点 \(i\) 是二叉树的根，无双亲；如果 \(i>1\)，则其双亲是结点 \(⌊i/2⌋\)。
  • 如果 \(2i>n\)，则结点 \(i\) 无左孩子（结点 \(i\) 为叶子结点）；否则其左孩子是结点 \(2i\) 。
  • 如果 \(2i+1>n\) ，则结点 \(i\) 无右孩子；否则其右孩子是结点 \(2i+1\)。

二叉树的存储结构

二叉树的顺序存储结构

• 对于完全二叉树，完全可以用顺序存储结构：

• 对于一般二叉树，可以将其按完全二叉树编号，把不存在的结点设置为空： "^"。

• 顺序存储一般只用于完全二叉树，用于其他二叉树可能会造成较大的空间浪费。

二叉链表

• 使用链式存储结构，每个结点设计一个数据域存储数据，两个指针域指向左孩子和右孩子。这样的链表称为二叉链表。

/// 二叉树结点结构
typedef struct BiTNode
{
    TElemType data;///< 结点数据
    struct BiTNode* lchild;///< 左孩子指针
    struct BiTNode* rchild;///< 右孩子指针
}BiTNode, *BiTree;

• 如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表

遍历二叉树

二叉树遍历原理

• 二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

• 深度优先搜索(dfs)：前序遍历、中序遍历、后序遍历

• 宽度优先遍历(bfs)：层序遍历

• 二叉树的前中后序遍历一般使用递归算法

• 递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。，因此用栈可以可以将递归方法转换为迭代方法，使用栈可以实现二叉树的前中后序的遍历了。

• 层序遍历采用队列数据结构，每轮循环，同一层结点出栈，然后从左到右遍历该层结点的所有孩子结点，遍历的同时将孩子结点入队，下一轮循环，继续讲这一层的结点出栈，然后遍历孩子结点的孩子结点，依此类推。

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

/// 二叉树前序遍历递归算法
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
    printf("%c", T->data);// 先访问根结点
    PreOrderTraverse(T->lchild);// 再先前序遍历左子树
    PreOrderTraverse(T->rchild);// 最后前序遍历右子树
}

/// 二叉树前序遍历迭代算法
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    if(root == nullptr) return result;
    stack<TreeNode*> st;
    st.push(root);
    while(!st.empty()){
        TreeNode* cur = st.top();						// 中
        st.pop();
        result.emplace_back(cur->val);
        if(cur->right != nullptr) st.push(cur->right);	// 右（空节点不入栈）
        if(cur->left != nullptr) st.push(cur->left);	// 左（空节点不入栈）
    }
    return result;
}

中序遍历

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

/// 二叉树中序遍历递归算法
void InOrderTraverse(BiTree T)
{
    // 如果为空即返回
    if (T == NULL)
        return;
    InOrderTraverse(T->lchild);// 先中序遍历左子树
    printf("%c", T->data);     // 然后访问根节点
    InOrderTraverse(T->rchild);// 最后中序遍历右子树
}

/// 二叉树中序遍历迭代算法
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur != NULL || !st.empty()) {
        if (cur != NULL) { // 指针来访问节点，访问到最底层
            st.push(cur); // 将访问的节点放进栈
            cur = cur->left;                // 左
        } else {
            cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
            st.pop();
            result.push_back(cur->val);     // 中
            cur = cur->right;               // 右
        }
    }
    return result;
}

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

/// 后序遍历算法
void PostOrderTraverse(BiTree T)
{
    // 如果为空即返回
    if (T == NULL)
        return;
    PostOrderTraverse(T->lchild);// 先后序遍历左子树
    PostOrderTraverse(T->rchild);// 然后后序遍历右子树
    printf("%c", T->data);       // 最后访问根节点
}

vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if (root == NULL) return result;
        st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
            if (node->right) st.push(node->right); // 空节点不入栈
        }
        reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
        return result;
}

层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

/// 层序遍历迭代法
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if(root == nullptr) return result;
    queue<TreeNode*> que;
    que.push(root);
    while(!que.empty()){
        int n = que.size();
        vector<int> row;
        for(int i = 0; i < n; i++){
            TreeNode* cur = que.front();
            que.pop();
            row.emplace_back(cur->val);
            if(cur->left != nullptr) que.push(cur->left);
            if(cur->right != nullptr) que.push(cur->right);
        }
        result.emplace_back(row);
    }

    return result;
}

/// 层序遍历 递归法
void bfs(vector<TreeNode*>& nodes, vector<vector<int>>& result){
    if(nodes.empty()) return;
    vector<TreeNode*> nextNodes;
    vector<int> row;
    for(auto& elem : nodes){
        row.emplace_back(elem->val);
        if(elem->left != nullptr) nextNodes.emplace_back(elem->left);
        if(elem->right != nullptr) nextNodes.emplace_back(elem->right);
    }
    result.emplace_back(row);
    bfs(nextNodes, result);
}

推导遍历结果

已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历结果是多少？

• 由 ABCDEF 知树的根节点为 A，结合中序遍历CBAEDF 知 A 的 左子树包括 B、C 两个结点，右子树包括 D、E、F 三个结点。

• A 的左子树的前序遍历为 BC ，则 B 为 A 的左孩子。左子树的中序遍历为 CB，则 C 为 B 的左孩子

• A 的右子树的前序遍历为 DEF，说明 D 是 A 的右孩子，E 和 F 是 D 的子孙（不一定是左右孩子）。
• A 的右子树的中遍历为 EDF，说明 E 是 D 的左孩子，F 是 D 的右孩子

• 由此可得后续遍历的结果为：CBEFDA

二叉树的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列。

• 由后序序列 BDCAFGE，可得 E 为树的根结点。在结合中序序列是 ABCDEFG 得 E 的左子树包括 ABCD，E的右子树包括 FG
• E 的左子树后序序列为 BDCA ，可知 A 为 E 的左孩子。再结合中序序列是 ABCD 得 A 的右子树包括 BCD。
• A 的右子树后序序列为 BDC，可知 C 为 A 的右孩子。再结合中序序列为 BCD 得 B 是 C 的左孩子，D 是 C 的右孩子。目前前序序列的分析结果为 EACBD
• E 的右子树后序序列为FG，可知 G 是 E 的右孩子。再结合中序序列为 FG 得 F 为 G 的左孩子。E 的左子树的前序序列则为 GF
• 最后整棵树的前序序列为 EACBDGF。

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

注意：已知前序和后序遍历，是不能确定一棵二叉树的。

二叉树的建立

通过输入遍历序列来构建二叉树。

• 为了能让每个结点确认是否有左右孩子，对树进行了扩展：

• 如上图所示，扩展后的前序遍历就为 AB#D##C##

/// 以扩展二叉树的前序遍历来构造二叉树
void CreateBiTree(BiTree* T)
{
    TElemType ch;
    scanf_s("%c", &ch);
    if (ch == '#')
    {
        *T = NULL;
    }
    else
    {
        *T = malloc(sizeof(BiTNode));
        if (!*T)
            exit(1);// 溢出，异常退出
        (*T)->data = ch;// 生成根节点
        CreateBiTree(&(*T)->lchild);// 构造左子树
        CreateBiTree(&(*T)->rchild);// 构造右子树
    }
}

本栏目推荐文章
• 2024/1/13 算法笔记
• Jmeter 如何连接mysql数据库？
• SQL Server 检测是不是数字型数据的两种方法
• 如何通过Navicat把MySQL远程数据库导入到本地数据库
• 和利时MACS6通过dat文件实现任意时间范围与测点的历史数据提取与科研分析
• 深入理解spring框架：剖析多线程模式下数据库连接
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 数据可视化是如何帮助大型企业提高效率的？
• redis 数据库

数据结构 算法 结构 专题 数据数据结构 算法 结构 专题 数据结构 结构 专题 数据 数据结构 算法 结构 数据 数据结构 结构 基础 专题 算法 数据结构 根基 线性 数据结构 算法 结构 基础 算法 数据结构 结构 数据 算法 数据结构 根基 结构 队列 算法 层级 数据结构 数据结构 队列 算法 结构