企业官网建设流程全解析

一、前言

本章节是数据结构与算法的第七篇：树与二叉树。内容包括：树、二叉树的概念和性质、二叉树的实现、树、森林和二叉树之间的转换。

二、树的概念

树是由n（n>= 0）个结点构成的有限集合T。n=0为空树。

有序树：把结点从上到下从左到右的次序顺序编号

森林：多个树放在一起

三、二叉树的概念和性质

1.概念

！度为2的有序树 不是 二叉树

空二叉树：不含任何结点的空集

满二叉树：一个二叉树中的任意一层结点个数都达到最大值

完全二叉树：叶子结点只可能出现在最下面2层

正则二叉树：严格二叉树，只有度为2的分支结点和度为0的子节点

扩充二叉树：空的地方补上叶子结点

2.性质

性质1：第 i 层最多有 2^(i−1) 个结点

等比数列：第一层1个、第二层2个、第三层4个...

性质2：高度为 k 的二叉树最多有 2^k − 1 个结点

性质3：叶子结点数 n₀ 与度为 2 的结点数 n₂ 满足 n₀ = n₂ + 1

结点总数 = 度为0,1,2结点树之和

性质4：完全二叉树高度为 ⌊log₂ n⌋+1

相当于性质2反过来用

性质5. 完全二叉树的顺序存储性质

按层序编号（i = 1 为根）父结点为 ⌊i/2⌋；左孩子为 2i（若 ≤ n）；右孩子为 2i+1（若 ≤ n）。

四、二叉树的表现和实现

1.存储结构

顺序存储：

顺序存储就是用一组地址连续的存储单元依次存放二叉树的结点，本质上是一个数组。

对完全二叉树来说，顺序存储非常自然：按层序（从上到下、从左到右）给结点编号，编号即数组下标，根结点放在下标 1（或 0）处。此时父子关系可以直接用下标算出来：

• 若根结点下标为 1：结点 i 的父结点为 ⌊i/2⌋，左孩子为 2i，右孩子为 2i+1。
• 若根结点下标为 0：结点 i 的父结点为 ⌊(i−1)/2⌋，左孩子为 2i+1，右孩子为 2i+2。
• 孩子下标超过结点总数 n 时，说明该孩子不存在。

顺序存储通常用于完全二叉树或满二叉树，例如堆（大根堆、小根堆）就是顺序存储的典型应用；而对于形态任意的普通二叉树，更常用的是下面要介绍的链式存储。

链式存储：

链式存储用指针把结点串起来，每个结点单独申请空间，不必像顺序存储那样给缺失结点留空位，形态任意的二叉树也能高效存储。

按指针域的数量，常见的有二叉链表和三叉链表两种结构：

二叉链表

每个结点包含数据域和两个指针域，分别指向左孩子和右孩子，这也是最常用的二叉树存储结构。

// 二叉链表结点 struct BiNode { char data; // 数据域 BiNode* lchild; // 指向左孩子 BiNode* rchild; // 指向右孩子 BiNode(char d) : data(d), lchild(nullptr), rchild(nullptr) {} }; typedef BiNode* BiTree; // 二叉树类型，指向根结点

三叉链表

在二叉链表的基础上再增加一个指向父结点的指针，便于从某个结点直接回溯到它的双亲。

// 三叉链表结点 struct TriNode { char data; // 数据域 TriNode* lchild; // 指向左孩子 TriNode* rchild; // 指向右孩子 TriNode* parent; // 指向父结点 TriNode(char d) : data(d), lchild(nullptr), rchild(nullptr), parent(nullptr) {} }; typedef TriNode* TriTree; // 三叉链表二叉树类型

两种结构的对比

• 空间开销：设结点数为 n，二叉链表共有 2n 个指针域，其中只有 n−1 个用于指向孩子，其余 n+1 个为空指针；三叉链表有 3n 个指针域，比二叉链表多出 n 个父指针，空间开销更大。
• 二叉链表：结构简单、空间省，适合以自顶向下为主的遍历、递归求高度、统计结点数等操作，是二叉树最通用的存储方式。
• 三叉链表：多一个父指针，可以 O(1) 找到双亲，适合需要频繁回溯父结点的场景，例如求两个结点的最近公共祖先、按结点向上查找路径、非递归遍历中回退等；代价是每个结点多一个指针的存储开销，且插入、删除时要同步维护 parent 指针。

实际做题和工程中，若没有明确要求，一般默认使用二叉链表；只有在需要频繁访问父结点时，才考虑三叉链表。

2.遍历运算

深度遍历（竖着的）

前序（根左右）

核心代码：

cout << t-data << ' '; //访问当前结点 preOrder(t->left); //前序遍历左子树 preOrder(t->right); //前序遍历右子树

注：这里的t是根结点的指针，preOrder是提前写好的递归前序遍历函数

中序（左根右）

核心代码

inOrder(t->left); cout << t->data << ' '; inOrder(t->right);

把这三行代码交换顺序，然后改成对应的函数

后序（左右根）

核心代码

postOrder(t->left); postOrder(t->right); cout << t->data << ' ';

广度遍历（横着的）

广度遍历（层序遍历）按从上到下、从左到右的顺序逐层访问结点。

借助队列实现：根结点先入队，之后每次取出队头结点并访问，再把它的左孩子、右孩子依次入队，直到队列为空。

核心代码：

void levelOrder(BiNode* t) { if (t == nullptr) return; // 空树直接返回 queue<BiNode*> q; q.push(t); // 根结点入队 while (!q.empty()) { BiNode* p = q.front(); // 取出队头结点 q.pop(); cout << p->data << ' '; // 访问当前结点 if (p->lchild) q.push(p->lchild); // 左孩子入队 if (p->rchild) q.push(p->rchild); // 右孩子入队 } }

注：这里的t是根结点的指针，需要包含头文件<queue>。每个结点只入队、出队各一次，因此时间复杂度为 O(n)，空间复杂度为 O(n)（最坏情况队列中存放一整层结点）。

五、树和森林

1.树、森林、二叉树的相互转换

树变二叉树：

兄弟相连留长子

二叉树变树：

左孩右右连双亲，去掉原来右孩线

森林变二叉树：

树变二叉根相连

二叉树变森林：

去掉全部右孩线，孤立二叉再还原

六、总结

本文系统介绍树与二叉树的基本概念、性质及存储实现。重点阐述二叉树的五类形态（如满、完全、正则、扩充二叉树）及其性质，包括层结点数、高度、结点关系等。详细对比顺序存储（适用于完全/满二叉树）与链式存储（二叉链表为主，三叉链表支持父指针回溯），并讲解前序、中序、后序及层序遍历的递归与非递归实现。最后说明树、森林与二叉树间的相互转换方法，为后续算法设计奠定基础。