5.1 树的基本概念

5.1.1 树的定义

树的定义和基本术语.pdf

树： $n$ 个结点的有限集（树是一种递归的数据结构，适合于表示具有层次的数据结构）。是递归定义的。当 $n = 0$ 时，称为**空树
非空树的特性：有且只有一个根结点
根结点：只有子结点没有父结点的结点。除了根结点外，树任何结点都有且仅有一个前驱。
分支结点：有子结点也有父结点的结点；
叶子结点：没有子结点只有父结点的结点。
子树：当 $n > 1$ 时，其余结点可分为 $m$ 个互不相交的有限集合，每个集合本身又是一棵树，其就是根结点的子树。

5.1.2 基本术语

结点之间的关系描述
- 双亲：靠近根结点且最靠近该结点的结点。
- 孩子：与双亲的定义相对应
- 祖先：根结点到结点的路径上的任意结点都是该结点的祖先。
- 子孙：与祖先的定义相对应
- 兄弟：有共同双亲结点的结点。
- 堂兄弟：双亲结点在同一层的两个结点，如果不是兄弟，则互为堂兄弟。
结点、树的属性描述
- 结点的度：一个结点的孩子（分支）个数。
- 树的度：树中所有结点度数的最大值。
- 结点的层次（深度）：从上往下数，默认从1开始。
- 结点的高度：从下往上数。
- 树的高度（深度）：树中结点的最大层次。
- 两结点之间的路径：由两个结点之间所经过的结点序列构成。
- 两结点之间的路径长度：路径上所经过的边的个数。
- 树的路径长度：指树根到每个结点的路径长的总和，根到每个结点的路径长度的最大值是树的高。
有序树vs无序树
- 有序树：逻辑上看，数中结点的各子树从左至右是有次序的，不能互换
- 无序树：逻辑上看，数中结点的各子树从左至右是无次序的，可以互换
森林： $m (m ⩾ 0)$ 棵互不相交的树的集合

5.1.3 树的性质

树的性质.pdf

常用于求解树结点与度之间的关系的性质

总结点数 $= n_{0} + n_{1} + n_{2} + \dots + n_{m}$ ，其中 $n_{i}$ 是度为 $i$ 的结点数
总度数 $= n_{1} + 2 n_{2} + \dots + m n_{m}$
结点数 $n$ = 总度数 $+ 1$ ^[提示：1 表示根结点]

度为 $m$ 的树、 $m$ 叉树的区别

度为 $m$ 的树	$m$ 叉树
树的度： $m$ 为各结点的度的最大值	$m$ 叉树：每个结点最多只能有 $m$ 个孩子的树
任意结点的度 $⩽ m$ 至少有一个结点度 $= m$	任意结点的度 $⩽ m$ 允许所有结点的度 $< m$
一定是非空树，至少有 $m + 1$ 个结点	可以是空树
第 $i$ 层至多有 $m^{i - 1}$ 个结点	第 $i$ 层至多有 $m^{i - 1}$ 个结点
至多有 $\frac{m ^{h} - 1}{m - 1}$ 个结点，至少有 $h + m - 1$ 个结点	至多有 $\frac{m ^{h} - 1}{m - 1}$ 个结点，至少有 $h$ 个结点
最小高度为 $⌈ lo g_{m} [(n (m - 1) + 1)]⌉$ ，最大高度为 $n - m + 1$	最小高度为 $⌈ lo g_{m} [(n (m - 1) + 1)]⌉$ ^[此处可以理解为 $\frac{m ^{h - 1} - 1}{m - 1} < n ⩽ \frac{m ^{h} - 1}{m - 1}$ ]

5.1.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

5.2 二叉树的概念

5.2.1 二叉树的定义与特性

二叉树的定义和基本术语.pdf

二叉树是 $n$ 个结点的有限集合：或者为空二叉树，或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树
二叉树有左右之分，次序不能颠倒

二叉树常考性质

二叉树的性质.pdf

设非空二叉树中度为0、1和2的结点个数分别为 $n_{0}, n_{1}$ 和 $n_{2}$ ，则 $n_{0} = n_{2} + 1$ ，所以 $n_{0} + n_{2}$ 一定是奇数 ^[提示：假设树中结点总数为 $n$ ，则有： $n = n_{0} + n_{1} + n_{2}$ 且 $n = n_{1} + 2 n_{2} + 1$ ] 考前记一记
具有 $n$ 个结点的完全二叉树的高度 $h$ 为 $⌈ lo g_{2} (n + 1) ⌉$ 或 $⌊ lo g_{2} n ⌋ + 1$ 。可用来推导第 $i$ 个结点所在层次 ^[提示：结点总数满足 $\frac{2 ^{h - 1} - 1}{2 - 1} < n ⩽ \frac{2 ^{h} - 1}{2 - 1}$ ；或根据完全二叉树的定义有 $2^{h - 1} ⩽ n < 2^{h}$ ] 考前记一记
对于完全二叉树，可以由结点数 $n$ 推出度为0、1和2的结点个数为 $n_{0}$ 、 $n_{1}$ 和 $n_{2}$ ，则 $n_{1} = 0$ 或 $1$ 。
含有 $n$ 个结点的二叉树最多有 $\frac{C _{2 n}^{n}}{n + 1} = \frac{( 2 n )!}{n ! ( n + 1 )!}$ ，即：卡特兰数

5.2.2 几种特殊的二叉树

满二叉树（形态特殊）：高度为 $h$ ，且含有 $2^{h} - 1$ 个结点

只有最后一层有叶子结点，不存在度为1的结点
从层序为1开始编号，结点 $i$ 的左孩子为 $2 i$ ，右孩子为 $2 i + 1$ ，结点 $i$ 的父结点为 $⌊ i /2 ⌋$ （如果有的话）

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=8em/2, level distance=3em},
	level 3/.style={sibling distance=8em/4, level distance=3em},
	]
	\node(1) {1}
		child {node (2) {2}
			child {node (4) {4}
				child {node[fill=green!20] (8) {8}}
				child {node[fill=green!20] (9) {9}}
			}
			child {node (5) {5}
				child {node[fill=green!20] (10) {10}}
				child {node[fill=green!20] (11) {11}}
			}
		}
        child {node (3) {3}
			child {node (6) {6}
				child {node[fill=green!20] (12) {12}}
				child {node[fill=green!20] (13) {13}}
			}
			child {node (7) {7}
				child {node[fill=green!20] (14) {14}}
				child {node[fill=green!20] (15) {15}}
			}
		};
	\end{tikzpicture}
\end{document}

完全二叉树（形态特殊）：当且仅当其每个结点都与高度为 $h$ 的满二叉树中编号为 $1 \sim n$ 的结点一一对应时，称为完全二叉树（即：在满二叉树的基础上，去掉了末端的数个结点）

只有最后两层可能有叶子结点，最多只有一个度为1的结点
从层序为1开始编号，结点 $i$ 的左孩子为 $2 i$ ，右孩子为 $2 i + 1$ ，结点 $i$ 的父结点为 $⌊ i /2 ⌋$ （如果有的话）
- $i ⩽ ⌊ n /2 ⌋$ 为分支结点， $i > ⌊ n /2 ⌋$ 为叶子结点考前记一记

\begin{document}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=8em/2, level distance=3em},
	level 3/.style={sibling distance=8em/4, level distance=3em},
	]
	\node(1) {1}
		child {node (2) {2}
			child {node (4) {4}
				child {node[fill=green!20] (8) {8}}
				child {node[fill=green!20] (9) {9}}
			}
			child {node (5) {5}
				child {node[fill=green!20] (10) {10}}
				child {node[fill=green!20] (11) {11}}
			}
		}
        child {node (3) {3}
			child {node (6) {6}
				child {node[fill=green!20, xshift=-2em] (12) {12}}
			}
			child {node[fill=green!20] (7) {7}}
		};
	\end{tikzpicture}
\end{document}

二叉排序树（功能特殊）

一棵空二叉树，或者是具有如下性质的二叉树：
- 左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于根结点的关键字；左子树和右子树又各自是一棵二叉排序树
可用于元素的排序、搜索

平衡二叉树（功能特殊）

树上的任一结点的左子树和右子树的深度之差不超过1
平衡二叉树能有更高的搜索效率

5.2.3 二叉树的存储结构

二叉树的存储结构.pdf

二叉树的顺序存储

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来；

定义

#define MaxSize 100
 
struct TreeNode{
	ElemType value; //结点中的数据元素
	bool isEmpty;	//结点是否为空
} TreeNode;

初始化：将所有结点标记为空

void InitSqBiTree (TreeNode t[], int length){
	for (int i=0; i<MaxSize; i++){
		t[i].isEmpty = true;
	}
}
 
int main(){
	TreeNode t[MaxSize];
	InitSqBiTree(t, 100);
	//...
}

判空：判断下标为 index 的结点是否为空

bool isEmpty(TreeNode t[], int length, int index){
	if (index >= length || index < 1) return true;//下标越界
	return t[index].isEmpty;
}

访问父结点、左孩子结点、右孩子结点

//找到下标为index的结点的左孩子，并返回其下标。若结点没有左孩子则返回-1
int getlChild(TreeNode t[], int length, int index){
	int lChild = index * 2;
	if (isEmpty(t[], length, lChild)) return -1;//左孩子为空
	return lChild;
}
 
//找到下标为index的结点的右孩子，并返回其下标。若结点没有右孩子则返回-1
int getrChild(TreeNode t[], int length, int index){
	int rChild = index * 2 + 1;
	if (isEmpty(t[], length, rChild)) return -1;//右孩子为空
	return rChild;
}
 
//找到下标为index的结点的父结点，并返回其下标。若结点没有父结点则返回-1
int getlChild(TreeNode t[], int length, int index){
	if (index == 1) return -1;
	int parent = index / 2;
	if (isEmpty(t[], length, parent)) return -1;//根结点没有父结点
	return parent;
}

先序遍历：从下标为index的结点开始先序遍历

void PreOrderSqTree (TreeNode *t, int length, int index) {
	if (isEmpty(t, length, index)) return;
	visitNode(t[index]);//访问结点
	PreOrderSqTree(t, length, getlChild(t, length, index));
	PreOrderSqTree(t, length, getrChild(t, length, index));
}

中序遍历：从下标为index的结点开始中序遍历

void InOrderSqTree (TreeNode *t, int length, int index) {
	if (isEmpty(t, length, index)) return;
	InOrderSqTree(t, length, getlChild(t, length, index));
	visitNode(t[index]);//访问结点
	InOrderSqTree(t, length, getrChild(t, length, index));
}

后序遍历：从下标为index的结点开始后序遍历

void PostOrderSqTree (TreeNode *t, int length, int index) {
	if (isEmpty(t, length, index)) return;
	PostOrderSqTree(t, length, getlChild(t, length, index));
	PostOrderSqTree(t, length, getrChild(t, length, index));
	visitNode(t[index]);//访问结点
}

\begin{document}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=8em/2, level distance=3em},
	level 3/.style={sibling distance=8em/4, level distance=3em},
	]
	\node(1) {1}
		child {node (2) {2}
			child {node (4) {4}
				child {node[fill=green!20] (8) {8}}
				child {node[fill=green!20] (9) {9}}
			}
			child {node (5) {5}
				child {node[fill=green!20] (10) {10}}
				child {node[fill=green!20] (11) {11}}
			}
		}
        child {node (3) {3}
			child {node (6) {6}
				child {node[fill=green!20, xshift=-2em] (12) {12}}
			}
			child {node[fill=green!20] (7) {7}}
		};
	\end{tikzpicture}
\end{document}

\begin{document}
	\begin{tikzpicture}[scale=1.8, line width=1.5pt]
	\tikzstyle{every node}=[font=\huge, minimum width=4em, minimum height=4em]
		\foreach \i in {0,1,...,15} {
			\node[draw=black, very thick, rectangle, fill=gray!20] at (\i,0) {\^{}};
			\node at (\i,-1) {t[\i]};
		}
 
		\foreach \i in {1,2,...,6} {
			\node[draw=black, very thick, circle, fill=white, minimum size=3em] at (\i,0) {\i};
			\node at (\i,-1) {t[\i]};
		}
		\foreach \i in {7,8,...,12} {
			\node[draw=black, very thick, circle, fill=green!20, minimum size=3em] at (\i,0) {\i};
			\node at (\i,-1) {t[\i]};
		}
 
	\end{tikzpicture}
\end{document}

基本操作，以数组下标从 $1$ 开始为例：

i 的左孩子编号： $2 i$
i 的右孩子编号： $2 i + 1$
i 的父结点编号： $⌊ i /2 ⌋$
i 所在的层次： $⌈ lo g_{2} (i + 1) ⌉$ 或 $⌊ lo g_{2} i ⌋ + 1$

若完全二叉树中共有 $n$ 个结点（非完全二叉树只能使用isEmpty判断）

判断 i 是否有左孩子： $2 i ⩽ n$
判断 i 是否有右孩子： $2 i + 1 ⩽ n$
判断 i 是否是叶子/分支结点： $i > ⌊ n /2 ⌋$

最坏情况：高度为 $h$ 且只有 $h$ 个结点的单支树（所有结点只有右孩子），也至少需要 $2^{h} - 1$ 个存储单元；

结论：二叉树的顺序存储结构，只适合存储完全二叉树和满二叉树

二叉树的链式存储

$n$ 个结点→ $2 n$ 个指针域，其中有 $n - 1$ 个指针（除根结点），所以一共有 $n + 1$ 个空链域，可以用于构造线索二叉树

二叉树的链式存储结构体算法题

// 二叉链表
typedef struct BiTNode{
	ElemType data;	//数据域
	struct BiTNode *lChild, *rChild;	//左、右孩子指针
}BiTNode, *BiTree;

// 定义一棵空树
BiTree root = NULL;
 
// 插入根结点
root = (BiTree) malloc (sizeof(BiTNode));
root -> data = {1};	//根结点存入数据1
root -> lChild = NULL;
root -> rChild = NULL;
 
// 插入新结点
BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
p -> data = {2};	//根结点存入数据2
p -> lChild = NULL;
p -> rChild = NULL;
root -> lChild = p;	//作为根结点的左孩子

寻找指定结点 $p$ 的左/右孩子较为方便
寻找指定结点 $p$ 的父结点时，只能从根结点开始遍历，所以也可以使用三叉链表，即再结构体中再定义一个指针，指向父结点

// 三叉链表
typedef struct BiTnode{
	ElemType data;					// 数据域
	struct BiTNode *lChild, *rChild;// 左、右孩子指针
	struct BiTNode *parent;			// 父结点指针
}BiTNode, *BiTree;

5.2.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

5.3 二叉树的遍历和线索二叉树

5.3.1 二叉树的遍历

二叉树的先中后序遍历.pdf

二叉树的遍历是指按照某种顺序访问树的每一个结点，使得每个结点均被访问到，而且仅访问一次。这里的访问是指对结点进行各种处理的统称，包括对结点数据进行运算、修改和打印信息等
对二叉树进行遍历是为了对二叉树进行某些操作或者获取树中的某些信息。
分支结点逐层展开法：如果是一个结点是分支结点而不是叶子结点的话，就嵌套递归地按照特定的遍历序列把它展开到下一级
对算术表达式的“分析树”进行遍历，可以得到其表达式：先序遍历对应前缀表达式，中序遍历对应中缀表达式，后序遍历对应后缀表达式

二叉树的先序遍历

先序遍历：根左右 NLR

LeetCode144. 二叉树的前序遍历

先序遍历规则

若二叉树为空，不用操作

若二叉树非空（左右子树也可能是空二叉树）：

访问根结点

先序遍历左子树

先序遍历右子树

递归实现，时间复杂度，空间复杂度算法题

void preOrder(BiTree root){
	if (root == NULL) return;
 
	visit(root);			//访问根结点
	preOrder(root->lChild);	//递归遍历左子树
	preOrder(root->rChild);	//递归遍历右子树
}

迭代实现，时间复杂度 $O (n)$ ，空间复杂度 $O (lo g_{2} n) \sim O (n)$

void preOrder(TreeNode* root){
	if (root == NULL) return;
 
	stack <TreeNode*> stk;	// 等价于递归栈
	TreeNode* node = root;
	while(!stk.empty() || node!=NULL) {
		while (node != NULL) {	// 找到最左下方的结点
			visit(node);		// 边找边访问根结点
			stk.push(node);
			node = node->left;
		}
		node = stk.top();
		stk.pop();
		node = node->right;
	}
}

脑补空结点，从根结点出发，画一条路：

如果左边还有没走的路，优先往左边走；
走到路的尽头（空结点）就往回走；
如果左边没有路就往右边走；
如果左右边都没有路就往上面走；
先序遍历：每一个结点都被路过三次，第一次路过时访问结点

二叉树的中序遍历

中序遍历：左根右 LNR

LeetCode94. 二叉树的中序遍历

中序遍历规则

若二叉树为空，不用操作

若二叉树非空：

先序遍历左子树

访问根结点

先序遍历右子树

递归实现，时间复杂度 $O (n)$ ，空间复杂度 $O (lo g_{2} n) \sim O (n)$ 算法题

void inOrder(BiTree root) {
	if (root == NULL) return;
 
	inOrder(root->lChild);	//递归遍历左子树
	visit(root);			//访问根结点
	inOrder(root->rChild);	//递归遍历右子树
}

迭代实现，时间复杂度 $O (n)$ ，空间复杂度 $O (lo g_{2} n) \sim O (n)$

void inOrder(TreeNode* root) {
	stack<TreeNode*> stk;
	while (root != NULL || !stk.empty()) {
		while (root != NULL) {	// 找到最左下方的结点
			stk.push(root);
			root = root->left;
		}
		root = stk.top();
		stk.pop();
		visit(root);					// 左子树为空，访问根结点
		root = root->right;
	}
}

脑补空结点，从根结点出发，画一条路：

如果左边还有没走的路，优先往左边走；
走到路的尽头（空结点）就往回走；
如果左边没有路就往右边走；
如果左右边都没有路就往上面走；
中序遍历：每一个结点都被路过三次，第二次路过时访问结点

二叉树的后序遍历

后续遍历：左右根 LRN

LeetCode145. 二叉树的后序遍历

后续遍历规则

若二叉树为空，不用操作

若二叉树非空：

先序遍历左子树

先序遍历右子树

访问根结点

递归实现，时间复杂度 $O (n)$ ，空间复杂度 $O (lo g_{2} n) \sim O (n)$ 算法题

void postOrder(BiTree root){
	if (root == NULL) return;
 
	postOrder(root->lChild);	//递归遍历左子树
	postOrder(root->rChild);	//递归遍历右子树
	visit(root);				//访问根结点
}

迭代实现，时间复杂度 $O (n)$ ，空间复杂度 $O (lo g_{2} n) \sim O (n)$

// 【注意】后序遍历中需要记录前一个访问的结点
 
void postorderTraversal(TreeNode *root) {
	if (root == NULL) return res;
 
	stack<TreeNode *> stk;
	TreeNode *prev = NULL;
	while (root != NULL || !stk.empty()) {
		while (root != NULL) {	// 找到最左下方的结点
			stk.push(root);
			root = root->left;
		}
		root = stk.top();
		stk.pop();
		if (root->right == NULL || root->right == prev) {// 右子树为空或者已经被访问过，访问根结点
			visit(root);
			prev = root;
			root = NULL;
		} else {	// 右子树非空，在右子树中找到最左下方的结点
			stk.push(root);
			root = root->right;
		}
	}
}

脑补空结点，从根结点出发，画一条路：

如果左边还有没走的路，优先往左边走；
走到路的尽头（空结点）就往回走；
如果左边没有路就往右边走；
如果左右边都没有路就往上面走；
后序遍历：每一个结点都被路过三次，第三次路过时访问结点

二叉树的层序遍历

LeetCode102. 二叉树的层序遍历

二叉树的层次遍历.pdf

算法思想：

初始化一个辅助队列
根结点入队
若队列非空，则队头结点出队，访问该结点，依次将其左、右孩子插入队尾（如果有的话）
重复以上操作直至队列为空

void levelOrder(TreeNode* root) {
	if (root == NULL) return;
 
	queue <TreeNode*> q;	// 辅助队列
	q.push(root);
	while (!q.empty()) {
		int currentLevelSize = q.size();	// 当前层元素个数
		// 一次性出队一层结点
		for (int i = 1; i <= currentLevelSize; ++i) {
			TreeNode* node = q.front();
			q.pop();
			visit(node);
			if (node->left) q.push(node->left);		// 左孩子入队
			if (node->right) q.push(node->right);	// 右孩子入队
		}
	}
}

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$

由遍历序列构造二叉树

由遍历序列构造二叉树.pdf

如果只给出一棵二叉树的前/中/后/层序遍历序列的一种，并不能唯一确定一棵二叉树

前/后/层序序列的两两组合也无法唯一确定一棵二叉树

LeetCode105. 从前序与中序遍历序列构造二叉树

LeetCode106. 从中序与后序遍历序列构造二叉树

先序序列（根左右） + 中序序列（左根右）：先序序列的第一个结点一定是二叉树的根结点，该结点将中序序列分为两个子序列，分别对应根结点的左子树和右子树。再在子序列中递归拆分，即可得到完整的二叉树。
后序序列（左右根） + 中序序列（左根右）：后序序列的最后一个一个结点一定是二叉树的根结点，该结点将中序序列分为两个子序列，分别对应根结点的左子树和右子树。再在子序列中递归拆分，即可得到完整的二叉树。
层序序列（根左根右根） + 中序序列（左根右）：层序序列中各层的根结点依次出现

关键点：找到树的根结点，并根据中序序列划分左右子树，再找到左右子树根结点

二叉树遍历的应用

查找结点

BiTNode* FindNode(BiTNode* b, ElemType x){
	BiTNode* p;
	if(b==NULL) return NULL;
 
	if(b->data == x) {
		return b;
	} else{
		p=FindNode(b->lChild, x);			// 在左孩子中递归寻找
		if(p!=NULL) return p;
		else return FindNode(b->rChild ,x);	// 在右孩子中递归寻找
	}
}

求树的深度

LeetCode104. 二叉树的最大深度

int treeDepth(BiTree T){
	if (T == NULL) return 0;
 
	int l = treeDepth(T->lChild);	// 左子树深度
	int r = treeDepth(T->rChild);	// 右子树深度
	return l>r ? l+1 : r+1;			// 树的深度 = Max(左子树深度，右子树深度)+1
}

统计结点数量

int countNode(BiTree T){
	if (T == NULL) return 0;
	else return countNode(T->lChild) + countNode(T->rChild) + 1;
}

寻找祖先结点

对于后序遍历而言，一定能通过子孙结点找到祖先结点。考前记一记

5.3.2 线索二叉树

线索二叉树的概念.pdf

线索二叉树的概念与作用

普通二叉树存在的问题：

进行遍历时，必须从根结点出发
寻找指定结点在遍历序列中的前驱/后继时，只能从头遍历

线索二叉树

$n$ 个结点的二叉树，有 $n + 1$ 个空链域，可用来记录前驱、后继的信息
实现思路：
- 若无左子树，令lChild指向其前驱结点；若无右子树，令rChild指向其后继结点
- 遍历序列中的第一个结点的前驱指向 NULL，最后一个结点的后继指向 NULL

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=3em},
	level 2/.style={sibling distance=8em/1.5, level distance=3em},
	level 3/.style={sibling distance=8em/4, level distance=3em},
	]
	\node(A) {$A$}
		child {node (B) {$B$}
			child {node (D) {$D$}
				child {node[xshift=2em] (G) {$G$}}
			}
			child {node (E) {$E$}}
		}
        child {node (C) {$C$}
			child {node[xshift=-4em] (F) {$F$}}
		};
 
	\node[font=\small, draw=none] (nullC) [right=of C, yshift=-2em] {NULL};
	\node[font=\small, draw=none] (nullD) [left=of D, yshift=-2em] {NULL};
 
	\draw[-latex, dashed, orange] (D) to [in=0, out=-120](nullD);
	\draw[-latex, dashed, orange] (G) to [in=-90, out=-120](D);
	\draw[-latex, dashed, purple] (G) to [in=-100, out=-60](B);
	\draw[-latex, dashed, orange] (E) to [in=-80, out=-120](B);
	\draw[-latex, dashed, purple] (E) to [in=-100, out=-60](A);
	\draw[-latex, dashed, orange] (F) to [in=-80, out=-120](A);
	\draw[-latex, dashed, purple] (F) to [in=-100, out=-60](C);
	\draw[-latex, dashed, purple] (C) to [in=-180, out=-60](nullC);
	\end{tikzpicture}
\end{document}

线索二叉树的存储结构

先序线索二叉树——线索指向先序前驱、先序后继
中序线索二叉树——线索指向中序前驱、中序后继
后序线索二叉树——线索指向后序前驱、后序后继

//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lChild, *rChild;	// 左、右孩子指针
	int ltag, rtag;						// 左、右线索标志
}ThreadNode, *ThreadTree;

为了区分 lChild 和 rChild 指向的是左右孩子还是前驱或后继结点，需要增加 tag 为作为标识：

tag == 0：指针指向结点的孩子
tag == 1：指针指向结点的前驱/后继

二叉树的线索化

二叉树的线索化.pdf

土办法寻找中序前驱

//个人理解：对整个二叉树重新进行一次中序遍历，并设置两个指针：当前结点q，前驱结点pre
//前驱结点pre始终比q结点晚一个位置，故pre指向当前访问结点的前驱结点
 
void findPre(BiTree T){
	if(T!=null){
		findPre(T->lChild);	//递归遍历左子树
		visit(T);			//访问根结点
		findPre(T->rChild);	//递归遍历右子树
	}
}
//访问结点q
void visit(BiTNode *q){
	if(q == p)	//当前访问结点刚好是结点p
		final = pre;	// 找到p的前驱（也就是上一次的q）
	else	// 将pre指向当前访问的结点，之后继续遍历
		pre = q;
}
//辅助全局变量，用于查找结点p的前驱
BiTNode *p;
BiTNode *pre = null;
BiTNode *final = null;

中序线索化

注意单独处理最后一个结点

//个人理解：类似土办法找中序前驱的方法来线索化
 
//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lChild, *rChild;
	int ltag, rtag;	// 左、右线索标志
}ThreadNode, *ThreadTree;
 
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
//中序遍历二叉树，访问结点时对其线索化
void InThread(ThreadTree &root, ThreadNode &pre){
	if(root == NULL) return;
	InThread(root->lChild, pre);//中序遍历左子树
	visit(root, pre);			//访问根结点
	InThread(root->rChild, pre);//中序遍历右子树
}
void visit(ThreadNode &node, ThreadNode &pre){
	if(node->lChid == NULL){//左子树为空，建立前驱线索
		node->lChild = pre;	//前驱结点
		node->ltag = 1;		//置tag值为1
	}
 
	if(pre!=NULL && pre->rChild = NULL){//前驱结点不为空且前驱结点的rChild为空
		pre->rChild = node;	//建立前驱结点的后继线索
		pre->rtag = 1;
	}
	pre = node;
}
 
//中序线索化二叉树T
void CreateInThread(ThreadTree T){
	ThreadTree pre = NULL;		//pre初始为NULL
	if(T != NULL){	//非空二叉树才能进行线索化
		InThread(T, pre);
		//为最后一个结点的后继置为NULL
		pre->rChild == NULL
		pre->rtag = 1;
	}
}

先序线索化

注意单独处理最后一个结点
注意转圈问题：当 ltag == 0 时，才能对左子树先序线索化。例如下图中当遍历到 $D$ 结点时，将 $D$ 结点的 lChild 指向 $B$ 结点建立了前驱关系。在尝试访问左子树时 lChild!=NULL，如果没有判断 ltag 的值，又会重复访问 $B$ 结点

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=8em/1.5, level distance=3em},
	level 3/.style={sibling distance=8em/4, level distance=3em},
	]
	\node(A) {$A$}
		child {node (B) {$B$}
			child {node (D) {$D$}
				child {node[xshift=2em] (G) {$G$}}
			}
			child {node (E) {$E$}}
		}
        child {node (C) {$C$}
			child {node[xshift=-4em] (F) {$F$}}
		};
 
	% 创建新结点并指定它们相对于已知结点的位置和距离
	\node[font=\Large, draw=none] (pre) [left=of B] {pre};
	\node[font=\Large, draw=none] (q) [left=of D] {q};
	\draw[-latex, thick] (pre) -- (B);
	\draw[-latex, thick] (q) -- (D);
 
	\draw[-latex, dashed, orange] (D) to [in=-160, out=180](B);
	\end{tikzpicture}
\end{document}

typedef struct ThreadNode{
	int data;
	struct ThreadNode *lChild, *rChild;
	int ltag, rtag;	// 左、右线索标志
}ThreadNode, *ThreadTree;
 
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
 
//先序遍历二叉树，访问结点时对其线索化
void PreThread(ThreadTree T){
	if(T == NULL) return;
 
	visit(T);
	//当子结点的左子树为空时，与其父结点建立了前驱关系
	//这里将访问子结点的左子树，如果不进行判断，将会重新访问父结点
	if(T->ltag == 0)	//lChild不是前驱线索（解决转圈问题）
		PreThread(T->lChild);
	PreThread(T->rChild);
}
 
void visit(ThreadNode *q){
	if(q->lchid = NULL){	//左子树为空，建立前驱线索
		q->lChild = pre;
		q->ltag = 1;
	}
 
	if(pre!=NULL && pre->rChild = NULL){
		pre->rChild = q;	//建立前驱结点的后继线索
		pre->rtag = 1;
	}
	pre = q;
}
 
//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
	pre = NULL;	//pre初始为NULL
	if(T!=NULL){	//非空二叉树才能进行线索化
		PreThread(T);	//先序线索化二叉树
		if(pre->rChild == NULL)
			pre->rtag=1;	//处理遍历的最后一个结点
	}
}

后序线索化

注意单独处理最后一个结点

typedef struct ThreadNode{
	int data;
	struct ThreadNode *lChild, *rChild;
	int ltag, rtag;	// 左、右线索标志
}ThreadNode, *ThreadTree;
 
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
 
//后序遍历二叉树，访问结点时对其线索化
void PostThread(ThreadTree T){
	if(T == NULL) return;
 
	PostThread(T->lChild);
	PostThread(T->rChild);
	visit(T);	//访问根结点
}
 
void visit(ThreadNode *q){
	if(q->lchid = NULL){	//左子树为空，建立前驱线索
		q->lChild = pre;
		q->ltag = 1;
	}
 
	if(pre!=NULL && pre->rChild = NULL){
		pre->rChild = q;	//建立前驱结点的后继线索
		pre->rtag = 1;
	}
	pre = q;
}
 
//后序线索化二叉树T
void CreatePostThread(ThreadTree T){
	pre = NULL;	//pre初始为NULL
	if(T!=NULL){	//非空二叉树才能进行线索化
		PostThread(T);	//后序线索化二叉树
		if(pre->rChild == NULL)
			pre->rtag=1;	//处理遍历的最后一个结点
	}
}

线索二叉树中找前驱、后继

在线索二叉树中找前驱后继.pdf

	中序线索二叉树	先序线索二叉树	后续线索二叉树
找前驱	√	×	√
找后继	√	√	×

中序线索二叉树找中序后继

在中序线索二叉树中找到指定结点 *p 的中序后继 next：

若 p->rtag == 1： p->rChild；
若 p->rtag == 0，则 p 必有右孩子：右子树中最左下结点（左子树中最先被访问的结点）——左根右 / 左根 (左根右)

//个人理解：从给定结点开始，实现对中序线索二叉树的中序遍历
 
//1. 找到以P为根的子树中，第一个被中序遍历的结点
//即循环遍历，找到最左下的结点（不一定是叶结点，也可能是只有右孩子没有左孩子的结点）
ThreadNode *Firstnode(ThreadNode *p){
	while(p->ltag == 0)
		p = p->lChild;
	return p;
}
 
//2. 在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
	//右子树最左下结点
	if(p->rtag == 0)
		return Firstnode(p->rChild);
	else
		return p->rChild;		// rtag==1，直接返回后继线索
}
 
//3. 对中序线索二叉树进行中序遍历
void Inorder(ThreadNode *T){	// T为根结点指针
	for(ThreadNode *p = Firstnode(T); p!=NULL; p = Nextnode(p))
		visit(p);
}

时间复杂度 = $O (1)$

中序线索二叉树找中序前驱

在中序线索二叉树中找到指定结点 *p 的中序前驱 pre：

若 p->ltag == 1： p->lChild；
若 p->ltag == 0，则 p 必有左孩子：左子树中最右下结点（左子树中最后被访问的结点）——左根右/（左根右）根右

//个人理解：从给定结点开始，实现对中序线索二叉树的逆向中序遍历
 
//1. 找到以P为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
	//循环找到最右下的结点（不一定是叶结点）
	while(p->rtag == 0)
		p = p->rChild;
	return p;
}
 
//2. 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
	if(p->ltag == 0)
		return Lastnode(p->lChild);//左子树最右下结点
	else
		return p->lChild; //ltag==1，直接返回前驱线索
}
 
//3. 对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){            //T为根结点指针
	for(ThreadNode *p = Lastnode(T); p!=NULL; p = Prenode(p))
		visit(p);
}

先序线索二叉树找先序后继

在先序线索二叉树中找到指定结点 *p 的先序后继 next：

若 p->rtag == 1： p->rChild
若 p->rtag == 0，则 p 必有右孩子（左孩子不知道）
- case1：若 p 有左孩子：p 的左孩子——根左右 / 根 (根左右) 右，即左子树中最先被访问的结点
- case2：若 p 没有左孩子：p 的右孩子——根右 / 根 (根左右)，即右子树中最先被访问的结点

先序线索二叉树找先序前驱

在先序线索二叉树中找到指定结点 *p 的先序前驱pre：

若 p->ltag == 1，则 next = p->lChild；
若 p->ltag == 0，则 p 必有左孩子，但是先序遍历中，左右子树的结点只可能是根的后继，不可能是前驱，所以不能从左右孩子里寻找 p 的先序前驱，（除非从头开始遍历/三叉链表）
- case1：若能找到 p 的父结点，且 p 是左孩子：p 的父结点——根左右/根（根左右）右
- case2：若能找到 p 的父结点，且 p 是右孩子，且其左兄弟为空： p 的父结点——根右/根（根左右）
- case3：若能找到 p 的父结点，且 p 是右孩子，且其左兄弟非空：左兄弟子树中最后一个被先序遍历到的结点（根结点出发，优先往右，右没有往左，找到最下一层的结点）——根左右/根（根左右）右
- case4：若 p 没有父结点，即 p 为根结点，则 p 没有先序前驱

后序线索二叉树找后序前驱

在后序线索二叉树中找到指定结点 *p 的后序前驱pre：

若 p->ltag == 1：p->lChild；
若 p->ltag == 0，则 p 必有左孩子（不知道有没有右孩子）
- case1：若 p 有右孩子：p 的右孩子——— 左右根 / 左 (左右根) 根
- case2：若 p 没有右孩子：p 的左孩子——— 左根/(左右根)根

后序线索二叉树找后序后继

在后序线索二叉树中找到指定结点 *p 的后序后继next：

若 p->rtag == 1, 则 next = p->rChild;
若 p->rtag == 0, 则 p 必有右孩子，左孩子不知道，但是在后序遍历中，左右子树中的结点只有可能是根的前驱，而不可能是根的后继，所以找不到后继，（除非从头开始遍历/三叉链表）
- case1：如果能找到 p 的父结点，且 p 是右孩子：p 的父结点即为其后继——左右根/左(左右根)根
- case2：如果能找到 p 的父结点，且 p 是左孩子，其右兄弟为空：p 的父结点即为其后继——左根/（左右根）根
- case3：如果能找到 p 的父结点，且 p 是左孩子，其右兄弟非空： p 的后继为其右兄弟子树中第一个被后序遍历的结点——左右根/左（左右根）根
- case4：p 没有父结点，即 p 为根结点，则 p 没有后序后继

后续线索二叉树无法直接找到后续后继，所以如果要通过后续线索二叉树遍历二叉树的话，需要栈的辅助（来找父结点）

5.3.3 本节习题精选

选择题：题目、答案

综合题：题目、答案

5.4 树、森林

5.4.1 树的存储结构

树的存储结构.pdf

树的逻辑结构

树是 $n (n ⩾ 0)$ 个结点的有限集合， $n = 0$ 时称为空树，这是一种特殊情况。在任意一棵非空树中应满足：

有且仅有一个特定的称为根的结点
当 $n > 1$ 时，其余结点可分为 $m (m > 0)$ 个互不相交的有限集合 $T_{1}, T_{2}, \dots, T_{m}$ ，其中每个集合本身又是一棵树，并且称为根结点的子树

双亲表示法

双亲表示法（顺序存储）：顺序存储各个结点，每个结点中保存指向双亲的指针

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every path/.style={latex-}, % 结点之间连线的样式
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/2, level distance=3em},
	level 3/.style={sibling distance=4em/1, level distance=3em},
	]
	\node(A) {$A$}
		child {node (B) {$B$}
			child {node (E) {$E$}
				child {node (K) {$K$}}}
			child {node (F) {$F$}}
		}
		child {node (C) {$C$}
			child {node (G) {$G$}}
		}
		child {node (D) {$D$}
			child {node (H) {$H$}}
			child {node (I) {$I$}}
			child {node (J) {$J$}}
		};
	\end{tikzpicture}
\end{document}

编号	0	1	2	3	4	5	6	7	8	9	10
`data`	A	B	C	D	E	F	G	H	I	J	K
`parent`	$- 1$	$0$	$0$	$0$	$1$	$1$	$2$	$3$	$3$	$3$	$4$

#define MAX_TREE_SIZE 100	//树中最多结点数
 
typedef struct{	//树的结点定义
	ElemType data;
	int parent;	//双亲位置域
}PTNode;
 
typedef struct{	//树的类型定义
	PTNode nodes[MAX_TREE_SIZE];	//双亲表示
	int n;	//结点数
}PTree;

根结点存储在第一个位置，用-1表示没有双亲
增：新增数据元素，无需按逻辑上的次序存储；（只需要更改结点数n）
删（叶子结点）：① 将位指针域设置为-1（存在空数据，遍历更慢）；②用后面的数据填补；（需要更改结点数n）
删（不是叶子结点）：删除该结点以及其子孙结点（查询）
查询：
- 优点：查指定结点的双亲很方便；
- 缺点：查指定结点的孩子只能从头遍历，空数据导致遍历更慢；

双亲表示法也可用于存储森林

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every path/.style={latex-}, % 结点之间连线的样式
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/2, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/2, level distance=3em},
	level 3/.style={sibling distance=4em/2, level distance=3em},
	]
	\node[fill=green!30] (A) at(0,0) {$A$}
		child {node[fill=green!30] (B) {$B$}
			child {node[fill=green!30] (E) {$E$}
				child {node[fill=green!30] (K) {$K$}}
				child {node[fill=green!30] (L) {$L$}}
			}
			child {node[fill=green!30] (F) {$F$}}
		};
	\node[fill=purple!30] (C) at(1.5,0) {$C$}
		child {node[fill=purple!30] (G) {$G$}};
	\node[fill=orange!30] (D) at(3,0) {$D$}
		child {node[fill=orange!30] (H) {$H$}}
		child {node[fill=orange!30] (I) {$I$}}
		child {node[fill=orange!30] (J) {$J$}};
	\end{tikzpicture}
\end{document}

编号	0	1	2	3	4	5	6	7	8	9	10	11
data	A	B	C	D	E	F	G	H	I	J	K	L
parent	-1	0	-1	-1	1	1	2	3	3	3	4	4

孩子表示法

孩子表示法（顺序+链式）：顺序存储各结点，每个结点保存中保存孩子链表头指针

\usetikzlibrary{positioning}
\newcommand{\drawChildren}[2]{
	\pgfmathsetmacro{\idx}{#1}
	\def\childs{#2}
	\foreach \num [count=\i] in \childs {
		\ifnum\num=-1
			\node[draw=none, font=\LARGE] at(\i*3+1, -\idx) (temp){NULL};
		\else
			\node[fill=gray!20, minimum width=1cm, minimum height=2em] at(\i*3+1, -\idx) (temp){\num};
			\node[minimum width=1cm, minimum height=2em] at(\i*3+2, -\idx) (\idx-\i){};
		\fi
		\pgfmathtruncatemacro{\pre}{\i-1}
		\draw[-latex] (\idx-\pre.center) -- (temp);
	}
}
 
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/2, level distance=3em},
	level 3/.style={sibling distance=4em/1, level distance=3em},
	]
	\node(A) {$A$}
		child {node (B) {$B$}
			child {node (E) {$E$}
				child {node (K) {$K$}}}
			child {node (F) {$F$}}
		}
		child {node (C) {$C$}
			child {node (G) {$G$}}
		}
		child {node (D) {$D$}
			child {node (H) {$H$}}
			child {node (I) {$I$}}
			child {node (J) {$J$}}
		};
	\end{tikzpicture}
	\begin{tikzpicture}[scale=1, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[draw=none, font=\large] at(0,1){data};
		\node[draw=none, font=\large] at(1.5,1){firstchild};
 
		\def\myChar{A,B,C,D,E,F,G,H,I,J,K}
		\foreach \char [count=\i] in \myChar {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node at (0,-\idx) (node-\idx){\char};
			\node[font=\Large, draw=none, left of = node-\idx] {\idx};
			\node at (1.5,-\idx) [minimum width=2cm] (\idx-0){};
		}
 
		\drawChildren{0}{1,2,3,-1};
		\drawChildren{1}{4,5,-1};
		\drawChildren{2}{6,-1};
		\drawChildren{3}{7,8,9,-1};
		\drawChildren{4}{10,-1};
		\drawChildren{5}{-1};
		\drawChildren{6}{-1};
		\drawChildren{7}{-1};
		\drawChildren{8}{-1};
		\drawChildren{9}{-1};
		\drawChildren{10}{-1};
	\end{tikzpicture}
\end{document}

struct CTNode{// 孩子链表
	int child;	// 孩子结点在数组中的位置
	struct CTNode *next;	// 下一个孩子
};
// ↓
typedef struct{
	ElemType data;
	struct CTNode *firstChild;	// 第一个孩子
}CTBox;
// ↓
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];
	int n, r;	// 结点数和根的位置
}CTree;

优点：找孩子很方便
缺点：找父亲不方便，只能遍历整个链表

孩子表示法也可表示森林

\usetikzlibrary{positioning}
\newcommand{\drawChildren}[2]{
	\pgfmathsetmacro{\idx}{#1}
	\def\childs{#2}
	\foreach \num [count=\i] in \childs {
		\ifnum\num=-1
			\node[draw=none, font=\LARGE] at(\i*3+1, -\idx) (temp){NULL};
		\else
			\node[fill=gray!20, minimum width=1cm, minimum height=2em] at(\i*3+1, -\idx) (temp){\num};
			\node[minimum width=1cm, minimum height=2em] at(\i*3+2, -\idx) (\idx-\i){};
		\fi
		\pgfmathtruncatemacro{\pre}{\i-1}
		\draw[-latex] (\idx-\pre.center) -- (temp);
	}
}
 
\begin{document}
 
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/2, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/2, level distance=3em},
	level 3/.style={sibling distance=4em/2, level distance=3em},
	]
	\node[fill=red!30] (A) at(-1.5,0) {$A$};
	\node[fill=green!30] (B) at(0,0) {$B$}
		child {node[fill=green!30] (E) {$E$}
			child {node[fill=green!30, xshift=-2em] (K) {$K$}}
		}
		child {node[fill=green!30] (F) {$F$}};
	\node[fill=purple!30] (C) at(1.5,0) {$C$}
		child {node[fill=purple!30] (G) {$G$}};
	\node[fill=orange!30] (D) at(3,0) {$D$}
		child {node[fill=orange!30] (H) {$H$}}
		child {node[fill=orange!30] (I) {$I$}}
		child {node[fill=orange!30] (J) {$J$}};
	\end{tikzpicture}
	\begin{tikzpicture}[scale=1, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[draw=none, font=\large] at(0,1){data};
		\node[draw=none, font=\large] at(1.5,1){firstchild};
 
		\def\myChar{A,B,C,D,E,F,G,H,I,J,K}
		\foreach \char [count=\i] in \myChar {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node at (0,-\idx) (node-\idx){\char};
			\node[font=\Large, draw=none, left of = node-\idx] {\idx};
			\node at (1.5,-\idx) [minimum width=2cm] (\idx-0){};
		}
 
		\drawChildren{0}{-1};
		\drawChildren{1}{4,5,-1};
		\drawChildren{2}{6,-1};
		\drawChildren{3}{7,8,9,-1};
		\drawChildren{4}{10,-1};
		\drawChildren{5}{-1};
		\drawChildren{6}{-1};
		\drawChildren{7}{-1};
		\drawChildren{8}{-1};
		\drawChildren{9}{-1};
		\drawChildren{10}{-1};
	\end{tikzpicture}
\end{document}

孩子兄弟表示法

孩子兄弟表示法（链式）（最重要）：按照层序处理结点，左孩子右兄弟

对应二叉树的链式存储

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/2, level distance=3em},
	level 3/.style={sibling distance=4em/2, level distance=3em},
	]
	\node(A) at(0,0){$A$}
		child {node (B) {$B$}
			child {node (E) {$E$}
				child {node (K) {$K$}}
			}
			child {node (F) {$F$}}
		}
		child {node (C) {$C$}
			child {node (G) {$G$}}
		}
		child {node (D) {$D$}
			child {node (H) {$H$}}
			child {node (I) {$I$}}
			child {node (J) {$J$}}
		};
 
	\node(A) at (5,0){$A$}
		child {node [xshift=-4em](B) {$B$}
			child {node [xshift=-2em](E) {$E$}
				child {node (K) {$K$}}
				child {node (F) {$F$}}
			}
			child {node (C) [xshift=2em]{$C$}
				child {node (G) {$G$}}
				child {node (D) {$D$}
					child {node [xshift=-2em] (H) {$H$}
						child {node [xshift=2em](I) {$I$}
							child {node [xshift=2em] (J) {$J$}}
						}
					}
				}
			}
		};
	\end{tikzpicture}
	\hspace{10em}
\end{document}

可以用熟悉的二叉树操作处理树

typedef struct CSNode{
	ElemType data;	//数据域
	struct CSNode *firstchild, *nextsibling;
	//第一个孩子和右兄弟指针, *firstchild 看作左指针，*nextsibling看作右指针
}CSNode. *CSTree;

用于存储森林时，将森林中每棵树的根结点视为平级的兄弟关系

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/2, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/2, level distance=3em},
	level 3/.style={sibling distance=4em/2, level distance=3em},
	]
	\node[fill=green!30] (B) at(0,0) {$B$}
		child {node[fill=green!30] (E) {$E$}
			child {node[fill=green!30] (K) {$K$}}
			child {node[fill=green!30] (L) {$L$}}
		}
		child {node[fill=green!30] (F) {$F$}};
	\node[fill=purple!30] (C) at(1.5,0) {$C$}
		child {node[fill=purple!30] (G) {$G$}};
	\node[fill=orange!30] (D) at(3,0) {$D$}
		child {node[fill=orange!30] (H) {$H$}}
		child {node[fill=orange!30] (I) {$I$}}
		child {node[fill=orange!30] (J) {$J$}};
 
	\node[fill=green!30](B) at (6,0) {$B$}
		child {node[fill=green!30, xshift=-2em](E) {$E$}
			child {node[fill=green!30] (K) {$K$}
				child {node[fill=green!30, xshift=2em] (L) {$L$}}
			}
			child {node[fill=green!30] (F) {$F$}}
		}
		child {node[fill=purple!30] (C) [xshift=2em]{$C$}
			child {node[fill=purple!30] (G) {$G$}}
			child {node[fill=orange!30] (D) {$D$}
				child {node[fill=orange!30, xshift=-2em] (H) {$H$}
					child {node[fill=orange!30, xshift=2em](I) {$I$}
						child {node[fill=orange!30, xshift=2em] (J) {$J$}}
					}
				}
			}
		};
	\end{tikzpicture}
	\hspace{10em}
\end{document}

5.4.2 树、森林与二叉树的转换

树、森林与二叉树的转换.pdf

树↔二叉树：本质是用二叉链表存储树，左子树为孩子，右子树为兄弟
森林↔二叉树：本质是用二叉链表存储森林，森林中各个树的根结点之间视为兄弟关系

5.4.3 树、森林的遍历

树和森林的遍历.pdf

树的遍历

树的先序遍历

LeetCode589. N 叉树的前序遍历

若树非空，先访问根结点，再依次对每棵子树进行先根遍历；（和与之对应二叉树的先序遍历序列相同）

//递归实现，时间复杂度O(n)，空间复杂度O(log n)~O(n)
class Solution {
public:
	vector<int> preorder(Node* root) {
		vector<int> res;
		getPreOrder(root, res);
		return res;
	}
	void getPreOrder(Node* root, vector<int>& res){
		if(root==nullptr) return;
		res.push_back(root->val);
		for(Node* child:root->children){
			getPreOrder(child, res);
		}
	}
};

树的后序遍历

LeetCode590. N 叉树的后序遍历

若树非空，先依次对每棵子树进行后根遍历，最后再返回根结点；（和与之对应二叉树的后序遍历序列相同）

深度优先遍历

void PostOrder(TreeNode *R){
	if(R != NULL){
	while(R还有下一个子树T)
		PostOrder(T);	//后跟遍历下一个子树
	visit(R);	//访问根结点
	}
}

树的层序遍历

LeetCode429. N 叉树的层序遍历

层序遍历（队列实现）：类比二叉树的层序遍历

广度优先遍历
若树非空，则根结点入队；
若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；
重复以上操作直至队尾为空；

森林的遍历

森林是 $m (m ⩾ 0)$ 棵互不相交的树的集合，每棵树去掉根结点后，其各子树又组成森林

先序遍历：等同于依次对各个子树进行先序遍历；也可以先转换成与之对应的二叉树，对二叉树进行先序遍历；
- 若森林非空，则按如下规则进行遍历：
- 访问森林中第一棵树中根结点的子树森林
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历除去第一棵树之后剩余的树组成的森林
中序遍历：等同于依次对各个树进行后序遍历；也可以先转换成与之对应的二叉树，对二叉树进行中序遍历；
- 若森林非空，则按如下规则进行遍历：
- 中序遍历第一棵树中根结点的子树森林
- 访问森林中第一棵树的根结点
- 中序遍历除去第一棵树之后剩余的树组成的森林

树和森林的遍历与二叉树的遍历关系

考前记一记

树	森林	二叉树
先序遍历	先序遍历	先序遍历
后序遍历	中序遍历	中序遍历

后序遍历树可分为两步：从左到右访问双亲结点的每个孩子（转化为二叉树后就是先访问根结点再访问右子树）；访问完所有孩子后再访问它们的双亲结点（转化为二叉树后就是先访问左子树再访问根结点），因此树的后序遍历序列与其相应二叉树的中序遍历序列相同。

5.4.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

5.5 树与二叉树的应用

5.5.1 哈夫曼树

哈夫曼树.pdf

带权路径长度

结点的权：带有某种现实意义的数值，如表示结点的重要性
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
树的带权路径长度：树中所有叶结点的带权路径长度之和 $W P L = i = 1 \sum n w_{i} l_{i}$ 。如下述二叉树的带权路径长度为 $W P L = 1 \times 3 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 25$ 或 $W P L = 4 + 8 + 13 = 25$

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, fill=gray!20, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/1, level distance=3em},
	level 3/.style={sibling distance=4em/1, level distance=3em},
	]
	\node(1) {13}
		child {node (2) {8}
			child {node (4) {4}
				child {node[fill=green!20] (6) {1}}
				child {node[fill=green!20] (7) {3}}
			}
			child {node[fill=green!20] (5) {4}}
		}
        child {node[fill=green!20] (3) {5}};
	\end{tikzpicture}
\end{document}

哈夫曼树的定义

哈夫曼树的定义：在含有 $n$ 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称为最优二叉树

平时一般所说的哈夫曼树是指最优二叉树，也叫做严格二叉树（注意不是完全二叉树），但是哈夫曼树完全不局限于二叉树，也存在于多叉树中，即度为 $m$ 的哈夫曼树也叫最优 $m$ 叉树、严格 $m$ 叉树（注意不是完全 $m$ 叉树）

哈夫曼树的构造（重点）

给定 $n$ 个权值分别为 $w_{1}, w_{2}, \dots, w_{n}$ 的结点，构造哈夫曼树的算法描述如下：

将这 $n$ 个结点分别作为 $n$ 棵仅含一个结点的二叉树，构成森林 $F$
构造一个新结点，从 $F$ 中选区两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为左右子树上根结点的权值之和
从 $F$ 中删除刚才选出的两棵树，同时将新得到的树加入到 $F$ 中去
重复操作，直至 $F$ 中只剩下一棵树为止

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, fill=gray!20, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/1, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/1, level distance=3em},
	level 3/.style={sibling distance=4em/1, level distance=3em},
	]
	\node(1) {}
		child {node[fill=green!20] (2) {7}}
        child {node (3) {}
			child {node (4) {}
				child {node (6) {}
					child {node[fill=green!20] (7){1}}
					child {node[fill=green!20] (8){2}}
				}
				child {node[fill=green!20] (7) {2}}
			}
			child {node[fill=green!20] (5) {3}}
		};
 
	\node[font=\Large, draw=none, fill=none] [below=of 1, yshift=3em] {15};
	\node[font=\Large, draw=none, fill=none] [below=of 3, yshift=3em] {8};
	\node[font=\Large, draw=none, fill=none] [below=of 4, yshift=3em] {5};
	\node[font=\Large, draw=none, fill=none] [below=of 6, yshift=3em] {3};
	\end{tikzpicture}
\end{document}

特点：（联系构造过程）

每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度就越大
哈夫曼树的结点总数为 $2 n - 1$
哈夫曼树中只有度为 $0$ 和度为 $m$ 的结点
哈夫曼树并不唯一，但WPL必然相同且为最优
哈夫曼树中上层结点权值大于下层结点权值

二叉以上情形：添加虚结点（权值为0），添加个数为 $(m - 1) - (n_{0} - 1) % (m - 1)$

$m$ 叉哈夫曼树总结点数： $n_{0} + n_{m} = m \cdot n_{m} + 1$ ，则叶结点个数 $n_{0} = 1 + (m - 1) n_{m}$

\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=5em/1, level distance=4em},%横向距离与纵向距离
	level 2/.style={sibling distance=5em/1.5, level distance=4em},
	level 3/.style={sibling distance=5em/1.5, level distance=4em},
	]
	\node[rectangle] {27}
		child {node [rectangle]{14}
			child {node[rectangle] {5}
				child {node[dashed] {0}}
		        child {node {2}}
				child {node {3}}
			}
			child {node {4}}
			child {node {5}}
		}
        child {node {6}}
		child {node {7}};
	\end{tikzpicture}
\end{document}

哈夫曼编码（重点）

字符编码

固定长度编码：每个字符用相等长度的二进制位表示
可变长度编码：允许用不同字符对不等长的二进制位表示
- 前缀编码：如果没有一个编码是另一个编码的前缀，称这样的编码为前缀编码（前缀编码无歧义）
- 可以联系IPv4地址

哈弗曼编码：由哈夫曼树得到哈弗曼编码，字符集中每一个字符作为一个叶子结点，各个字符出现带频度作为结点的权值，构造哈夫曼树（哈夫曼树同样不唯一）。

相比固定长度编码，哈夫曼编码可以减少编码长度，压缩数据易错

Example

下图中ABCD的出现频次分别为10,8,80,2，编码分别为01、000、1、001

 

\usetikzlibrary{positioning}

\begin{document}

\begin{tikzpicture}[scale=2, ultra thick,

every node/.style={draw=black, circle, very thick, fill=gray!20, font =\huge, minimum size=3em},

level 1/.style={sibling distance=4em/1, level distance=3em},%横向距离与纵向距离

level 2/.style={sibling distance=4em/1, level distance=3em},

level 3/.style={sibling distance=4em/1, level distance=3em},

]

\node(1) {}

  child {node (2) {}

  	child {node (4) {}

  		child {node[fill=green!20] (6) {B}}

  		child {node[fill=green!20] (7) {D}}

  	child {node[fill=green!20] (5) {A}}

   child {node[fill=green!20] (3) {C}};

\node[font=\Large, draw=none, fill=none] [below=of 3, yshift=3em] {80};

\node[font=\Large, draw=none, fill=none] [below=of 5, yshift=3em] {10};

\node[font=\Large, draw=none, fill=none] [below=of 6, yshift=3em] {8};

\node[font=\Large, draw=none, fill=none] [below=of 7, yshift=3em] {2};

\node[font=\Large, draw=none, fill=none] [below left=of 1, xshift=2.5em, yshift=2.5em] {0};

\node[font=\Large, draw=none, fill=none] [below right=of 1, xshift=-2.5em, yshift=2.5em] {1};

\node[font=\Large, draw=none, fill=none] [below left=of 2, xshift=2.5em, yshift=2.5em] {0};

\node[font=\Large, draw=none, fill=none] [below right=of 2, xshift=-2.5em, yshift=2.5em] {1};

\node[font=\Large, draw=none, fill=none] [below left=of 4, xshift=2.5em, yshift=2.5em] {0};

\node[font=\Large, draw=none, fill=none] [below right=of 4, xshift=-2.5em, yshift=2.5em] {1};

\end{tikzpicture}

\end{document}

5.5.2 并查集

并查集演示

并查集.pdf

如何表示“集合”关系

逻辑结构：集合

将各个元素划分为若干个互不相交的子集–>类比森林，可以用互不相交的树表示多个集合，因此可以把同一个集合中的不同元素组合成一棵树

\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=4em/2, level distance=3em},%横向距离与纵向距离
	level 2/.style={sibling distance=4em/2, level distance=3em},
	level 3/.style={sibling distance=4em/2, level distance=3em},
	]
	\node[fill=green!30] (A) at(0,0) {$A$}
		child {node[fill=green!30] (B) {$B$}
			child {node[fill=green!30] (E) {$E$}
				child {node[fill=green!30] (K) {$K$}}
				child {node[fill=green!30] (L) {$L$}}
			}
			child {node[fill=green!30] (F) {$F$}}
		};
	\node[fill=purple!30] (C) at(1.5,0) {$C$}
		child {node[fill=purple!30] (G) {$G$}};
	\node[fill=orange!30] (D) at(3,0) {$D$}
		child {node[fill=orange!30] (H) {$H$}}
		child {node[fill=orange!30] (I) {$I$}}
		child {node[fill=orange!30] (J) {$J$}};
	\end{tikzpicture}
\end{document}

编号	0	1	2	3	4	5	6	7	8	9	10	11
data	A	B	C	D	E	F	G	H	I	J	K	L
parent	-1	0	-1	-1	1	1	2	3	3	3	4	4

并查集：表示一种集合的逻辑关系，只进行“并”、“查”和“初始化”三种基本操作

初始化Intial(S)
并Union(S, Root1, Root2)：把两个集合合并为一个集合–>让其中一棵树成为另一棵树的子树即可
查Find(S, x)：查询一个元素到底属于哪一个集合–>从指定元素出发，找到其根结点
- 判断两个元素是否属于同一个集合–>判断二者的根结点是否相同即可

并查集的代码实现

树使用双亲表示法表示时，更容易查询到父结点，故此时并查操作更容易实现

#define SIZE 13
int UFSet[SIZE];	//集合元素数组
 
//初始化并查集
void Initial(int S[]){
	for (int i=0; i<SIZE; i++)
		S[i]=-1;	//初始化时，每个元素相互独立
}

Find “查”操作，查找 x 所属集合（返回 x 所属根结点），最坏时间复杂度 $O (n)$

int Find(int S[], int x){
	while(S[x]>=0)	//循环寻找x的根
		x=S[x];		//不断找父结点
	return x;	//根的S[]小于0，返回根结点
}

Union “并”操作，将两个集合合并为一个，时间复杂度 $O (1)$

void Union(int S[], int Root1, int Root 2){
	if(Root1 == Root2)	//要求Root1与Root2是不同的集合
		return;
	S[Root2]=Root1;	//将根Root2连接到另一根Root1下面
}

并查集的优化

Find操作的复杂度与树的高度直接相关

对 Union 操作的优化：Union 操作时，尽量不让树长高

思路：在每次Union操作构建树的时候，尽可能让树不长高
- Union操作，让小树合并到大树，小树成为大树的子树
- 用根结点的绝对值表示树的结点总数
该方法构造的树高不超过 $⌊ lo g_{2} n + 1 ⌋$ ，优化后Find操作最坏时间复杂度为 $O (lo g_{2} n)$

编号	0	1	2	3	4	5	6	7	8	9	10	11
data	A	B	C	D	E	F	G	H	I	J	K	L
parent	-6	0	-2	-5	1	1	2	3	3	3	4	4

//Union “并”操作，小树合并到大树
void Union(int S[], int Root1, int Root2){
	if(Root1 == Root2)
		return;
	if(S[Root2]>S[Root1]){	//Root2结点更少
		S[Root1] += S[Root2];	//累加结点总数
		S[Root2] = Root1;		//小树合并到大树
	}else{	//Root1结点更少
		S[Root2] += S[Root1];
		S[Root1] = Root2;
	}
}

并查集的进一步优化

对 Find 操作的优化：查找时，顺便压缩路径，把路径上所有的非根结点都挂到根结点上

并查集的进一步优化.pdf

思路：先找到根结点，再将查找路径上所有结点都挂到根结点下
每次 Find 操作，先找根，再压缩路径，可使树的高度不超过 $O (α (n))$ 。其中 $α (n)$ 是一个增长很缓慢的函数，对于常见的 $n$ 值，通常 $α (n) ⩽ 4$

//Find “查”操作优化，先找到根结点，再进行“压缩路径”
int Find(int S[], int x){
	int root = x;
	while(S[root]>=0)	//循环找到根
		root=S[root];
	while(x!=root){	//压缩路径，从下往上把路径上的所有非根结点都挂到根结点上
		int t=S[x];		//t指向x的父结点
		S[x]=root;		//x直接挂到根结点下
		x=t;
	}
	return root;	//返回根结点编号
}

并查集的应用

Kruskal算法：判断是否加入一条边之前，先查找这条边关联的两个顶点是否属于同一个集合(即判断加入这条边之后是否形成回路)，若形成回路，则继续判断下一条边；若不形成回路，则将该边和边对应的顶点加入最小生成树T，并继续判断下一条边，直到所有顶点都已加入最小生成树考前记一记
判断连通性：遍历无向图的边，每遍历到一条边，就把这条边连接的两个顶点合并到同一个集合中，处理完所有边后，只要是相互连通的顶点都会被合并到同一个子集合中，相互不连通的顶点一定在不同的子集合中。
判环

5.5.3 本节习题精选

选择题：题目、答案

综合题：题目、答案

我的 Obsidian 知识库

探索

第5章 树与二叉树

5.1 树的基本概念

5.1.1 树的定义

5.1.2 基本术语

5.1.3 树的性质

5.1.4 本节习题精选

5.2 二叉树的概念

5.2.1 二叉树的定义与特性

二叉树常考性质

5.2.2 几种特殊的二叉树

5.2.3 二叉树的存储结构

二叉树的顺序存储

二叉树的链式存储

5.2.4 本节习题精选

5.3 二叉树的遍历和线索二叉树

5.3.1 二叉树的遍历

二叉树的先序遍历

二叉树的中序遍历

二叉树的后序遍历

二叉树的层序遍历

由遍历序列构造二叉树

二叉树遍历的应用

5.3.2 线索二叉树

线索二叉树的概念与作用

线索二叉树的存储结构

二叉树的线索化

中序线索化

先序线索化

后序线索化

线索二叉树中找前驱、后继

中序线索二叉树找中序后继

中序线索二叉树找中序前驱

先序线索二叉树找先序后继

先序线索二叉树找先序前驱

后序线索二叉树找后序前驱

后序线索二叉树找后序后继

5.3.3 本节习题精选

5.4 树、森林

5.4.1 树的存储结构

树的逻辑结构

双亲表示法

孩子表示法

孩子兄弟表示法

5.4.2 树、森林与二叉树的转换

5.4.3 树、森林的遍历

树的遍历

树的先序遍历

树的后序遍历

树的层序遍历

森林的遍历

树和森林的遍历与二叉树的遍历关系

5.4.4 本节习题精选

5.5 树与二叉树的应用

5.5.1 哈夫曼树

带权路径长度

哈夫曼树的定义

哈夫曼树的构造（重点）

哈夫曼编码（重点）

5.5.2 并查集

如何表示“集合”关系

并查集的代码实现

并查集的优化

并查集的进一步优化

并查集的应用

5.5.3 本节习题精选

关系图谱

目录

反向链接

第5章树与二叉树