【自考】数据结构第四章树和二叉树，期末不挂科指南，第6篇
章节简介
前5篇博客写的都是线性结构，对于有层级结构的数据需要用树形结构来描述
本章的重要知识点
- 理解有关树的基本概念和二叉树的基本概念
- 掌握二叉树的存储结构以及遍历方法
- 掌握树的存储结构以及树、森林、二叉树的相互转换方法
- 梳理掌握哈夫曼树构造方法和哈夫曼编码的设计方法
树的基本概念
核心一句话
线性结构中一个结点至多只有一个直接后继，树形结构一个结点可以有一个或多个直接后继
认识树
看图即可，你要能区分出来哪些是树，哪些不是树
树的相关术语
结点的度：树上任意结点所拥有的子树的数目称为该结点的度
叶子：度为0的结点称为叶子或者终端结点
- 树的度：一棵树中所有结点的度的最大值称为该树的度，就是把所有结点的度求和
结点的层次：从根算起，根的层次为1，其余结点的层次为其双亲的层次加1
- 树的高度：一棵树中所有结点层次数的最大值称为该树的高度或
深度 还有一些小概念：有序树、无序树
树的相关术语，一定要一开始就明确清晰，后面才好学习
二叉树
官方概念：二叉树是n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并且这两棵子树之间有次序关系，交换位置就成为一棵不同的二叉树。
左子树和右子树，也有的叫做左孩子和右孩子
二叉树五种基本形态，方块表示子树
二叉树的基本运算（不写代码，了解重点函数即可）
- 初始化
- 求双亲
- 求左孩子
- 求右孩子
- 建二叉树
- 先序遍历！！！
- 中序遍历！！！
- 后序遍历！！！
- 层次遍历！！！
先序遍历，中序遍历，后序遍历在考试中一般不要求手写代码，但是需要你能通过一棵树结构，输出最终的结果，这个博客结尾给大家看一下例题
二叉树性质（很重要，细碎知识点很多）
性质1：二叉树第i(i≥1)层上至多有2^i-1^个结点。
不需要死记硬背，实际需要的时候画一个二叉树就可以求出来了
性质2：深度为k（k≥1）的二叉树至多有2^k^-1个结点
依旧可以推导出来
深度为1的二叉树 结点最多为1
深度为2的二叉树 结点最多为3
深度为3的二叉树 结点最多为7
深度为k的二叉树 结点最多为2^k^-1
性质3：对任何一棵二叉树，若度数为0的结点（叶结点）个数为n~0~，度数为2的结点个数为n~2~，则n~0~ = n~2~+1
这个性质需要稍微推导一下
先回答一个问题，你知道树的度数，怎么计算树的结点数
例如 树的度数为2，结点树为几，这个不难想象，会出现如下情况
看到这里不难发现，存在一个公式为 树的度数+1=树的结点树
那么我们开始推导上述公式
假设 二叉树的0度，1度，2度结点个数为n~0~，n~1~，n~2~，结点总数为t
t = n~0~+n~1~+n~2~
树的度数+1 = t
树的度数怎么求？n~0~0+n~1~1+n~2~2 是树的度数
继续n~0~0+n~1~1+n~2~2 +1 = t = n~0~+n~1~+n~2~
===> 2n~2~+1=n~0~+n~2~
===>n~0~=n~2~+1
好了，上述过程，争取看明白吧
性质4：含有n个结点的完全二叉树的深度为