树和二叉树的定义
树的定义
树 属于1：n的形式，属于非线性结构
有且仅有一个根，其余的都是子树
而字树也有自己的根和子树，所以，树是一个递归的定义
结点的度：结点拥有的子树的个数，或者是分支的个数，或者是指针的个数
度=0：叶子
度！=0：分支节点或者叫内部节点
树的度：各节点度的最大值
树的深度：最大的层数（根节点为第一层），图中树的深度是四层
孩子：结点子树的根结点
双亲：与孩子反过来
例如：B是A的孩子；A是B的双亲
子孙：某节点子树中的任一个结点
祖先：从根到该结点所“途径"的"所有“结点，例如，H的祖先是A、D
一棵树也是森林，把一棵树的根结点去掉，就变成了三棵树，就是一个普通的森林，
森林加上一个双亲结点，就变成了一颗树
线性结构和树形结构的比较
二叉树的定义
起因
定义
注意 子树有左右之分，并且次序不能颠倒，根可以有空的左右子树
注意
二叉树：哪怕其中一个子树是空的 那么另一个子树也得在自己位置 并且区分左右
树：不区分左右，其中一个子树为空时，另一个只有一个位置
案例引入
前缀码编码
表达式的实现
二叉树的抽象类型定义
创建二叉树时，根据definition来构造 而definition的值分别对应着三个不同的遍历方式
二叉树的性质和存储结构
二叉树的性质
直接假设二叉树是满二叉树 也就是直接计算最多情况下的结点数，就是“至多”的结点数
第i层 那就是求等比数列的常数项 也就是a1*（q的n-1次方） a1是1
每层至少一个
等比数列求和
一共最少有k个
度为2：也就是有两个孩子的结点
证明：1.以总边数为桥梁
2.从下往上分析：每个结点头上都连着一个边，只有根结点没有，所以 总边数B=n-1（n是总结点数）
3.从上往下分析：B=2n2+1n1
（n2、n1、分别表示度为2和度为1的结点数）
4.以B为桥梁 带入n=n2+n1+n0
二叉树的特殊形式
满二叉树
满二叉树 必须每个位置都有结点 每层都要满 叶子结点必须都在最后一层
完全二叉树
要从满二叉树中连续的去掉元素而不修改 也就是编号位置不能变 结点中存放的元素也不能变 就是将完全二叉树映射到满二叉树时 没有异常的地方 可以残缺 但不可以异常 并且 一定要从左往右是连续的 不能有缺口
完全二叉树的两个性质
因为是完全二叉树 去掉最后一层 就是满二叉树 补全最后一层 也是满二叉树 所以 可以利用满二叉树的性质来构造一个不等式，
去掉最后一层 就是满二叉树 那么不等式左边就是k-1层时的总结点数
补全最后一层 就是满二叉树 那么不等式右边就是k层时的总结点数
之后简化不等式 最后一步将小于号改成去小于x的最大整数
因为是完全二叉树 去掉最后一层 就是满二叉树 补全最后一层 也是满二叉树 所以 可以利用满二叉树的性质来构造一个不等式，之后简化不等式 最后一步将小于号改成去小于x的最大整数
总结来说 除了根结点
其他结点：双亲结点的编号是【i/2】
左孩子结点是2i
右孩子结点是2i+1
如果左右孩子的编号超出了最大结点数 那么就是孩子不存在
二叉树的存储结构
顺序存储结构
按照满二叉树的位置定义编号 再定义一个数组 编号对应数组下标
空值 数组位置不能缩进 仍然保留 数值为空
所以就造成了空间的浪费
链式存储结构
一般会有一个头指针指向根结点，上面的结构体是对结点的定义
除了根节点 其他结点一定有双亲 那么每个双亲肯定会牺牲一个链域来存放孩子的地址 所以 空指针数目是2n-（n-1）
遍历二叉树
简介
分类
遍历每一个子树时 将子树也按照整棵树的遍历方式遍历 ，也就是以根结点为参考 转换根结点的参考
先序
先以整个树为参考 先访问根结点
之后访问左子树：这时将左子树的B 看成根结点 继续采用先序的访问方式来访问B的左子树 依次类推 直到访问到左右子树为空的叶子结点 从而完成对左子树的访问
最后访问右子树：这时将右子树中的D看成根结点 继续采用先序的访问方式来访问D的左子树 依次类推递归 直到访问到左右子树为空的叶子结点 从而完成对右子树的访问
中序
先访问左子树：这时将左子树的B 看成根结点 继续采用先序的访问方式来访问B的左子树 依次类推 直到访问到左右子树为空的叶子结点 从而完成对左子树的访问
后序
案例
根据序列确定二叉树
只知道先序序列和后序序列是无法唯一确定一颗二叉树的
先序+中序
由先序确定根，中序确定左右子树
对于左右子树 再根据先序确定左右子树的根 之后 再根据中序确定子树的左右子树，依次类推
后序+中序
遍历二叉树的算法实现
先序
遍历的过程如右图所示 只要结点不为空 就访问根结点和左右子树 即使是叶子结点 也会去访问左右子树 将叶子结点视为与其他节点一致 这样方便代码操作
链表算法
注意要判断是否为空 这是结束递归的关键条件
这里的访问根结点 是一种泛型的描述 访问根结点可以是输出 可以是修改 等操作
访问左右子树时 仍然调用该方法 实现递归调用
层层递归 当某一层有返回值时 会返回到上一层 之后继续执行上一层没有执行完的操作，例如图中由绿色变成蓝色 就是经历了一次函数返回
当最终全部返回完毕之后 主程序完成 遍历完成
在一次次的递归中 每个节点都会被当作根结点一次 所以每个结点都会被具体访问操作一次
注意要设置跳出的条件 考虑跳出的条件时 要考虑基本单元 或者说 最深处 具备怎样的条件就可以跳出了
中序后序
算法分析
每个结点经过三次 但是每个结点只访问一次
最大存储空间 O(n) 经过某结点但是不访问但是还要返回来时 就需要存储该结点的地址
非递归算法实现（栈和队列）
中序遍历
对于中序遍历的特性 可以利用栈的特点 来进行非递归算法的实现
p指向了B B不为空 压栈 之后 访问B的左孩子 为空 出栈根结点B
B被出栈 之后q指针指向出栈元素 访问其data 并且得到出栈元素的右孩子 交给p 进一步在局部进行判断
D的左孩子为空 出栈
后进先出 先进后出
while的判断条件是 当p不为空 或者 当栈还有元素时 都要进行循环
if（p）之后是p不为空的时候执行的操作
而else是p为空 栈还有元素执行的操作
p是一个遍历指针 也是一个边界指针 几乎每个地方都要走一遍
而q指向出栈的结点 q只负责输出数据以及得到出栈结点的右孩子并交给p 进一步遍历
到最后 p指向最后一个叶子结点的左孩子 并且所有元素被出栈 循环结束
层次遍历算法
从根节点开始入队 之后也是根结点出队 根结点出队时 如果其有左右孩子 那么左右孩子入队 之后左孩子出队 出队时 如果他有左右孩子 那么左右孩子入队 之后右孩子出队 出队时 如果他有左右孩子 那么左右孩子入队 依次类推
每次只考虑下面一层 不考虑下面两层或者更深
示意图
算法代码
首先是队列的定义算法 先定义一个数组 之后定义队头和队尾指针 队尾指针指向队尾元素的下一个元素 并且少存放一个元素 用来区分空队列和满队列
层次遍历算法
循环判断条件 队不为空 那么就循环继续
其中 进队时的操作方法体中 p指针是指队头元素 因为是队列 所以输出是从队头输出
因为每个元素出队进队都是针对于自己一个元素单独完成操作，所以只关注头元素即可
遍历二叉树的算法应用
建立二叉树
如果想唯一确定一个二叉树 那么由之前的学习可知 必须两种顺序遍历结合 先序+中序 或者 后序+中序
现在只有一个先序 所以无法唯一确定一个二叉树 所以这里对每个末端结点加两个空指针，从而可以唯一确定一个二叉树
算法实现
这里T是引用参数
引用参数以及指针参数传递时 虽然形参与实参是同步的 但是形参与实参的变量名 可以不一致
对于&T 引用类型 是形参与实参共用一块地址 形参相当于是实参的另一个名字
指针参数就是传递地址
复制二叉树
仍然采用递归的方式 传入两个参数 一个是新树 一个是旧树 依次判断是否为空 依次赋值即可
递归 层层向下深入 之后一层层向上返回 可以通过画图来理解
计算树的深度
最深的值再+1
因为要加上根结点那层的深度
计算树的结点个数
返回值是左+右+1
因为根结点没有参与运算 所以要+1
计算叶子结点个数
首先看最后一行返回值 是返回左子树+右子树
所以 接下来递归的时候 是叶子结点就返回1 不是就返回0 这样 就可以进入最后一行进行加法运算 运算完之后返回上一级 再次进行加法运算即可 之后层层返回 层层运算
并且不会丢下结点 因为每一级都是带着该级下运算完的结果 返回上一级进行运算
总结
递归算法 先将视野放到最开始的一层 写出算法逻辑 其他层一般情况下是与最开始的一层保持一致
同时要注意返回值返回什么 可以返回表达式 或者一个变量值 总之 返回值是连接上下层的纽带 非常重要
线索二叉树
问题提出：这里所说的某个系列中二叉树结点的前驱和后继 是指 将二叉树的结点写成一行时 他的前面以及后面元素分别是什么
每个结点（除了根结点）上面都有链条连接 所以 他们都是孩子 所以有n-1个
从树上看是否为空结点
从遍历的结果看谁是谁的前驱和后继
切忌从树上看谁是谁的前驱后继
设一个标记域 用以区分左右指针到底指向的是前驱还是后继
增设一个头结点 头指针（定义的时候就有了 同时也是链表的名字）指向该头结点 左边设为0 表示指向根结点 右边设为1 表示是一个线索 指向最后一个结点
之后 遍历出来的第一个结点的前驱指向新增的头结点 以及最后一个结点的后继指向头结点
树和森林
树（区分于二叉树 这个更有普遍性）
表示方式
双亲表示法
算法实现
上面定义结点类型 每个结点除了数据域之外 还要有一个标志域 用来指向双亲结点在数组中的下标
下面定义树结构 包括一个数组 用来存放结点数据（数据+双亲位置）
以及两个变量用来表示根结点的位置以及结点的个数
孩子链表
将孩子结点排列起来 组成一个线性链表 每个结点都有孩子链表（叶子的孩子链表为空表）
首先将数据元素的数据存放在一个数组里 每个元素对应一个数组下标
之后添加firstchild域 用来指向“其孩子下标组成的链表的第一个孩子元素”，也就相当于是链表的头指针存放域
算法描述
孩子结点结构 也就是上面的孩子下标组成的链表的结点 包括两部分：孩子的下标 指向下一个下标的指针
双亲结点结构：双亲的数据 以及指向孩子下标组成的链表的头指针 类型与其结点的类型一致（也就是孩子结点结构）
树结构仍然是一个双亲结点组成的数组以及两个变量
因为不方便找双亲 所以可以每个数组结点再增加一个域 用来存放其双亲的位置
孩子兄弟表示法（最为常用）
可以按照需要 添加双亲结点
类似于二叉树的结点结构 只不过第一个指针域存指向第一个“孩子” 第二个指针指向他自己的“兄弟”
如下图图示
如何查找某个结点
先顺着左指针到第二层 之后顺着右指针可以在当前层查找
可以 以右斜45度的线为一层 越往下层数加一 看哪些路径可以到某个层数，比如到第三层 可以从A的左指针 也可以从C的左指针
树和二叉树的转换
二者在计算机中的存储方式是一样的 都是二叉链表 只不过解释不一样 一个是左孩有兄 一个是左孩右孩 所以解释出来的树长的不一样
树->二叉树
口诀：长兄如父
二叉树->树
森林和二叉树的转换
森林->二叉树
核心思想 先将森林中的每一颗树转换成二叉树 之后 再把每个二叉树连起来 并规定第一棵树是根结点
二叉树->森林
树和森林的遍历
树的遍历
（相比于二叉树 少了中序遍历）
文章来源：https://www.toymoban.com/news/detail-620670.html
森林的遍历
（相比于二叉树的遍历 没有层次遍历和后序遍历 这里注意 二叉树 树 森林 不要混淆 三者分别有自己的遍历分类）
（注：如果对森林中的每一个树都进行后序遍历 那么得到的结果跟“森林的中序遍历得到的结果”一样）
文章来源地址https://www.toymoban.com/news/detail-620670.html
到了这里，关于数据结构---树和二叉树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
