好好学习，好好记笔记。
目录1.树和二叉树的定义1.1树的定义1.2树的术语1.3二叉树的定义5.2案例引入5.3树和二叉树的抽象数据类型定义5.4二叉树的性质和存储结构5.5遍历二叉树和线索二叉树5.6树和森林
1.树和二叉树的定义树是非线性数据结构，是以分支关系定义的层次结构。
1.1树的定义树是n(n=0)个结点的有限集
空树：n=0
非空树：
有且仅有一个称之为根的结点。
除根结点外其余结点可单独成树，为根的子树。(递归定义树)
1.2树的术语结点：树中的一个独立单元。双亲和孩子：结点的子树的根是其孩子，它本身即孩子的双亲。结点的度：结点的孩子量。兄弟：同一双亲的孩子的互称。祖先：根到该结点所经分支上的所有结点。层次：代数(根为第一层，为第一代)。堂兄弟：同一层(代的结点。树的深度：又称高度，即最大层次数。有序树和无序树：从左到右看的树即有序，否则无序。森林：多棵互不相交的树的集合。
1.3二叉树的定义二叉树是一种特殊的树，但二叉树的每个结点最大度数是2。
二叉树的5个形态：
空二叉树
仅有根结点的二叉树
右子树为空的二叉树
左子树为空的二叉树
左右子树均为非空的二叉树
5.2案例引入数据压缩的问题：哈夫曼编码(详见历史推文)
利用二叉树求解表达式的值。(计算器的实现)
5.3树和二叉树的抽象数据类型定义详见课文，本笔记不做详解。
5.4二叉树的性质和存储结构5.4.1二叉树的性质
在第i层上至多有2^(i-1)个结点(i=1)。
深度为k的二叉树至多有2^k-1个结点。
叶子节点的数量总是比度为2的结点数量大1。
满二叉树：深度为k且含有2^k-1个结点的树。
完全二叉树：
叶子节点只可能在最大的两层出现。
与对应深度的满二叉树相比较，完全二叉树的结点是从右子树开始缺失的。
具有n个结点的完全二叉树的深度为[log2n]+1。
5.4.2二叉树的存储结构
顺序存储结构：常用数组存储。
链式存储结构：每个结点都会有2个指针指向孩子结点或NULL。
5.5遍历二叉树和线索二叉树5.5.1遍历二叉树
先序遍历：先访问父结点，再依次左右子结点。
中序遍历：先访问左子结点，再依次访问父节点、右子结点。
后序遍历：先依次访问左右子结点，后为父结点。
5.5.2线索二叉树
遍历二叉树后以一定的顺序将各个结点排成一个序列，一般会在保留原树结构的基础上在各个结点中新增前驱指针和后继指针。
5.6树和森林5.6.1树的存储结构
双亲表示法：结构如[data
parent]
孩子表示法：结构如[data
degree
child1..
childn"]
孩子兄弟法：结构如[lchild
data
rchild]
5.6.2森林和二叉树的转换
森林转换成二叉树：用森林的第一棵树作为根，以该树的根结点作为左子树，森林的其余树在递归成右子树。
二叉树转换为森林：以上述原理作递归。
5.6.3树和森林的遍历
树的遍历：
先根遍历
后根遍历
森林的遍历：
先序遍历
后序遍历
预览时标签不可点收录于话题#个上一篇下一篇