[数据结构] 树与二叉树
树的基本概念
树的定义
树是由\(n(n \geq 0)\)个节点组成的有限集。当\(n = 0\)时，称为空树。
任意一棵非空树应满足以下两点：
（1）有且仅有一个特定的称为根的节点；
（2）当\(n > 1\)时，其余节点可分为\(m(m>0)\)个互不相交的有限集\(T_1, T_2, \dots, T_m\)，其中每个集合本身又是一棵树，称为根的子树；
树有以下几个特点：
（1）根节点没有前驱，除根节点外所有节点有且仅有一个前驱；
（2）树中所有节点有零个或多个后继；
（3）n个节点的树中有n-1条边；
基本术语
（1）祖先、子孙、父亲、孩子、兄弟、堂兄弟
如图，考虑节点K，从根A到节点K的唯一路径的所有其他节点，称为节点K的祖先；路径上里节点K最近的节点E称为节点K的父亲，而K为E的孩子；有相同父亲节点的节点称为兄弟，如K和L；父亲节点在同一层的节点互为堂兄弟，如E、F、H、I、J。
（2）节点的度和树的度
树中一个节点的孩子个数称为节点的度；
树中节点的最大度数称为树的度；
（3）分支节点和叶节点
度大于0的节点称为分支节点（非终端节点）；度为0（没有孩子节点）的节点称为叶节点（终端节点）；
（4）节点的深度、高度、层次
节点的层次从树根开始定义；
节点的深度即节点所在的层次；
节点高度是以该节点为根的子树的高度；树的高度是树中节点的最大层数；
（5）有序树和无序树
树中节点各子树从左到右是有次序的，不能互换，称为有序树，否则称为无序树；
（6）路径和路径长度
树中两个节点之间的路径是由这两个节点之间所经过的节点序列构成的，而路径长度是路径上所经过的边的个数；
（7）森林
森林是\(m(m \ge 0)\)棵互不相交的树的集合。
树的性质
（1)树的节点数n等于所有节点的度数之和加1。
证明：
如果是以层次的方式看待树，那么根节点的度，就等于第二层的节点数，第二层节点的度数之和，就等于第三层的节点数，以此类推。那么从第一层开始的每层节点度数和就等于从第二层开始的节点数之和，换言之，只是少了根节点。
（2）度为\(m\)的树中第\(i\)层至多有\(m^{i-1}\)个节点（\(i \ge 1\)）
证明：
（数学归纳法及简单推导）
第一层：至多有一个节点（根节点）；
第二层：至多有m个节点（仅有两层：根节点孩子节点个数=度数m；超过两层：根节点度数大于其孩子节点度数，第二层有m个节点；根节点度数小于其孩子节点度数，树的度数为孩子节点度数m，第二层有空缺）；
第三层：至多有\(m^2\)个节点；
根据数学归纳法，易得第n层有\(m^{i-1}\)个节点。
（3）高度为\(h\)的\(m\)叉树至多有\((m^h-1)/(m-1)\)个节点
证明：
（首先说明，这个性质在\(h>1\)时才成立）
由性质2，节点最多，则每层都有\(m^{i-1}\)个节点，则节点总数：
\[n = m^0+m^1+m^2+\dots+m^{h-1} = \frac{m^h-1}{m-1}。 \]
（4）度为\(m\)、具有\(n\)个节点的树的最小高度\(h\)为\(\lceil \log_m(n(m-1)+1) \rceil\)
证明：
高度最小，则每个节点的度都要达到\(m\)。由性质3：\(n = \frac{m^h-1}{m-1}\),
整理可得：\(m^h - 1 = n \times (m - 1) \Longrightarrow h = \log_m(n(m-1)+1)\) ；
由于多余节点也是一层，向上取整，得到最小高度
（5）满\(m\)叉树节点编号\(i\)的第\(k\)个孩子节点编号为\((i-1)m+k+1(1 \le k \le m)\)
证明：
设节点 \(i\)为该$ m$ 叉树的第 $h \(层\)（h=1，2，3…)$，
则前 \(h-1\) 层共有\(N_1 = \frac{m^{h-1}-1}{m-1}\)个节点，前\(h\)层共有\(N_2 = \frac{m^h-1}{m-1}\)个节点，显然\(i\)为第\(h\)层的第\(i-N_1\)个节点，\(\Longrightarrow i\)有\(i-N_1-1\)个左兄弟
\(\Longrightarrow i\)的第一个孩子\(j\)有\((i-N_1-1)m\)个左兄弟，在第\(h+1\)层的次序为\((i-N_1-1)m+1\)，在树中的编号为\(N_2+(i-N_1-1)m+1\)：
\[\begin{aligned} & N_2 = \frac{m^h-1}{m-1} \\ & j = N_2+(i-N_1-1)m+1 \end{aligned} \]\(\Longrightarrow\)节点\(i\)第的一个孩子\(j = (i-1)m+2\);
又树为m叉树，\(\Longrightarrow i\)的最后一个孩子\(j = (i-1)m+2+m-1=(i-1)m+m+1\)
\(\Longrightarrow i\)的节点的孩子节点编号为\((i-1)m+k+1(1 \le k \le m)\)
二叉树的概念
二叉树的定义及主要特征
二叉树是一种特殊的树形结构，其特点是每个节点最多只有两棵子树且子树有左右之分，次序不能颠倒。
【注】二叉树与度为2的有序树的区别：
- 度为2的树至少有3个节点，二叉树可以为空；
- 度为2的有序树的孩子的左右次序是相对另一个孩子而言的，若某个节点只有一个孩子，则这个孩子就无序区分其左右次序；而二叉树无论其孩子数是否为2，均需要确定其左右次序。
几种特殊的二叉树：
- 满二叉树：高度为\(h\)，且有\(2^h-1\)个节点的二叉树，对满二叉树按层序编号，约定从根节点起，自上而下，自左向右，每个节点对应一个编号，对编号为\(i\)的节点，若有父亲节点，父亲节点的编号为\(\lfloor i/2 \rfloor\)，若有左孩子，左孩子节点为\(2i\)，若有右孩子，右孩子节点为\(2i+1\)。
- 完全二叉树：高度为\(h\)，有\(n\)个节点，当且仅当每个节点都与高度为\(h\)的满二叉树中编号为\(1-n\)的节点一一对应时，称完全二叉树.
- 二叉排序树：左子树上的所有节点的关键字均小于根节点的关键字；右子树上所有节点的关键字均大于根节点的关键字，左子树和右子树又各是一棵二叉排序树。
- 平衡二叉树：树中任意一个节点的左子树和右子树的高度之差的绝对值不超过1。
- 正则二叉树：树中每个分支节点都有2个孩子，即树中只有度为0或2的节点。
二叉树的性质
（1）非空二叉树的叶节点数等于度为2的结点数加一。
证明：
设度为0,1,2的节点个数分别为\(n_0,n_1,n_2\)，节点总数\(n = n_0+n_1+n_2\).
看二叉树中的分支数，除根节点外，其余节点都有一个分支进入，设B为分支总数，则\(n=B+1\)。由于这些分支都是由度为1或2的节点射出的，因此有\(B=n_1+2n_2\)。
结合以上公式，得到\(n_0=n_2+1\)。
（2）非空二叉树的第\(k\)层最多有\(2^{k-1}\)个节点(\(k \ge 1\))。
证明：
等比数列。
（3）高度为\(h\)的二叉树至多有\(2^h-1\)个节点(\(h \ge 1\))。
证明：
（2）中等比数列求和。
（4）对于完全二叉树从上到下，从左到右的顺序依次编号\(1,2,\dots,n\)，则有以下关系：
- 若\(i \le \lfloor n/2 \rfloor\)，则节点\(i\)为分支节点，否则为叶节点，即最后一个分支节点的编号为\(\lfloor n/2 \rfloor\)。
- 叶节点只可能在层次最大的两层上出现。
- 若有度为1的节点，则只可能有1个，且该节点只有左孩子而无右孩子。
- 按层次编号后，一旦出现某节点为叶节点或只有左孩子的情况，则编号大于\(i\)的节点均为叶节点。
- 若\(n\)为奇数，则每个分支节点都有左右孩子；若\(n\)为偶数，则编号最大的分支节点只有左孩子，没有右孩子，其他分支节点都有左、右孩子。
- 当\(i>1\)时，节点\(i\)的父亲节点的编号为\(\lfloor i/2 \rfloor\)。
（5）具有\(n(n>0)\)个节点的完全二叉树高度为\(\lceil \log_2(n+1) \rceil\)或\(\lfloor \log_2n \rfloor+1\)。
二叉树的存储结构
（1）顺序存储结构
二叉树的顺序存储是用一组连续的存储单元依次自上而下、自左向右存储完全二叉树上的节点匀速，即将完全二叉树上编号\(i\)的节点元素存储在一维数组下标为\(i-1\)的分量中。
【注】从数组下标1开始存储树中的节点，保证数组下标与节点编号一致。
（2）链式存储结构
顺序存储空间利用率较低，因此二叉树一般都采用链式存储结构，用链表节点来存储二叉树中的每个节点。在二叉树中，节点结构通常包括若干数据域和若干指针域，二叉链表至少包含三个域：数据域data、左指针域lchild、右指针域rchild。
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
二叉树的遍历及线索二叉树
二叉树的遍历
二叉树的遍历是按照某条搜索路径访问树中每个节点，使得每个节点均被访问一次，而且仅被访问一次。由于二叉树是一种非线性结构，每个节点都可能有两棵子树，因此需要寻找一种规律，以便使二叉树上的节点能排列在一个线性队列上，进而便于遍历。
遍历一棵二叉树要决定对根节点\(N\)，左子树\(L\)和右子树\(R\)的访问顺序。
NLR（先序遍历，PreOrder）
若二叉树为空，则什么也不做；否则，（1）访问根节点；（2）先序遍历左子树；（3）先序遍历右子树。
递归算法如下：
void PreOrder(BiTree T) {
if(T != NULL) {
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
非递归算法：
void PreOrder(BiTree T) {
InitStack(S);
BiTree p = T;
while(p || ! IsEmpty(S)) {
if(p) {
visit(p);
Push(S, p);
p = p->lchild;
}
else {
Pop(S, p);
p = p->rchild;
}
}
}
LNR（中序遍历，InOrder）
若二叉树为空，则什么也不做；否则，（1）中序遍历左子树；（2）访问根节点；（3）中序遍历右子树。
递归算法如下：
void InOrder(BiTree T) {
if(T != NULL) {
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
非递归算法：
void InOrder(BiTree T) {
InitStack(S);
BiTree p = T;
while(p || ! IsEmpty(S)) {
if(p) {
Push(S, p);
p = p->lchild;
}
else {
Pop(S, p);
visit(p);
p = p->rchild;
}
}
}
LRN（后序遍历， PostOrder）
若二叉树为空，则什么也不做；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根节点。
递归算法如下：
void PostOrder(BiTree T) {
if(T != NULL) {
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
层次遍历
进行层次遍历，需要借助一个队列。层次遍历的思想如下，①首先将二叉树根节点入队；②队列非空，则队头节点出队，访问该节点，若它有左孩子，则将其左孩子入队；若它有右孩子，则将其右孩子入队；③重复②，直到队列为空。
算法如下：
void LevelOrder(BiTree T) {
InitQueue(Q);
BiTree p;
EnQueue(Q, T);
while(! IsEmpty(Q)) {
DeQueue(Q, p);
visit(p);
if(p->lchild != NULL)
EnQueue(Q, p->lchild);
if(p->rchild != NULL)
EnQueue(Q, p->rchild);
}
}
由遍历序列构造二叉树
以下几个例子都采用\(Leetcode\)来展示。
先序、中序构造二叉树
class Solution {
private:
unordered_map<int, int> index;
public:
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
// 前序遍历中的第一个节点就是根节点
int preorder_root = preorder_left;
// 在中序遍历中定位根节点
int inorder_root = index[preorder[preorder_root]];
// 先把根节点建立出来
TreeNode* root = new TreeNode(preorder[preorder_root]);
// 得到左子树中的节点数目
int size_left_subtree = inorder_root - inorder_left;
// 递归地构造左子树，并连接到根节点
// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
// 递归地构造右子树，并连接到根节点
// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 构造哈希映射，帮助我们快速定位根节点
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};
中序、后序构造二叉树
class Solution {
int post_idx;
unordered_map<int, int> idx_map;
public:
TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
// 如果这里没有节点构造二叉树了，就结束
if (in_left > in_right) {
return nullptr;
}
// 选择 post_idx 位置的元素作为当前子树根节点
int root_val = postorder[post_idx];
TreeNode* root = new TreeNode(root_val);
// 根据 root 所在位置分成左右两棵子树
int index = idx_map[root_val];
// 下标减一
post_idx--;
// 构造右子树
root->right = helper(index + 1, in_right, inorder, postorder);
// 构造左子树
root->left = helper(in_left, index - 1, inorder, postorder);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
// 从后序遍历的最后一个元素开始
post_idx = (int)postorder.size() - 1;
// 建立（元素，下标）键值对的哈希表
int idx = 0;
for (auto& val : inorder) {
idx_map[val] = idx++;
}
return helper(0, (int)inorder.size() - 1, inorder, postorder);
}
};
中序、层序构造二叉树
BiTree Create(DataType LEVEL[], int l1, int h1, DataType LDR[], int l2, int h2) {
if (l2 > h2)
return NULL;
else {
BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
int mark = 0; //标识器
int i, j;//分别指向LEVEL和LDR中数组的元素
//寻找根，LEVEL中第一个与LDR中元素匹配的即为根结点
for (i = l1; i <= h1; ++ i) {
for (j = l2; j <= h2; ++ j)
if (LEVEL[i] == LDR[j]) {
mark = 1;
break;
}
}
if (mark == 1)
break;
}
T->data = LEVEL[i]; //根节点数据域
T->lchild = Create(LEVEL, l1 + 1, h1, LDR, l2, j - 1);
T->rchild = Create(LEVEL, l1 + 1, h1, LDR, j + 1, h2);
return T;
}
}
前序、后序遍历构造二叉树*
不唯一！
class Solution {
public:
TreeNode *constructFromPrePost(vector<int> &preorder, vector<int> &postorder) {
int n = preorder.size();
unordered_map<int, int> postMap;
for (int i = 0; i < n; i++) {
postMap[postorder[i]] = i;
}
function<TreeNode *(int, int, int, int)> dfs = [&](int preLeft, int preRight, int postLeft, int postRight) -> TreeNode * {
if (preLeft > preRight) {
return nullptr;
}
int leftCount = 0;
if (preLeft < preRight) {
leftCount = postMap[preorder[preLeft + 1]] - postLeft + 1;
}
return new TreeNode(preorder[preLeft],
dfs(preLeft + 1, preLeft + leftCount, postLeft, postLeft + leftCount - 1),
dfs(preLeft + leftCount + 1, preRight, postLeft + leftCount, postRight - 1));
};
return dfs(0, n - 1, 0, n - 1);
}
};
线索二叉树
规定：若无左子树，令\(lchild\)指向其前驱节点；若无右子树，令\(rchild\)指向其后继节点；此外还需要增加两个标志域，以标识指针域指向左（右）孩子或前驱（后继）。
其中标志域的含义如下：
线索二叉树的存储结构如下：
typedef struct ThreadNode {
inr data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;
}ThreadNode, *ThreadTree;
中序线索二叉树的构造
通过中序遍历对二叉树线索化的递归算法如下：
void InThread(ThreadTree &p, ThreadTree &pre) {
if(p != NULL) {
InThread(p->lchild, pre);
if(p->lchild == NULL) {
p->lchild = pre;
p->ltag = 1;
}
if(pre != NULL && pre->rchild == NULL) {
pre->rchild = p;
pre->tag = 1;
}
pre = p;
TnThread(p->rchild, pre);
}
}
通过中序遍历建立中序线索二叉树的主过程：
void CreateInThread(ThreadTree T) {
ThreadTree pre = NULL;
if(T != NULL) {
InThread(T, pre);
pre->rchild = NULL;
pre->rtag = 1;
}
}
中序线索二叉树的遍历
求中序线索二叉树的中序序列下的第一个节点：
ThreadNode *Firstnode(ThreadNode *p) {
while(p->ltag == 0)
p = p->lchild;
return p;
}
求中序线索二叉树中节点p在中序序列下的后继：
ThreadNode *NextNode(ThreadNode *p) {
if(p->rtag == 0)
return Firstnode(p->rchild);
else
return p->rchild;
}
不含头节点的中序线索二叉树的中序遍历算法：
void Inorder(ThreadNode *T) {
for(ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p))
visit(p);
}