考研复习Day 16 | 数据结构与算法 --树与二叉树（上）

一、树的基本概念1.1 树的定义树nn≥0个结点的有限集。当 n0 时称为空树当 n1 时其余结点可分为 m 个互不相交的有限集每个集合本身又是一棵树称为根的子树树的定义是递归的——在定义中引用了自身因此树是一种典型的递归数据结构。树的逻辑特征特征说明根结点没有前驱唯一其他结点有且仅有一个前驱所有结点可拥有零个或多个后继重要结论在包含 n 个结点的树中恰好存在n-1 条边。1.2 基本术语以图5.1中的树为例根A子结点B、C、D...术语说明示例祖先从根到某结点路径上的所有结点B是K的祖先子孙某结点子树中的所有结点K是B的子孙双亲路径上最接近该结点的结点E是K的双亲孩子双亲的直接后继K是E的孩子兄弟具有相同双亲的结点K与L互为兄弟堂兄弟双亲位于同一层的结点G与E、F、H、I、J互为堂兄弟结点的层次根为第1层其孩子为第2层以此类推结点的深度结点所在的层次树的高度深度树中结点的最大层数结点的高度以该结点为根的子树的高度结点的度结点的孩子个数树的度树中所有结点的度的最大值分支结点非终端结点度 0 的结点叶结点终端结点度 0 的结点有序树子树从左到右有固定次序不可互换无序树子树无固定次序路径从一个结点到另一个结点所经过的结点序列路径长度路径上边的数目森林mm0棵互不相交的树的集合森林与树的关系将树的根结点移除后其各子树构成一个森林反之为m棵独立的树添加一个新结点作为共同根森林便转化为一棵树。1.3 树的性质性质公式说明结点数与度数的关系n 总度数 1除根结点外每个结点都有唯一双亲度为m的树第i层最多结点数m^(i-1)第1层1个第2层m个第3层m²个...高度为h的m叉树最多结点数(m^h - 1)/(m - 1)各层结点数达到最大时度为m、n个结点的树最小高度树应尽可能饱满度为m、n个结点的树最大高度n - m 1至少一个结点有m个孩子其他层仅一个结点二、二叉树的概念2.1 二叉树的定义及其主要特性二叉树每个结点至多拥有两棵子树不存在度大于2的结点且子树有明确的左右之分次序固定不可交换。二叉树的5种基本形态空二叉树只有根结点只有左子树只有右子树左右子树都有二叉树与度为2的有序树的区别度为2的树至少3个结点二叉树可以为空度为2的有序树中只有一个孩子时无须区分左右二叉树中左右位置是结构本身的固有属性2.2 几种特殊的二叉树特殊二叉树定义特点满二叉树高度为h包含2^h-1个结点每一层结点数都达到最大所有叶结点在最下一层除叶结点外每个结点度均为2完全二叉树高度为hn个结点与满二叉树中编号1~n的结点一一对应叶结点只出现在最后两层最多只有一个度为1的结点二叉排序树左子树所有结点 根结点 右子树所有结点左右子树本身也是二叉排序树平衡二叉树任意结点左右子树高度差绝对值 ≤ 1—正则二叉树每个分支结点均有2个孩子树中仅有度为0或2的结点完全二叉树的编号性质编号从1开始性质公式最后一个分支结点编号⌊n/2⌋结点i的双亲编号⌊i/2⌋i1结点i的左孩子编号2i若存在结点i的右孩子编号2i1若存在结点i所在层次⌊log₂i⌋ 1完全二叉树高度⌈log₂(n1)⌉或⌊log₂n⌋ 12.3 二叉树的性质性质公式说明叶子结点与度为2的结点关系n₀ n₂ 1非空二叉树第k层最多结点数2^(k-1)k≥1高度为h的二叉树最多结点数2^h - 1—性质1的证明设n₀、n₁、n₂分别为度为0、1、2的结点数n n₀ n₁ n₂。分支数B n - 1 n₁ 2n₂代入得n₀ n₂ 1。2.4 二叉树的存储结构1. 顺序存储结构使用一组连续的存储单元按层序自上而下、自左至右存储二叉树结点。适用场景完全二叉树和满二叉树最适用能最大限度节省存储空间。缺点一般二叉树需插入“空结点”补全为完全二叉树形状最坏情况单支树需要近2^h-1个存储单元空间利用率极低。建议从数组下标1开始存储保证数组下标与结点编号一致。2. 链式存储结构二叉链表typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;重要结论在含有n个结点的二叉链表中共有n1个空链域常考选择题。三、二叉树的遍历3.1 三种递归遍历遍历方式访问顺序遍历序列图5.7二叉树先序遍历PreOrder根 → 左 → 右1,2,4,6,3,5中序遍历InOrder左 → 根 → 右2,6,4,1,3,5后序遍历PostOrder左 → 右 → 根6,4,2,5,3,1递归算法模板// 先序遍历 void PreOrder(BiTree T) { if (T ! NULL) { visit(T); // 访问根结点 PreOrder(T-lchild); PreOrder(T-rchild); } } // 中序遍历 void InOrder(BiTree T) { if (T ! NULL) { InOrder(T-lchild); visit(T); InOrder(T-rchild); } } // 后序遍历 void PostOrder(BiTree T) { if (T ! NULL) { PostOrder(T-lchild); PostOrder(T-rchild); visit(T); } }时间复杂度O(n)每个结点访问一次空间复杂度O(h)递归工作栈深度等于树高最坏情况O(n)3.2 层次遍历借助队列从上到下、从左到右逐层访问。void LevelOrder(BiTree T) { Queue Q; InitQueue(Q); BiTree p T; if (p ! NULL) EnQueue(Q, p); while (!QueueEmpty(Q)) { DeQueue(Q, p); visit(p); if (p-lchild ! NULL) EnQueue(Q, p-lchild); if (p-rchild ! NULL) EnQueue(Q, p-rchild); } }3.3 由遍历序列构造二叉树核心原则必须知道中序序列再辅以先序、后序或层序中的任意一种才能唯一确定一棵二叉树。已知序列组合是否能唯一确定二叉树先序 中序能后序 中序能层序 中序能先序 后序不能先序 层序不能后序 层序不能构造方法组合方法先序中序先序第一个为根 → 在中序中划分左右子树 → 递归后序中序后序最后一个为根 → 在中序中划分左右子树 → 递归层序中序层序第一个为根 → 在中序中划分左右子树 → 层序中后续结点依次为各子树的根四、线索二叉树4.1 线索二叉树的基本概念背景在n个结点的二叉树中有n1个空链域。利用这些空指针指向遍历序列中的前驱或后继称为线索化。结点结构标志位含义ltag 0lchild指向左孩子ltag 1lchild指向前驱线索rtag 0rchild指向右孩子rtag 1rchild指向后继线索存储结构定义typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; } ThreadNode, *ThreadTree;4.2 中序线索二叉树的构造设pre指向刚刚访问过的结点p指向当前正在访问的结点。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); // 递归线索化右子树 } } void CreateInThread(ThreadTree T) { ThreadTree pre NULL; if (T ! NULL) { InThread(T, pre); pre-rchild NULL; // 处理最后一个结点 pre-rtag 1; } }4.3 中序线索二叉树的遍历找中序第一个结点ThreadNode *FirstNode(ThreadNode *p) { while (p-ltag 0) p p-lchild; // 最左下结点 return 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); }4.4 先序和后序线索二叉树遍历方式查找后继的复杂度先序线索较简单有左孩子则左孩子为后继否则右孩子为后继否则线索直接指向后序线索较复杂需要知道双亲信息通常需用三叉链表后序线索查找后继的三种情况情况后继结点是根后继为空结点是双亲的右孩子或是双亲的左孩子且双亲无右孩子后继为双亲结点是双亲的左孩子且双亲有右子树后继为右子树中后序第一个结点五、思考1. 树 ≈ 文件系统电脑文件夹结构就是一棵树根目录是根结点子文件夹是子树文件是叶子结点。2. 递归遍历 ≈ 俄罗斯套娃每打开一个套娃里面还有一个更小的套娃直到最小的那个空树。递归就是这种“自己包含自己”的结构。3. 层次遍历 ≈ 逐层打印就像BFS广度优先搜索一层一层地处理先处理根再处理所有孩子再处理所有孙子。4. 线索二叉树 ≈ 链表的“快速跳转”把二叉树变成链表一样的结构遍历时不需要递归直接沿着线索走。注以上内容参考 2027年数据结构考研复习指导 王道论坛 组编其中有一些个人想法如有任何错误或不妥欢迎各位大佬指出如果各位有一些有意思的想法也可以和我交流一下~感谢六、一点题外话学习了二叉树脑海中不由得浮现出了中学学过的一篇课文美国诗人罗伯特·弗罗斯特创作的《未选择的路》黄色的树林里分出两条路可惜我不能同时去涉足我在那路口久久伫立我向着一条路极目望去直到它消失在丛林深处。但我却选了另外一条路它荒草萋萋十分幽寂显得更诱人、更美丽虽然在这条小路上都很少留下旅人的足迹虽然那天清晨落叶满地两条路都未经脚印污染。啊留下一条路等改日再见但我知道路径延绵无尽头恐怕我难以再回返。也许多少年后在某个地方我将轻声叹息把往事回顾一片树林里分出两条路而我选了人迹更少的一条因此走出了这迥异的旅途。1. 二叉树的结构 人生的“分岔点”每一个选择都是一个结点选择的结果决定你走向哪一棵子树。我们的人生就是一棵巨大的、不断生长的二叉树。每一个自己都是由无数次“左拐还是右拐”塑造出来的。2. 路径的“不可逆性” 人生没有撤回键“啊留下一条路等改日再见但我知道路径延绵无尽头恐怕我难以再回返。”二叉树中一旦你选择了左子树就无法再回到父结点去走右子树除非有父指针。人生也一样你选择了一条路就不可能同时体验另外那条路。这就是选择的代价也是选择的庄严。3. “成功路不止一条” 二叉树有多条路径到达叶结点“这些路径中有很多都是可以通向成功的成功的路不止一条。”二叉树中从根到任何一个叶结点的路径都是一条完整的、独特的旅途。没有哪条路径是“标准答案”也没有哪条路径是“绝对的错误”。只要最终到达了你想去的“叶结点”这条路径就是对的。4.“受挫折时想二叉树”受到挫折时候想一想二叉树只要没有结束就永远会有翻盘的机会。二叉树的高度 ≠ 成功的早晚二叉树中从根到叶结点的路径长度可以完全不同有的叶结点在第3层早早成功有的叶结点在第10层大器晚成只要还没到NULL放弃你就还在遍历中。人生就像是二叉树是在无数次的选择中成长的选择决定了我是怎么样的一个我。只要没有结束永远会有翻盘的机会。这些路径中有很多都是可以通向成功的成功的路不止一条。七、明日计划树与二叉树下— 树、森林与二叉树的转换、哈夫曼树