树和二叉树

一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。

基本术语：

树结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；

兄弟结点：同一双亲的孩子结点；

堂兄结点：同一层上结点；

结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的高（深）度：树中最大的结点层

结点的度：结点子树的个数

树的度： 树中最大的结点度。

叶子结点：也叫终端结点，是度为0的结点；

分枝结点：度不为0的结点（非终端结点）；

森林：互不相交的树集合；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；

二叉树

二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。注意区分：二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树

二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。

二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是两种不同的结构。

性质：

在二叉树的第 i 层上至多有2i-1个结点。

深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）

对任何一棵二叉树，若它含有n0个叶子结点、n2个度为 2 的结点，则必存在关系式：n0= n2+1。

具有 n 个结点的完全二叉树的深度为⎣log2 n⎦+1 。

n个结点的二叉树中，完全二叉树具有最小的路径长度。

如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1<=i<=n),有：

如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲的编号是 i/2(整除）。

如果2i>n，无左孩子；否则，其左孩子是结点2i。

如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。

二叉树的存储结构

顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质5确定。

二叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点，总的指针是n+2

在有n个结点的二叉链表中，值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-(N-1)=N+1个为空链域。

二叉链存储法也叫孩子兄弟法，左指针指向左孩子，右指针指向右兄弟。而中序遍历的顺序是左孩子，根，右孩子。这种遍历顺序与存储结构不同，因此需要堆栈保存中间结果。而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符，因此不需要用堆栈。

遍历二叉树和线索二叉树

遍历二叉树：使得每一个结点均被访问一次，而且仅被访问一次。非递归的遍历实现要利用栈。

先序遍历DLR：根节点->左子树->右子树

中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序

后续遍历LRD：左子树->右子树->根节点。需要栈的支持。

层次遍历：用一维数组存储二叉树时,总是以层次遍历的顺序存储结点。层次遍历应该借助队列。

线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。

如何线索化？以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之前走过的点，不是下一将要去往的点。

加上结点前趋后继信息（结索）的二叉树称为线索二叉树。n个结点的线索二叉树上每个结点有2个指针域（指向左孩子和右孩子），总共有2n个指针域；一个n个结点的树有n-1条边，那么空指针域= 2n - (n-1) = n + 1，即线索数为n+1。指针域tag为0，存放孩子指针，为1，存放前驱/后继节点指针。

线索树下结点x的前驱与后继查找：设结点x相应的左（右）标志是线索标志，则lchild(rchild)就是前驱(后继），否则：

LDR–前驱：左子树中最靠右边的结点；后继：右子树中最靠左边的结点

LRD–前驱：右子树的根，若无右子树，为左子树跟。后继：x是根，后继是空；x是双亲的右孩子、x是双亲的左孩子，但双亲无右孩子，双亲是后继；x是双亲的左孩子，双亲有右孩子，双亲右子树中最左的叶子是后继

DLR–对称于LRD线索树—将LRD中所有左右互换，前驱与后继互换，得到DLR的方法。

为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点，约定：

头结点的lchild域：存放线索链表的根结点指针；

头结点的rchild域: 中序序列最后一个结点的指针；

中序序列第一结点lchild域指向头结点;

中序序列最后一个结点的rchild域指向头结点;

中序遍历的线索二叉树以及线索二叉树链表示意图

一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是1。前序和后续线索化后空链域个数都是1，中序是2。二叉树在线索化后，仍不能有效求解的问题是前序求前序先驱，后序求后序后继。

中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。在中序线索二叉树中,每一非空的线索均指向其祖先结点。

在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历,此时，不需栈，也不需递归。基本步骤：

p=T->lchild; p指向线索链表的根结点；

若线索链表非空，循环：

循环，顺着p左孩子指针找到最左下结点；访问之；

若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环： p=p->rchild； 并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）

一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使 p指向右孩子结点；