我所理解的二杈树
二杈树的一个最大特点是只有两个儿子，这为它的运算带来极大方便。
二杈树的存储方式有三种：顺序存储，链接存储和线索存储。顺序存储最简单，用数组就
能实现，但它要求二杈树必须是一棵完全二杈树，这种情况很少见，所以用的不多。链接存储
是很常见的方法，我将着重介绍。
链接存储的二杈树类型和结构定义如下：
typedef struct bnode
{
ElemType data;
struct bnode *lchild, *rchild;
} btree;
链接存储的二杈树的基本运算包括遍历二杈树和输出二杈树。其中根据访问根结点的不同
次序又可以分为先序，中序和后序遍历。我将分别用递归和非递归的算法实现这三种不同遍历
过程。
1。递归算法
先序遍历
void preorder(btree *p)
{
if(p != NULL)
{
printf("%d", p->data);//输出该结点（根结点）
preorder(p->lchild); //遍历左子树
preorder(p->rchild);//遍历右子树
}
}
中序遍历
void inorder(btree *p)
{
if(p != NULL)
{
inorder(p->lchild); //遍历左子树
printf("%d", p->data);//输出该结点
inorder(p->rchild); //遍历右子树
}
}
后序遍历
void postorder(btree *p)
{
if(p != NULL)
{
postorder(p->lchild); //遍历左子树
postorder(p->rchild); //遍历右子树
printf("%d", p->data);//输出该结点
}
}
2。非递归算法（使用栈存储树）
先序遍历
void preorder(btree *bt)
{
btree *p, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=0;
if(bt != NULL)//先判断是否为空树
{
stack[top] = bt; //根结点入栈
while(top >= 0)
{
p = stack[top--]; //栈顶元素出栈
printf("%d", p->data);//输出该结点
if(p->rchild != NULL) //如果该结点有右孩子，将右孩子入栈
{
stack[++top] = p->rchild;
}
if(p->lchild != NULL) //如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈
{
stack[++top] = p->lchild;
}
}
}
}
中序遍历
void inorder(btree *bt)
{
btree *p=bt, *stack[MAX]; //p表示当前结点，栈stack[]用来存储结点
int top=0;
if(p != NULL) //先判断是否为空树
{
while(top >= 0)
{
if(p != NULL) //先处理结点的左孩子结点
{
stack[top++] = p; //当前结点入栈
p = p->lchild; //寻找左孩子结点
}
else //找到最左边的孩子结点后
{
if(top == 0) //表示全部元素均已输出，结束输出
break;
p = stack[--top];//栈顶元素出栈
printf("%d", p->data); //输出该结点
p = p->rchild; //处理其右孩子结点
}
}
}
}
或者：
void inorder(btree *bt)
{
btree *p=bt, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=-1;
do
{
while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
p = p->lchild;
}
if(top >= 0) //所有左孩子处理完毕后
{
p = stack[top--];//栈顶元素出栈
printf("%d", p->data); //输出该结点
p = p->rchild; //处理其右孩子结点
}
} while((p != NULL)||(top >= 0));
}
后序遍历
void postorder(btree *bt)
{
btree *p=bt, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int tag[MAX];
int top=-1;
do
{
while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
tag[top] = 0;
p = p->lchild;
}
if(top >= 0) //所有左孩子处理完毕后
{
if(!tag[top]) //如果当前结点的右孩子还没被访问
{
p = stack[top];//输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点
p = p->rchild; //处理其右孩子结点
tag[top] = 1; //表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出
}
else //如果该结点的左右孩子都被访问过了
{
printf("%d", stack[top--]->data); //栈顶元素出栈，输出该结点，此时结点p指向NULL
}
}
} while((p != NULL)||(top >= 0));
}
应用：假设二杈数采用链接存储结构进行存储，root指向根结点，p所只结点为任一的结点，
编写一个求出从根结点到p所指结点之间路径的函数。
算法思路：本题采用非递归后序遍历树root，当后序遍历访问到p所指结点时，此时stack[]
所有元素均为p所指结点的祖先，由这些祖先便构成了一条从根结点到p所指结点的路径。
void Path(btree *bt, btree *p)
{
btree *p=bt, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int tag[MAX];
int top=-1, i;
do
{
while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
tag[top] = 0;
p = p->lchild;
}
if(top >= 0) //所有左孩子处理完毕后
{
if(!tag[top]) //如果当前结点的右孩子还没被访问
{
p = stack[top];//输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点
p = p->rchild; //处理其右孩子结点
tag[top] = 1; //表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出
}
else //如果该结点的左右孩子都被访问过了
{
if(stack[top] == p)
{
printf("The path: ");
for(i=0; i<=top; i++) //输出从栈底到栈顶的元素构成路径
printf("%c ", stack[i]->data);
break;
}
top--;
}
}
} while((p != NULL)||(top >= 0));
}
输出二杈树
给定一个二杈树，输出其嵌套括号表示。
采用的算法是：首先输出根结点，然后再依次输出它的左子树和右子树，不过在输出左子树
之前要打印左括号，在输出右子树之前后要打印右括号；另外，依次输出左，右子树要至少
有一个不为空，若都为空则不输出。
因此，输出二杈树的递归函数如下：
void Print(btree *bt)
{
if(bt != NULL)
{
printf("%d", bt->data);
if(bt->lchild!=NULL || bt->rchild!=NULL)
{
printf("(");
Print(bt->lchild);
if(bt->rchild!=NULL)
printf(",");
Print(bt->rchild);
printf(")");
}
}
}
求二杈树的深度：
若一棵二杈树为空，则其深度为0，否则其深度等于左字树和右子树中最大深度加1，即有如下
递归模型：
depth(b) = 0 若 b = NULL
depth(b) = max(depth(b->lchild),depth(b->rchild)+1 其他
因此，求二杈树的深度的递归函数如下：
int depth(btree *bt)
{
int dep1, dep2;
if(bt == NULL)
return 0;
dep1 = depth(p->lchild);
dep2 = depth(p->rchild);
return (dep1 > dep2)?(dep1+1):(dep2+1);
}
评论