二叉树的实现和遍历

1、二叉树基础知识：

性质1、在二叉树的第i层上至多有2^(i-1)个结点；
性质2、深度为k的二叉树至多有2^k-1个结点；
性质3、对任何一棵二叉树，如果其终端节点数为n0，度为2的结点数为n2，则n0=n2+1；
性质4、具有n个节点的完全二叉树的深度为[logn]+1 ，这里[ ]表示向下取整。
性质5、对一棵有n个节点的完全二叉树的结点按层序编号（从上往下，自左而右），则对任一结点i（1<=i<=n），有
a、如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)=[i/2]，这里[ ]表示向下取整。
b、如果2i>n，则结点i无左孩子（即终端结点），否则其左孩子LCHILD(i)=2i；
c、如果2i+1>n，则结点i无右孩子，否则其右孩子RCHILD(i)=2i+1。

二叉树的存储结构也可以有顺序存储和链式存储两种。

顺序存储适合完全二叉树，对完全二叉树进行编号，编号为i的结点存储在第(i-1)个存储单元中。但对一般二叉树采用顺序存储结构，空树也要占用存储单元，会浪费存储空间。

链式存储又包括二叉链表和三叉链表，前者有2个指针域，分别指向左、右孩子，而三叉链表有3个指针域，多出1个指向双亲结点的指针。

2、二叉树的遍历

二叉树的递归遍历算法可以分为先序遍历、中序遍历、后序遍历。假如以L、D和R分别表示遍历左子树、访问根结点和遍历右子树，则：
先序遍历：DLR
中序遍历：LDR

后续遍历：LRD

不论按哪一种次序进行遍历，对含有n个结点的二叉树，其时间复杂度均为O(n)。

3、线索二叉树（Threaded Binary Tree）

遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，这实质上是对一个非线性序列进行线性化操作，使每个结点在这个线性序列中有且仅有一个直接前驱和后继。在二叉链表中，我们只能得到每个结点的左右孩子信息，而不能得到结点在某次有序遍历中的直接前驱和后继。一个最简单的办法是在每个结点上增加两个指针域fwd和bkwd，分别指示结点在任一次序遍历时得到的前驱和后继信息，但这样做会大大降低使结构的存储密度。我们知道，含有n个结点的二叉链表存在n+1个空链域（由于n0=n2+1，因此2n0+n1=n0+n1+n2+1=n+1）。利用这些空链域存储其他有用信息，可以得到线索链表，如下图所示。