二叉树

非线性结构：树和图
树：是一种递归定义的递归结构，重要的非线性结构。
深度：树中结点最大层次的值。（结点最多的那一层层）
结点：树中的元素及若干指向其子树的分支。
结点度：一个结点拥有的子树数目。（本身结点）。
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
对于任意二叉树，如果n0、n1、n2分别表示度数为0,1,2的结点树，则有n0=n2+1（不理解，求解答？）

满二叉树

总结点个数 2^k -1 （k为深度，若为3，则结果为7）

完全二叉树：除最后最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干结点
是效率很高的结构，堆就是这种结构

完全二叉树

非完全二叉树图为下：

非完全二叉树.jpg

二叉树的储存方式：顺序结构、链式结构

二叉树遍历：（以满二叉树图为例）

1.先序遍历：先遍历根节点，再遍历左子树，再遍历右子树（1245367）
2.中序遍历：先遍历左子树，再遍历根节点，再遍历右子树（4251637）
3.后续遍历：先遍历左子树，再遍历右子树，再遍历根节点（4526731）

线索二叉树：（解决二叉树遍历时困难的问题）

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。
对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。
一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；
二是利用二叉树的空链指针。

线索二叉树应用明天继续。