树和二叉树答案,二叉树考研题
墨初 知识笔记 62阅读
文章目录 树与二叉树树的基本概念结点、树属性的描述树的性质 二叉树的概念二叉树的性质二叉树的构建二叉树的遍历先序遍历中序遍历后序遍历层次遍历 递归算法和非递归算法的转换源代码 线索二叉树二叉树的线索化线索二叉树 找前驱/后继 树和森林树的存储 树与二叉树的应用哈夫曼树和哈夫曼编码并查集 习题总结
树与二叉树 树的基本概念
树的定义是递归的即在树的定义中又用到了其自身树是一种递归的数据结构。同时是一种分层结构具有以下两个特点
树的根节点没有前驱除根节点外所有结点有且只有一个前驱。树中所有结点都可以有零个或多个后继。特点树适合于表示具有层次结构的数据。
结点、树属性的描述 树中一个结点的孩子个数称为该结点的度树中结点的最大度数称为树的度。
如结点B的度为 2结点D的度为 3树的度为 3剩余结点的度数都小于3因此这颗树的度为3。
结点的深度、高度和层次
结点的深度从上往下数默认从 1 开始
结点的高度从下往上数
树的层次总共多少层
树的性质树具有如下最基本的性质
结点数 总度数 1
结点的度结点有几个孩子分支
eg:【2010统考真题】在一棵度为4的树 T T T中若有20个度为4的结点10个度为3的结点1个度为2的结点10个度为1的结点则树 T T T的叶子结点个数是 B B B
A . 41 A.41 A.41 B . 82 B.82 B.82 C . 113 C.113 C.113 D . 122 D.122 D.122
结点数20 10 1 10 X 叶子 X_{叶子} X叶子 41 X 叶子 X_{叶子} X叶子
总度数20*4 10*3 1*2 10*1 122
结点数 总度数 1 > 41 X 叶子 X_{叶子} X叶子 122 1 > X 叶子 X_{叶子} X叶子 122 1 - 41 82
度为m的树和m叉树的区别
度为 m m m的树第 i i i层至多有 m i − 1 m^{i -1} mi−1个结点 m m m叉树第 i i i层至多有 m i − 1 m^{i - 1} mi−1个结点
高度为 h h h的 m m m叉树至多有 m h − 1 m − 1 \frac {m^{h} - 1}{m -1} m−1mh−1个结点
等比数列求和公式
a a q a q 2 ⋅ ⋅ ⋅ a q n − 1 a ( 1 − q n ) 1 − q a aq aq^2 ··· aq^{n - 1} \frac{a(1-q^n)}{1-q} aaqaq2⋅⋅⋅aqn−11−qa(1−qn)
每层的结点求和即 m 0 m 1 m 2 ⋅ ⋅ ⋅ ⋅ m h − 1 m^0 m^1 m^2 ···· m^{h-1} m0m1m2⋅⋅⋅⋅mh−1利用等比数列求和即可。
高度为 h h h的 m m m叉树至少有 h h h个结点高度为 h h h、度为 m m m的树至少有 h m − 1 hm-1 hm−1个结点。
具有n个结点的m叉树的最小高度为 ⌈ l o g m ( n ( m − 1 ) 1 ) ⌉ \lceil log_m(n(m -1) 1) \rceil ⌈logm(n(m−1)1)⌉
高度最小的情况所有结点都有 m m m个孩子
证明过程如下前 h − 1 h-1 h−1层最多有$\frac {m^{h -1} - 1}{m - 1} 个结点前 h 层最多有 个结点前h层最多有 个结点前h层最多有\frac {m^{h} - 1}{m - 1} $个结点
m h − 1 − 1 m − 1 < n ≤ m h − 1 m − 1 m h − 1 < n ( m − 1 ) 1 ≤ m h h − 1 < l o g m ( n ( m − 1 ) 1 ) ≤ h h m i n ⌈ l o g m ( n ( m − 1 ) 1 ) ⌉ \frac {m^{h -1} - 1}{m - 1} < n ≤ \frac {m^{h} - 1}{m - 1}\\ m^{h-1} < n(m -1) 1 ≤ mh\\ h - 1 < log_m(n(m - 1) 1) ≤ h\\ h_{min} \lceil log_m(n(m -1) 1) \rceil m−1mh−1−1<n≤m−1mh−1mh−1<n(m−1)1≤mhh−1<logm(n(m−1)1)≤hhmin⌈logm(n(m−1)1)⌉
本章需要着重讨论的是二叉树Binary Tree。
二叉树是一种特殊的树形结构其特点是每个节点至多只有两棵子树即二叉树中不存在度大于2的结点并且二叉树的子树有左右之分其次序不能任意颠倒。一棵二叉树大概长这样
并且二叉树任何结点的子树是有左右之分的不能颠倒顺序比如A结点左边的子树称为左子树右边的子树称为右子树。
二叉树有 5 中基本形态分别是
几种特殊的二叉树
满二叉树在一棵二叉树中所有分支结点都存在左子树和右子树且叶子结点都在同一层。
完全二叉树只有最后一层有空缺并且所有的叶子结点是按照从左往右的顺序排列的。所以一棵满二叉树一定是一棵完全二叉树。
二叉排序树可用于元素的排序、搜索
左子树上所有结点的关键字均小于根结点的关键字
右子树上所有结点的关键字均大于根结点的关键字
左子树和右子树又各是一颗二叉排序树
平衡二叉树能更高的搜索效率
树上任意一个结点的左子树和右子树的深度之差不超过 1。
假设一棵二叉树中结点总数为 n n n度为0、1、2的结点数量分别为 n 0 n_0 n0、 n 1 n_1 n1、 n 2 n_2 n2结点的边数为 E E E.
性质一非空二叉树上的叶子节点数等于度为2的结点树加1即 n 0 n 2 1 n_0 n_2 1 n0n21。
由于一棵二叉树中只有这三种类型的结点那么可以直接得到结点总数
n n 0 n 1 n 2 n n_0 n_1 n_2 nn0n1n2
接下来换一个思路从边的数量上考虑。因为每个结点有且仅有一条边与其父结点相连那么边数之和就可以表示为
E n 1 2 n 2 E n_1 2n_2 En12n2
度为 1 的结点有一条边度为 2 的结点有两条边度为 0 的结点没有边。
根据前面树的基本性质可知结点的边数为 E n − 1 E n - 1 En−1。因此可以得到另一个计算结点总数的方式结合公式 (3)(4)得
E n − 1 n 1 2 n 2 ( 公式 4 ) n n 1 2 n 2 1 n n 1 2 n 2 1 n 0 n 1 n 2 ( 公式 3 ) n 0 n 2 1 E n - 1 n_1 2n_2(公式 4)\\ n n_1 2n_2 1\\ n n_1 2n_2 1 n_0 n_1 n_2(公式 3)\\ n_0 n_2 1 En−1n12n2(公式4)nn12n21nn12n21n0n1n2(公式3)n0n21
性质二非空二叉树上第k层上至多有 2 k − 1 ( k ≥ 1 ) 2^{k - 1}(k≥1) 2k−1(k≥1)个结点。
第一层至多有 2 1 − 1 2^{1-1} 21−1个结点第二层至多有 2 2 − 1 2 2^{2-1} 2 22−12个结点以此类推可以证明其为一个公比为 2 的等比数列 2 k − 1 2^{k-1} 2k−1。
性质三高度为k的二叉树至多有 2 k − 1 2^k - 1 2k−1个结点 ( h ≥ 1 ) (h≥1) (h≥1)
对于一棵深度为k的二叉树可以具有的最大结点数量为
n 2 0 2 1 2 2 . . . 2 k − 1 n 2^0 2^1 2^2 ... 2^{k - 1} n202122...2k−1
实际上每一层结点数量构成了一个以公比q 2的等比数列结合等比数列求和公式得
S n a 1 × ( 1 − q n ) 1 − q 1 × ( 1 − 2 k ) 1 − 2 − ( 1 − 2 k ) 2 k − 1 S_n \frac {a_1 × (1 - q_n)}{1 - q} \frac{1×(1 - 2^k)}{1 - 2} -(1 - 2^k) 2^k - 1 Sn1−qa1×(1−qn)1−21×(1−2k)−(1−2k)2k−1
性质四
对一棵有n个结点、深度为k的完全二叉树按从上到下、从左到右的顺序依次编号 1,2···n现在对于任意一个结点i有以下关系
i来说其左孩子为2i右孩子为2i1。如果i 1那么此结点为二叉树的根节点如果i > 1那么其父结点就是 ⌊ i / 2 ⌋ \lfloor i/2 \rfloor ⌊i/2⌋比如第三个结点的父节点为第1个结点也就是根节点。如果2i > n则结点i没有左孩子比如下图中的二叉树n为5假设此时i 3那么2i 6 > n 5说明第三个结点没有左孩子。如果2i 1 > n则结点i没有右孩子。 性质五一棵具有n个结点的**完全二叉树**深度为 k ⌊ l o g 2 n 1 ⌋ k \lfloor log_2n 1 \rfloor k⌊log2n1⌋。
完全二叉树除了最后一层有空缺外其他层数都是饱满的。假设这棵二叉树为满二叉树那么根据我们前面得到的性质假设层数为k层那么总结点数量为 n 2 k − 1 n 2^k - 1 n2k−1根据完全二叉树性质最后一层可满可不满(1k-1层为满二叉树的情况下总结点数 2 k − 1 − 1 2^{k - 1} - 1 2k−1−1)那么一棵完全二叉树结点的总结点数n满足
2 k − 1 − 1 < n ≤ 2 k − 1 2^{k - 1} - 1 < n ≤ 2^k - 1 2k−1−1<n≤2k−1
因为n是一个整数那么可以写成
2 k − 1 ≤ n ≤ 2 k − 1 2^{k - 1} ≤ n ≤ 2^k - 1 2k−1≤n≤2k−1
这里左边可以取等号的情况如上图所示该树为完全二叉树的极端情况。
现在只看左边的不等式两边取对数得
k − 1 ≤ l o g 2 n k - 1 ≤ log_2n k−1≤log2n
综上所述一棵具有n个结点的完全二叉树深度为 k ⌊ l o g 2 n 1 ⌋ k \lfloor log_2n 1\rfloor k⌊log2n1⌋。
⚠️性质五推导比较复杂推荐直接记忆✌️。
二叉树练习题
由三个结点可以构造出多少种不同的二叉树
手画直接的到结果一共是五种。但是如果要求N个结点的话如何求解呢可以利用动态规划接下来我们分析一下
假设现在没有结点或者一个结点那么只有一种情况 h ( 0 ) h ( 1 ) 1 h(0) h(1) 1 h(0)h(1)1
假设现在有两个结点其中一个为根节点剩下的一个结点可以为左结点或右结点。如果为左结点那么右边 0 个结点如果为右结点那么左边 0 个结点则 h ( 2 ) h ( 1 ) × h ( 0 ) h ( 0 ) × h ( 1 ) 2 h(2) h(1)×h(0) h(0)×h(1) 2 h(2)h(1)×h(0)h(0)×h(1)2
假设现在有三个结点其中一个为根节点剩下的两个结点情况就有三种情况两个都在左边或者右边或者一边一个则 h ( 3 ) h ( 2 ) × h ( 0 ) h ( 1 ) × h ( 1 ) h ( 0 ) × h ( 0 ) 2 1 2 5 h(3) h(2) × h(0) h(1) × h(1) h(0) × h(0) 2 1 2 5 h(3)h(2)×h(0)h(1)×h(1)h(0)×h(0)2125
总结N每次加一项数就会多一项所以只需要按照规律把所有情况的结果相加即可。
#include <stdio.h>int main() { int n; scanf(%d, &n); int dp[n 1]; dp[0] dp[1] 1; for (int i 2; i < n; i) { dp[i] 0; for (int j 0; j < i; j) { dp[i] dp[i - j - 1] * dp[j]; } } printf(%d,dp[n]);}【2009年统考真题】已知一棵完全二叉树的第6层设根为第1层有8个叶结点则该完全二叉树的结点个数最多是C
A . 39 A.39 A.39 B . 53 B.53 B.53 C . 111 C.111 C.111 D . 119 D.119 D.119
解第6层最多 2 6 − 1 32 2^{6-1} 32 26−132个结点8个叶结点则剩下的24个结点均有左右孩子满足最多结点个数即第7层有24*248个结点前6层一共有 2 6 − 1 63 2^{6} - 1 63 26−163个结点所有最多有 63 48 111 63 48 111 6348111个结点。
二叉树的构建定义结构体
typedef char E;typedef struct TreeNode { E element; struct TreeNode *left, *right;} TreeNode, *Node;假设我们要构建这个二叉树首先我们要创建好这几个结点
int main() { Node a malloc(sizeof(TreeNode)); Node b malloc(sizeof(TreeNode)); Node c malloc(sizeof(TreeNode)); Node d malloc(sizeof(TreeNode)); Node e malloc(sizeof(TreeNode)); a->element A; b->element B; c->element C; d->element D; e->element E;}然后从上往下依次连接每一个结点并且测试是否连接成功
int main() { //创建结点代码.... a->left b; a->right c; b->left d; b->right e; c->left c->right NULL; d->left d->right NULL; e->left e->right NULL; printf(%c, a->left->left->element);}注意这里需要将叶子结点或者其他只有一个结点的另一个空结点设置为NULL。
与此同时我们在printf函数部分设置断点debug
前面通过使用链式结构成功构建出了一棵二叉树接着我们来看看如何遍历一棵二叉树也就是说想要访问二叉树的每一个结点。由于树形结构特殊遍历顺序并不唯一所以一共有四种访问方式**先序遍历、中序遍历、后序遍历、层序遍历。**不同的访问方式输出都结点顺序也不同。
首先需要将这棵二叉树组装好这一步比较繁琐无可避免
int main() { Node a malloc(sizeof(TreeNode)); Node b malloc(sizeof(TreeNode)); Node c malloc(sizeof(TreeNode)); Node d malloc(sizeof(TreeNode)); Node e malloc(sizeof(TreeNode)); Node f malloc(sizeof(TreeNode)); a->element A; b->element B; c->element C; d->element D; e->element E; f->element F; a->left b; a->right c; b->left d; b->right e; c->right f; c->left NULL; d->left d->right NULL; e->left e->right NULL; f->left f->right NULL;}先序遍历是一种勇往直前的态度走到哪就遍历到那里先走左边再走右边比如上面的这个图首先会从根节点开始从A开始先左后右那么下一个就是 B然后继续走左边左边为 D现在 ABD 走完之后B 的左边结束了那么就要从 B 的右边开始了因此下一个是 EE 结束之后现在 A 的左子树已经完全遍历完成了。然后就是 A 的右边接着就是 CC 没有左子树直接走右边最后输出 F所以上面这个二叉树的前序遍历结果为ABDECF。
先序遍历preOrder的操作过程如下若二叉树为空则什么也不做否则
打印根节点先序遍历左子树先序遍历右子树接下来就是编写实现先序遍历的函数了。我们传入的是根节点根据先序遍历的特点不难发现先序遍历中根节点一直都是先沿着左子树“勇往直前”直到走到了尽头再走右子树如此循环往复递归函数就具有这个特点。当走到一个结点的时候我们就打印对应的元素。那么如何结束这个递归函数呢之前说过递归函数有递归入口和终止条件入口已经有了那么终止条件是什么呢二叉树走到尽头即结点的左右孩子都为NULL那就表示已经到头了直接返回即可。
因此有了下面的函数
void perOrder(Node root) { //传入二叉树根节点 if (root NULL) return;//终止条件 printf(%c, root->element); perOrder(root->left); perOrder(root->right);}最后在main函数中调用即可
int main() { //组装二叉树函数 //... perOrder(a);}那么先序遍历我们了解完了接着就是中序遍历了中序遍历在顺序上与先序遍历不同先序遍历是走到哪就打印到哪而中序遍历需要先完成整个左子树的遍历后再打印然后再遍历其右子树。
中序遍历还是以上面的二叉树为例首先需要先不断遍历左子树走到最底部但是沿途并不进行打印而是到底之后再打印所以第一个打印的是D接着由于没有右子树所以我们回到B此时再打印B然后再去看B的右结点E由于没有左子树和右子树了所以直接打印E左边遍历完成接着回到A打印A然后对A的右子树重复上述操作。所以说遍历的基本规则还是一样的只是打印值的时机发生了改变。
中序遍历inOrder的操作过程如下若二叉树为空则什么也不做否则
中序遍历左子树打印结点中序遍历右子树所以这棵二叉树的中序遍历结果为DBEACF我们可以发现一个规律就是在某个结点的左子树中所有结点其中序遍历结果也是按照这样的规律排列的比如A的左子树中所有结点中序遍历结果中全部都在A的左边右子树中所有的结点全部都在A的右边这个规律很关键后面在做一些算法题时会用到。对应的递归算法如下
void inOrder(Node root) { if (root NULL) return; inOrder(root->left); printf(%c, root->element); inOrder(root->right);}接着我们来看一下后序遍历后序遍历继续将打印的时机延后需要等待左右子树全部遍历完成才会去进行打印。
首先还是一路向左到达结点D此时结点D没有左子树了接着看结点D还有没有右子树发现也没有左右子树全部遍历完成那么此时再打印D同样的D完事之后就回到B了此时接着看B的右子树发现有结点E重复上述操作E结点没有左子树也没有右子树E也打印出来了接着B的左右子树全部OK那么再打印B接着A的左子树就完事了现在回到A看到A的右子树继续重复上述步骤当A的右子树也遍历结束后最后再打印A结点。
后序遍历postOrder的操作过程如下若二叉树为空则什么也不做否则
后序遍历左子树后序遍历右子树打印结点所以最后的遍历顺序为DEBFCA不难发现整棵二叉树包括子树根结点一定是在后面的比如A在所有的结点的后面B在其子节点D、E的后面这一点恰恰和前序遍历相反注意不是得到的结果相反是规律相反
void postOrder(Node root) { if (root NULL) return; postOrder(root->left); postOrder(root->right); printf(%c, root->element);}三种遍历算法中递归遍历左、右子树的顺序都是固定的只是访问根节点的顺序不同。不管采用哪种遍历算法每个结点都访问一次且仅访问一次故时间复杂度都是 O ( n ) O(n) O(n)。在递归遍历中递归工作栈的栈深恰好为树的深度所以在最坏的情况下二叉树是有 n n n个结点且深度为 n n n的单支树遍历算法的空间复杂度为 O ( n ) O(n) O(n)。
层次遍历 层次遍历如左图所示即按照箭头所指方向按照1,2,3,4 的层次顺序对二叉树中的各个结点进行访问。要进行层次遍历需要借助一个 队列。首先将二叉树根节点入队然后出队访问出队结点。若它右左子树则将左子树根节点入队若它有右子树则将右子树根节点入队。完成入队后出队访问出队结点……如此反复直到队列为空。
二叉树的层次遍历算法如下
void levelOrder(TNode root) { Queue queue; initQueue(&queue); EnQueue(&queue, root); //根节点入队 while (!isEmpty(&queue)) { //不断重复直到队列为空为止 TNode node DeQueue(&queue);//出队元素并打印 printf(%c, node->element); if (node->left) //如果存在左还在入队 EnQueue(&queue, node->left); if (node->right) //如果存在右孩子入队 EnQueue(&queue, node->right); }}温故而知新这里顺带复习了一下队列的相关内容建议自己手写或手敲下列的所有内容加以巩固练习。
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>typedef char E;typedef struct TreeNode { E element; struct TreeNode *left, *right;} TreeNode, *TNode;typedef TNode T;typedef struct QueueNode { T element; struct QueueNode *next;} QueueNode, *QNode;typedef struct Queue { QNode front, rear;} Queue, *LinkedQueue;bool initQueue(LinkedQueue queue) { QNode node malloc(sizeof(QueueNode)); if (node NULL) return 0; queue->front queue->rear node; return 1;}bool EnQueue(LinkedQueue queue, T element) { QNode node malloc(sizeof(QueueNode)); if (node NULL) return 0; node->element element; queue->rear->next node; queue->rear node; return 1;}bool isEmpty(LinkedQueue queue) { return queue->front queue->rear;}T DeQueue(LinkedQueue queue) { T e queue->front->next->element; QNode node queue->front->next; queue->front->next queue->front->next->next; if (queue->rear node) queue->rear queue->front; free(node); return e;}void levelOrder(TNode root) { Queue queue; initQueue(&queue); EnQueue(&queue, root); //根节点入队 while (!isEmpty(&queue)) { //不断重复直到队列为空为止 TNode node DeQueue(&queue);//出队元素并打印 printf(%c, node->element); if (node->left) //如果存在左还在入队 EnQueue(&queue, node->left); if (node->right) //如果存在右孩子入队 EnQueue(&queue, node->right); }}int main() { TNode a malloc(sizeof(TreeNode)); TNode b malloc(sizeof(TreeNode)); TNode c malloc(sizeof(TreeNode)); TNode d malloc(sizeof(TreeNode)); TNode e malloc(sizeof(TreeNode)); TNode f malloc(sizeof(TreeNode)); a->element A; b->element B; c->element C; d->element D; e->element E; f->element F; a->left b; a->right c; b->left d; b->right e; c->right f; c->left NULL; d->left d->right NULL; e->left e->right NULL; f->left f->right NULL; levelOrder(a);}非递归的写法需要使用循环但是就比较麻烦了。我们需要使用栈来帮助我们完成实际上递归写法本质上也是在利用栈我们依然是从第一个结点开始先走左边每向下走一步先输出节点的值然后将对应的结点丢到栈中当走到尽头时表示左子树已经遍历完成接着就是从栈中依次取出栈顶节点如果栈顶结点有右子树那么再按照同样的方式遍历其右子树重复执行上述操作直到栈清空为止。
一路向左不断入栈直到尽头到达尽头后出栈看看有没有右子树如果没有就继续出栈直到遇到有右子树的为止拿到右子树后从右子树开始重复上述步骤直到栈清空比如我们还是以上面的这棵树为例
首先我们需要自己创建栈和相对应的数据结构
typedef char E;typedef struct TreeNode { E element; struct TreeNode *left, *right;} TreeNode, *TNode;typedef TNode T; //这里栈内元素类型定义为上面Node也是二叉树结点指针typedef struct StackNode { T element; struct StackNode *next;} StackNode, *SNode;//非递归操作void initStack(SNode head) { head->next NULL;}bool pushStack(SNode head, T element) { SNode node malloc(sizeof(StackNode)); if (node NULL) return 0; node->element element; node->next head->next; head->next node; return 1;}bool isEmpty(SNode head) { return head->next NULL;}T popStack(SNode head) { SNode top head->next; T e head->next->element; head->next head->next->next; free(top); return e;}创建完栈以后接下来我们实现先序遍历的函数
void perOrder(TNode root) { StackNode stack; initStack(&stack); while (root || !isEmpty(&stack)) {//栈为空且结点为 NULL 终止循环条件 while (root) {//先不断遍历左子树直到没有为止 printf(%c, root->element);//打印当前结点元素值 pushStack(&stack, root);//每经过一个结点就将接待你放入栈中 root root->left;//继续遍历下一个左孩子结点 } TNode node popStack(&stack);//经过前面循环左子树全部走完接着走右子树 root node->right; //得到右孩子重复上面的操作。 // 如果没有右孩子这里的 root 就被赋值为 NULL下一轮循环直接跳过上面的 while继续出站下一个结点找右子树 }}注在第一层 while 循环中调用isEmpty函数是因为防止到叶子结点的时候其左右孩子都为空。当叶子结点的右孩子为空时内层循环已经结束了会调用外层的 while 循环但是栈中可能还有其他元素处于非空的状态。如果依然使用 root 判断则会出错。
那么前序遍历我们了解完了接着就是中序遍历了中序遍历在顺序上与前序遍历不同前序遍历是走到哪就打印到哪而中序遍历需要先完成整个左子树的遍历后再打印然后再遍历其右子树。
我们还是以上面的二叉树为例首先需要先不断遍历左子树走到最底部但是沿途并不进行打印而是到底之后再打印所以第一个打印的是D接着由于没有右子树所以我们回到B此时再打印B然后再去看B的右结点E由于没有左子树和右子树了所以直接打印E左边遍历完成接着回到A打印A然后对A的右子树重复上述操作。所以说遍历的基本规则还是一样的只是打印值的时机发生了改变。
中序遍历左子树打印结点中序遍历右子树所以这棵二叉树的中序遍历结果为DBEACF我们可以发现一个规律就是在某个结点的左子树中所有结点其中序遍历结果也是按照这样的规律排列的比如A的左子树中所有结点中序遍历结果中全部都在A的左边右子树中所有的结点全部都在A的右边这个规律很关键后面在做一些算法题时会用到
void inOrder(TNode root){ StackNode stack; initStack(&stack); while (root || !isEmpty(&stack)) { //栈为空且结点为 NULL 终止循环条件 while (root) {//先不断遍历左子树直到没有为止 pushStack(&stack, root);//每经过一个结点就将接待你放入栈中 root root->left;//继续遍历下一个左孩子结点 } TNode node popStack(&stack);//经过前面循环左子树全部走完接着走右子树 printf(%c, node->element);//打印当前结点元素值 root node->right; //得到右孩子重复上面的操作。 // 如果没有右孩子这里的 root 就被赋值为 NULL下一轮循环直接跳过上面的 while继续出站下一个结点找右子树 }}#include <stdio.h>#include <stdlib.h>#include <stdbool.h>typedef char E;typedef struct TreeNode { E element; struct TreeNode *left, *right;} TreeNode, *TNode;typedef TNode T; //这里栈内元素类型定义为上面Node也是二叉树结点指针typedef struct StackNode { T element; struct StackNode *next;} StackNode, *SNode;//非递归操作void initStack(SNode head) { head->next NULL;}bool pushStack(SNode head, T element) { SNode node malloc(sizeof(StackNode)); if (node NULL) return 0; node->element element; node->next head->next; head->next node; return 1;}bool isEmpty(SNode head) { return head->next NULL;}T popStack(SNode head) { SNode top head->next; T e head->next->element; head->next head->next->next; free(top); return e;}void perOrder(TNode root) { StackNode stack; initStack(&stack); while (root || !isEmpty(&stack)) { //栈为空且结点为 NULL 终止循环条件 while (root) { //先不断遍历左子树直到没有为止 printf(%c, root->element); //打印当前结点元素值 pushStack(&stack, root); //每经过一个结点就将接待你放入栈中 root root->left; //继续遍历下一个左孩子结点 } TNode node popStack(&stack); //经过前面循环左子树全部走完接着走右子树 root node->right; //得到右孩子重复上面的操作。 // 如果没有右孩子这里的 root 就被赋值为 NULL下一轮循环直接跳过上面的 while继续出站下一个结点找右子树 }}void inOrder(TNode root){ StackNode stack; initStack(&stack); while (root || !isEmpty(&stack)) {//栈为空且结点为 NULL 终止循环条件 while (root) {//先不断遍历左子树直到没有为止 pushStack(&stack, root);//每经过一个结点就将接待你放入栈中 root root->left;//继续遍历下一个左孩子结点 } TNode node popStack(&stack);//经过前面循环左子树全部走完接着走右子树 printf(%c, node->element);//打印当前结点元素值 root node->right; //得到右孩子重复上面的操作。 // 如果没有右孩子这里的 root 就被赋值为 NULL下一轮循环直接跳过上面的 while继续出站下一个结点找右子树 }}int main() { TNode a malloc(sizeof(TreeNode)); TNode b malloc(sizeof(TreeNode)); TNode c malloc(sizeof(TreeNode)); TNode d malloc(sizeof(TreeNode)); TNode e malloc(sizeof(TreeNode)); TNode f malloc(sizeof(TreeNode)); a->element A; b->element B; c->element C; d->element D; e->element E; f->element F; a->left b; a->right c; b->left d; b->right e; c->right f; c->left NULL; d->left d->right NULL; e->left e->right NULL; f->left f->right NULL; perOrder(a); printf(\n); inOrder(a);}注源代码部分均可以运行复制粘贴即可。
线索二叉树目的引入线索二叉树正是为了加快查找结点前驱和后继的速度。
普通二叉树如何查找前驱和后继结点呢
确定需要找到的结点p。申请两个结点q和pre首先q指向第一个结点而pre指向null然后遍历二叉树q指向下一个结点根据先序、中序和后续的顺序pre指向q刚刚指向的结点。如此循环往复直到q指向p当p和q指针重合时pre指向p的前驱结点。当pre和p指针重合时q指向p的后继结点。实质上还是二叉树的遍历。当一个操作中需要反复寻找某个结点的前驱或者后继时这样的操作明显效率比较低。因此我们需要一种可以加快查找结点前驱和后继的速度的方法从而引入了线索二叉树。
二叉链表
typedef int Element;//二叉树的结点链式存储typedef struct BiTNode { Element data; struct BiTNode *lchild, *rchild;} BiTNode, *BiTNode;线索链表
typedef int Element;//线索二叉树结点typedef struct ThreadNode { Element data; struct BiTNode *lchild, *rchild; int ltag, rtag; //左、右线索标志} ThreadNode, *ThreadTree;tag 0表示指针指向孩子
Tag 1表示指针是“线索”
中序线索二叉树的存储
二叉树的线索化王道教材版本
//中序线索化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->rtag 1; } pre p; InThread(p->rchild, pre); }}//中序线索化二叉树Tvoid CreateInThread(ThreadTree T){ ThreadTree pre NULL; if(T ! NULL){ //非空二叉树线索化 InThread(T, pre); //线索二叉树 pre->rchild NULL; //处理遍历的最后一个结点 pre->rtag 1; }}课程版本
//中序线索化typedef char Element;//线索二叉树结点typedef struct ThreadNode { Element data; struct ThreadNode *lchild, *rchild; int ltag, rtag;} ThreadNode, *ThreadTree;//全局变量 pre指向当前访问结点的前驱ThreadNode *pre NULL;void visit(ThreadNode *q) { if (q->lchild NULL) { //左子树为空建立前驱线索 q->lchild pre; q->ltag 1; } if (pre ! NULL && pre->rchild NULL) { pre->rchild q; //建立前驱结点的后继线索 pre->rtag 1; } pre q;}void InThread(ThreadTree T){ if(T ! NULL){ InThread(T->lchild); //中序遍历左子树 visit(T); //访问根结点 InThread(T->rchild); //中序遍历右子树 }}void CreateInThread(ThreadTree T){ pre NULL; //pre初始为NULL if(T ! NULL){ //非空二叉树才能线索化 InThread(T); //中序线索化二叉树 if (pre->rchild NULL){ pre->rtag 1; //处理遍历的最后一个结点 } }}双亲表示法
这种结构采用一组连续空间来存储每个结点同时在每个结点中增设一个伪指针指示其双亲结点在数组中的位置。
双亲表示法的存储结构描述如下
#define MAX_TREE_SIZE 100 //树中最多结点数typedef int element;typedef struct { //树的结点定义 element data; //数据元素 int parent; //双亲位置域} PTNode;typedef struct { //树的类型定义 PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //结点数} PTree;优点可以很快地得每个结点的双亲结点。
缺点求结点的孩子时则需要遍历整个结构。
孩子表示法
将每个结点的孩子结点都用单链表连接起来形成一个线性结构。
优点寻找子女的操作非常直接。
缺点寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。
孩子兄弟表示法
即以二叉链表作为树的存储结构
树与二叉树的应用 哈夫曼树和哈夫曼编码定义树中结点常常被赋予一个表示某种意义的数值称为该结点的权。从树到热一结点的路径长度与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度记为
W P L ∑ i 1 n w i l i WPL \sum_{i1}^{n} w_i l_i WPLi1∑nwili
其中 w i w_i wi表示第 i i i个叶结点所带的权值 l i l_i li是该叶结点到根结点的路径长度。
哈夫曼树构造的特点
每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大。构造过程中共新建了 n − 1 n-1 n−1个结点双分支结点因此哈夫曼树的结点总数为 2 n − 1 2n-1 2n−1。每次构造都选择 2 2 2棵树作为新结点的孩子因此哈夫曼树中不存在度为 1 1 1的结点。 并查集 习题总结⚠️判断完全二叉树 n 1 n_1 n1的值 ⇔ n \Leftrightarrow n ⇔n
n 0 n 1 n 2 总结点 n n 1 0 / 1 n 0 n 2 1 n_0 n_1 n_2 总结点n\\ n_1 0/1\\ n_0 n_2 1 n0n1n2总结点nn10/1n0n21
由完全二叉树的性质可知度为 1 的结点要么只有一个要么就没有。
结合 n 0 n 2 1 n_0 n_2 1 n0n21公式可知如果 n 0 n_0 n0为偶数 ⇒ n 2 \Rightarrow n_2 ⇒n2为奇数如果 n 0 n_0 n0为奇数 ⇒ n 2 \Rightarrow n_2 ⇒n2为偶数所以 n 0 n 2 n_0 n_2 n0n2一定为奇数。
用上面解释可知 n n 0 n 1 n 2 n n_0 n_1 n_2 nn0n1n2的奇偶性与 n 1 n_1 n1有关。然而 n 1 0 / 1 n_1 0/1 n10/1。
如果 n 1 0 n_1 0 n10那么 n n n为奇数如果 n 1 1 n_1 1 n11那么 n n n为偶数反之如果 n n n为偶数那么 n 1 1 n_1 1 n11如果 n n n为奇数那么 n 1 0 n_1 0 n10。
e g : eg: eg:一棵完全二叉树上有 1001 个结点其中叶结点的个数是 ( D ) (D) (D)
A . 250 A.250 A.250 B . 500 B.500 B.500 C . 254 C.254 C.254 D . 501 D.501 D.501
解 n 1001 n 1001 n1001为奇数则 n 1 0 n_1 0 n10那么 n n 0 n 1 n 2 n 0 n 2 n 0 ( n 0 − 1 ) 2 n 0 − 1 1001 n n_0 n_1 n_2 n_0 n_2 n_0 (n_0 - 1) 2n_0 - 1 1001 nn0n1n2n0n2n0(n0−1)2n0−11001解得 n 501 n 501 n501。
e g : eg: eg:【2016年全国试题】若森林F有15条边、25个结点则F包含树的个数是 C C C
A . 8 A.8 A.8 B . 9 B.9 B.9 C . 10 C.10 C.10 D . 11 D.11 D.11
解树的结点数n边数分支数B有确定的关系 n B 1 n B 1 nB1森林是不相交的树的集合则森林的结点数 F n ∑ T i ∑ ( B i 1 ) F_n \sum T_i \sum(B_i 1) Fn∑Ti∑(Bi1)其中 T i T_i Ti就是森林中第 i i i棵树的结点数 B I B_I BI是森林中第 i i i棵树的分支。设森林中有 m m m棵树则 F n ∑ B i m F_n \sum B_i m Fn∑Bim即 25 15 m 25 15 m 2515m即森林中有10棵树。