树和二叉树
树描述
树是一种比较特别的数据结构，它与常见的链表，队列，栈等线性结构不同，它是非线性数据结构。最为常见的就是二叉树，其次还有B，B+树等变种，基本都是采用父亲孩子节点的方式，以下简单举个例子。
图1 高度为4的二叉树
对于如上所示的树，它的每一个节点最多有两个孩子，故它被称为二叉树。
- 父亲和孩子
具体说来87,45,78分别有两个孩子；32只有一个孩子；09,17,65,53称为叶子节点，它的孩子为空。45叫做87的左孩子，78叫做右孩子。
- 结点的度
结点的孩子的个数叫做结点的度。例如87的度为2，32的度为1。树中结点的最大度数叫做树的度。
- 叶子结点
度为0的结点为叶子结点。如图中的17,65,53,09。
- 结点的高度
从树的叶子结点开始自底向上叠加的。如图中的32结点的高度为2。
- 结点的深度
从树的根结点开始自顶向下。如图中32结点的深度为3。
- 树的高度(深度)
树中所有结点的最大高度。
- 特殊性质：令度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，则n0=n2+1。
证明：由于无环连接图的性质，结点的0个数等于边数加1，度为i的结点对应的边的个数为i。故所有的结点个数n = n0 + n1 + n2 = n1*1+ n2*2 + 1 解得n0=n2+1
二叉树的存储表示
顺序存储结构
如上所示的二叉树，可以按照顺序放入到一个连续的数组中。
|
索引 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
值 |
XX |
87 |
45 |
78 |
32 |
17 |
65 |
53 |
09 |
一定注意：上文的树刚好是完全二叉树的形式，故而可以在顺序数组中连续存储。如果它非完全的，例如17这个节点不存在，那个17对应的位置仍然会占用，一般被置为一个无意义的值即可。因此这种存储结构对比较稠密的二叉树比较合适，即完全二叉树和满二叉树。对于一个高度为H，只有右单分支的二叉树它仍然需要2^H-1个存储单元。
链式存储结构
| lchild | data | rchild |
链式存储结构避免了顺序存储结构空间利用率较低的问题，它对于每一个结点一般存储3个属性。
需要注意二叉树并不一样要只使用这三个属性，具体实现有时为了访问父亲的方便，还可以增加一个指向父亲的指针。链式存储结构举例如下，
图2 图的链式存储结构
如上图所示，结点A有两个孩子B和C，因此的lchild指向B，rchild指向C，data为A结点的值。对于结点C，它是叶子结点，两个孩子为空指针。
链式结构描述：
typedef
char TElemType;
typedef
struct BTreeNode
{
struct
BTreeNode* lchild;//左孩子
struct
BTreeNode* rchild;//右孩子
TElemType
data;//结点数据
}BTreeNode,*BTree;
二叉树的遍历
树的遍历是一种非常重要的算法，它是解决很多树的相关性质的问题的关键。例如求树的高度，树的宽度，树的结点深度，树的叶子节点的个数，树的节点的所有父亲，树是否相似等等的问题，都最终可以转化为树的遍历问题。掌握了树的遍历问题，可以说是掌握了二叉树的相关算法的精髓，这个是武功的内功心法，得其法则招式万变不离其中，各种复杂招式都会迎刃而解。
总体框架描述
树的遍历从大框架上分为两种，深度优先和宽度优先。深度优先强调的一直向树的深处即叶子节点去挖掘，直到不能挖掘的时候才返回；树的宽度优先也就是树的层次遍历，是按照树的层次一层一层的遍历。这个与图论的相关算法是有相似之处的。
以下举例仍以上面的图形为例
深度优先遍历算法
先序遍历
基本描述
先序遍历也就是先根遍历，先访问根节点，然后访问根节点的左孩子，再访问根节点的右孩子。注意它是一个递归形式，在访问根节点左孩子的时候，左孩子又可以看成是一个树，同样继续刚才的步骤。上图的先序遍历为ABDEC。先遍历根节点A，然后遍历A的左子树，由于左子树又可以看作是一棵树的形式，因此对这棵树仍然执行先序遍历，先遍历左子树的根B，然后遍历B的左孩子。同样对于B的左孩子继续先序遍历，只有一个节点D，先遍历D，然后遍历左孩子和右孩子，由于为空，故什么也不做。然后开始回退遍历B的右孩子E，然后继续回退遍历A的右孩子C。故而遍历顺序为ABDEC。
操作过程
1,如果树为空则什么也不做
2,访问根节点
3,先序遍历左子树
4,先序遍历右子树
实现代码
void
PreOrderTraverse(BTrees)
{
if(s !=NULL){
printf("%c ", (s)->data);
PreOrderTraverse(s->lchild);
PreOrderTraverse(s->rchild);
}
}
中序遍历
基本描述
中序遍历也就是中根遍历，先访问根节点的左孩子，然后访问根节点，再访问根节点的右孩子。注意它是一个递归形式，在访问根节点左孩子的时候，左孩子又可以看成是一个树，同样继续刚才的步骤。中序遍历的访问顺序为DBEAC，采用与先序同样的分析策略即可。
操作过程
1,如果树为空则什么也不做
2,中序遍历左子树
3,访问根节点
4,中序遍历右子树
实现代码
void
InOrderTraverse(BTrees)
{
if(s !=NULL){
InOrderTraverse(s->lchild);
printf("%c ", (s)->data);
InOrderTraverse(s->rchild);
}
}
后序遍历
基本描述
后序遍历也就是后根遍历，先访问根节点的左孩子，然后访问根节点的右孩子，再访问根节点。注意它是一个递归形式，在访问根节点左孩子的时候，左孩子又可以看成是一个树，同样继续刚才的步骤。中序遍历的访问顺序为DEBCA，采用与先序同样的分析策略即可。
操作过程
1,如果树为空则什么也不做
2,后序遍历左子树
3,后序遍历右子树
4,访问根节点
实现代码
void
PostOrderTraver(BTrees)
{
if(s !=NULL){
PostOrderTraver(s->lchild);
PostOrderTraver(s->rchild);
printf("%c ", (s)->data);
}
}
宽度优先遍历算法(层序遍历算法)
基本描述
层次遍历采用的非递归形式的遍历策略，使用队列辅助实现。首先将根节点入队列。然后逐个出队列并访问，同时对于每个访问过的结点，再将它的所有非空孩子入队列。层次遍历的访问顺序为ABCDE。
操作过程
1,如果树非空，将根入队列
2,当队列非空
2.1,循环出队列并访问
2.2,入队它的所有非空的孩子
实现代码
int
LevelTraverse(BTrees)
{
LinkQueue
Q;
InitQueue(&Q);
if(s !=NULL)
{
EnQueue(&Q,s);
while (!
IsQueueEmpty(&Q))
{
DeQueue(&Q,&s);
TreeVisit(s);
if (s->lchild !=NULL){
EnQueue(&Q,s->lchild);
}
if(s->rchild !=NULL){
EnQueue(&Q,s->rchild);
}
}
}
DestroyQueue(&Q);
return
SUCCESS;
}
遍历的一些特性
先序遍历和中序遍历，后序和中序，层序和中序都可以唯一的确定一棵二叉树。例如对于上述的图的序列：
PreOrderTraverse: a b d e c
InOrderTraverse: d b e a c
PostOrderTraver: d e b c a
LevelTraverse: a b c d e
先序每一次访问的都先是，然后才是它的孩子。中序的根在中间，左孩子在左边，右孩子在右边。后序的根在最后。层序的是按层次访问，第一个是根。
考虑到本文的特性，不便于过于扩展，就仅仅拿先序和中序来举例，后面如果有可能的话，我会写一个专门的程序来将先序序列和中序序列转换成一棵确定的二叉树。看到先序a，得a是树的根。再看中序序列a的位置，中序中的a将序列分为两个部分，dbe和c，那么可以得出a的左孩子为dbe，右孩子为c。然后在看dbe。在先序中dbe的顺序为bde，那么可知b应该为a的左孩子的根，从而可以用b在中序遍历的序列去拆分dbe，可以拆成d和e。因此可得b的两个孩子为d，e。从而可以得出确定的一棵二叉树。不管采用什么遍历，树的左孩子的节点序列一定在右孩子节点的前面，这是由于上面的四种遍历都是先访问左孩子，再访问右孩子的。
后面要继续的内容
二叉树的非递归遍历
非递归先序遍历
非递归中序遍历
非递归后序遍历
二叉树的先序构建(中序和后序与它类似)
线索二叉树
线索二叉树的基本描述
线索二叉树的构建
线索二叉树的遍历
二叉树遍历的的基本用途及实例算法
如何求树的高度
如何求树的宽度
如何求树的叶子节点
如何求树的指定节点的所有父亲
如何求树的两个节点的最近的公共父亲，或者是所有公共父亲
如何求树的相似
如何求树的度为1的节点个数
如何将通过先序和中序的遍历序列构建树
如何删除一个指定节点子树