我所理解的二杈树 二杈树的一个最大特点是只有两个儿子，这为它的运算带来极大方便。 二杈树的存储方式有三种：顺序存储，链接存储和线索存储。顺序存储最简单，用数组就能实现，但它要求二杈树必须是一棵完全二杈树，这种情况很少见，所以用的不多。链接存储是很常见的方法，我将着重介绍。 链接存储的二杈树类型和结构定义如下：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 = NULLdepth(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);}

评论