《算法与数据结构基础》学习笔记05_01——非线性结构_树、二叉树、二叉树的遍历 《声明 本文章只是本人个人学习笔记，如有错误，欢迎批评指正 以下是本人自学的视频数据结构与算法基础（青岛大学-王卓）_哔哩哔哩_bilibili 概要： 树（Tree）————非线性结构，结点有1个前驱，多个后继。由根（Root）和子树（SubTree）组成二叉树————最简单的树，每个结点最多能有2个孩子，且孩子分为左右子树（即使只有1个孩子也要分）满二叉树、完全二叉树是特殊的二叉树：编号从上到下，从左到右，中间不存在空结点，适合顺序存储二叉树的存储结构：顺序二叉树、二叉链表(左右指针域)遍历二叉树：分三种形式：先序遍历DLR、中序遍历LDR、后序遍历LRD，不同遍历方式的树结点前后后者不同遍历二叉树一般用递归实现，且遍历二叉树是二叉树实现其他算法的基础线索二叉树——将二叉链表的n+1个左右空指针利用上 非线性结构 树型————1对多（1个前驱，多个后继)图————多对多（多个前驱，多个后继) 5.1 树 树(Tree)——n个结点。递归定义：由根（Root）和子树（SubTree）组成
树的其他表现形式
5.1.2 树的基本术语 根结点————树的最外层的结点，即最开头的结点，其无前驱树的深度（高度）————结点的最大层次结点的度————结点拥有的子树数（分支树）树的度————树内所有结点的度的最大值终端结点（叶子）————度=0的结点非终端结点（除根结点外的非终端结点也称 内部结点）————度不为0的结点结点的双亲————结点的前驱结点结点的孩子————结点的后继结点兄弟结点————有共同双亲（共同前驱）的结点堂兄弟结点————属于同一层的结点，兄弟结点一定是堂兄弟结点结点的祖先————该结点一直往前的所有前驱结点，直到根结点结点的子孙————该结点的一直往后的所有后继。根结点的子孙：除根结点自身外的所有结点
有序树————各子树从左至右排序（最左边为第一个孩子），不能调换顺序。如上图T_1,T_2,T_3左右顺序不可调换无序树————子树顺序随意，可以调换。如上图T_1,T_2,T_3左右顺序可调换森林————m棵不相交的树的集合。一棵单独的树也是一个森林
5.1.3 树结构和线性结构的比较3 
5.2 树——二叉树 二叉树————结点的度最多为2的树，孩子分别叫左子树、右子树，孩子的顺序不能互换 二叉树可以是空集合，且左右子树可以为空树 为什么要研究二叉树：一般的树很复杂，而二叉树是最简单的树，规律性强。任何树都可与二叉树相互转换 注意：二叉树与树的最主要差别（也因其而是两者概念不同）————即使只有一个孩子，二叉树也要定义该孩子是左子树还是右子树；看下图例子
5.2.2 二叉树的5种基本形态 
5.2.3 二叉树的性质 性质1：二叉树在第
层最多有 个结点，最少有 1 个结点
性质2：深度为 的二叉树，最多有 个结点，最少有 个结点。 性质3：二叉树的总边数 ，总结点数 ，度2结点数 ，度1结点数 ，度0结点(叶子)数 。 总边数 总结点数 叶子数 与 度2结点数的关系：
5.2.4 特殊的二叉树——满二叉树、完全二叉树 5.2.4.1 满二叉树 满二叉树：所有结点都在的树。即深度 ，有 个结点的二叉树 满二叉树特点：每一层都满， 层结点数为 叶子结点全部在底层编号规则：从上到下，从左到右
5.2.4.2 完全二叉树 完全二叉树：结点编号和同深度的满二叉树相同的二叉树。满二叉树是特殊的完全二叉树 完全二叉树特点：编号规则————从上到下，从左到右结点确缺失规则————从最后一个结点开始，从右到左，下到上缺失叶子分布————最底层or倒数第二层对任意结点，左子树的层数=右子树层数or比右子树层数多1。（如下图A结点的左子树层数为2，右子树层数为1）
完全二叉树的性质具有 个结点的完全二叉树的深度 。（补充: ：表示不大于x的最大整数，即floor(x)）完全二叉树的编号关系：结点编号 ，则其双亲结点编号为 ，左孩子编号 ,右孩子编号
5.2.5 二叉树的顺序存储 1.按编号存储：从上到下，从左到右，表示数组下标 2.注！！！：即使子树为空，也为其编号，但是该数组位置存储空。目的就是使数组下标与树编号一一对应，可根据数组恢复二叉树原样
3.二叉树顺序存储类型定义 4.二叉树顺序存储缺点：对于非满二叉树，浪费空间大。适合完全二叉树 5.2.6 二叉树的链式存储——二叉链表 1.二叉链表2个指针域：左右孩子指针无头结点，头指针直接指向第一结点（根结点）n 个结点的二叉链表，有 n+1 个空指针域
2.二叉树链式存储类型定义 3.补充：三叉链表 新增个指针域：指向前驱
5.3 遍历二叉树 遍历————顺着一条路径巡访二叉树的结点，每个结点访问一次 二叉树的遍历通过递归实现 5.3.2 三种遍历方式 子树按照：从左到右遍历DLR————先根（序）遍历，根左右LDR————中根遍历，左根右LRD————后根遍历，左右根 将二叉树拆分成 逐级递减的二叉树，依次执行上述操作 执行到下一结点后都要重新开始执行3个操作，而不是直接访问该结点 1.先序遍历——根左右
2.中序遍历 右图：将BEL是A的左子树，所以BEL访问后才A才右子树；同样，E的左子树访问完后（为空），才E，才右子树L；
3.后序遍历 右图：二叉树拆分 拆分A：BEL——A——DHMIJ 拆分B：EL——B——空 拆分E：空——E——L——————【按照左右根的方式输出LE EL输出完后，按照左右根的方式输出B BEL输出完后，按照左右根的方式输出，右子树是DHMIJ，需要拆分 拆分D：HMI——D——J 拆分H：M——H——I——————【按照左右根的方式输出MIH H输出完后，按照左右根的方式输出，JD（注：若J还有子树，则还需再之前拆分J） D输出完后，输出A
例题：二叉树表示算数表达式
5.3.3 已知遍历次序反推二叉树 【已知先序、中序】or 【已知中序、后序】，可以确定二叉树；【已知先序、后序】，不能确定二叉树 1.【已知先序、中序】 先序：判断根结点（首端为根结点） 中序：判断左右子树
2.【已知中序、后序】 后序：判断根结点（末尾为根结点） 中序：判断左右子树
5.3.4 遍历二叉树的实现——递归算法 存储结构：二叉链表 实现方式：递归遍历 三种访问共性：访问路径相同，只是访问时机不同 时间复杂度 ————每个结点只访问依次 最大空间复杂度 ————递归到最远，栈占用最大辅助空间 1.【先序遍历 DLR】
2.【中序遍历 LDR】
3.【后序遍历 LRD】
5.3.5 遍历二叉树的实现——非递归算法 【中序遍历LDR】为例 实现方式——栈
5.3.6 二叉树的层次遍历 按照编号遍历：从上到下，从左到右 实现方式：队列 （根结点入队、结点出队、出队结点的孩子入队）
5.3.7 遍历二叉树的应用 1.【二叉树的建立——递归遍历实现】 遍历的操作：先序遍历，输入结点的信息，若输入#表示该结点为空
2.【二叉树的复制——递归遍历实现】 已知二叉树，将其复制一份 3.【计算二叉树深度——递归遍历实现】 当前结点的深度：计算左子树深度、和右子树深度，取大者+1（通过递归的回调计算上方结点的深度）
4.【计算二叉树结点总数——递归遍历实现】 当前二叉树结点总数：左子树结点总数+右子树结点总数+1（通过递归的回调计算大二叉树的结点总数） 5.【计算二叉树的叶子结点数——递归遍历实现】 当前二叉树叶子结点总数：左子树结点总数+右子树结点总数（通过递归的回调计算大二叉树的叶子数）——<和题4相比不用+1> 5.4 线索二叉树 二叉链表一定有n+1个空的指针域 1.利用二叉链表的n+1个指针域——线索化：某结点左孩子为空，则左指针指向其前驱某结点有孩子为空，则右指针指向其后继注意！！：上述规则的前驱和后继与前序、中序、后序遍历有关
2.线索二叉树（Threaded Binary Tree）——线索化后的二叉树 线索二叉树的二叉链表还需增设2个标志域 ltag，rtag——用于标识指向孩子还是前驱后继ltag = 0——lchild指向左孩子；ltag = 1——lchild指向前驱rtag = 0——rchild指向右孩子；rtag =1——rchild指向后继 3.线索二叉树的定义
补充：线索二叉树仍然会有空指针，可以增设头结点，让这些空结点指向头结点，类似于循环链表
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/40066.html
