数据结构实验
（一） 实验题目：遍历二叉树。
请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。
（二） 实验分析：
本次试验是要实现对二叉树的遍历。为此，我们必须根据输入的前序序列构造出一棵二叉树，然后对该二叉树进行前序、中序、后序遍历。构造该二叉树时，如果第一个字符为“*”，则该二叉树为空树，否则将该字符存入根结点，然后对二叉树的左右子树分别递归调用该函数。先序遍历二叉树时，先对根结点进行访问，然后对其左右子树分别递归调用该函数，直至访问结束。则该程序完毕。
（三） 实验步骤：
# define ok 1
# define error  0
# define overflow  -1
# include<stdio.h>
# include<stdlib.h>
typedef struct Bitnode
{char  data;
struct Bitnode  *lchild,*rchild;
}Bitnode,*Bitree;    /*定义树中结点的类型*/
int visit(char e)
{printf("%c",e);
return ok;     
}      /*定义visit函数*/
Bitree Creat_Tree(){
  char c;
  Bitree T;      /*定义二叉树的根结点*/
  c=getchar();      /*输入字符*/
  if(c=='*')T=NULL;      /*如果第一个字符是“*”，则该二叉树为空树*/
  else {T=(Bitree)malloc(sizeof(Bitnode));
              if(!T) exit(overflow);      /*如果不是，为该结点分配空间*/
              T->data=c;
T->lchild=Creat_Tree();    /*对左子树进行递归调用先序中序后序遍历二叉树Creat_Tree函数*/
T->rchild=Creat_Tree();    /*对右子树进行递归调用Creat_Tree函数*/
            }
return T;        /*返回该二叉树的根结点*/
}      /*按前序序列输入构造一棵二叉树函数*/   
int preordertraverse(Bitree T)
{if(T){
if(visit(T->data))    /*先访问根结点*/
  if(preordertraverse(T->lchild))    /*再递归访问该结点的左子树*/
    if(preordertraverse(T->rchild))  return ok;    /*再递归访问该结点的右子树*/
return error;
  }
else return ok;
}        /*前序访问二叉树函数*/
int inordertraverse(Bitree T)
{if(T){
      if(inordertraverse(T->lchild))      /*先递归访问该结点的左子树*/
        if(visit(T->data))    /*再访问根结点*/
          if(inordertraverse(T->rchild))  return ok;    /*再递归访问该结点的右子树*/
      return error;
      } 
else return ok;
}      /*中序访问二叉树函数*/
int lastordertraverse(Bitree T)
{if(T){
    if(lastordertraverse(T->lchild))    /*递归访问该结点的左子树*/
      if(lastordertraverse(T->rchild))      /*再递归访问该结点的右子树*/
        if(visit(T->data))    return ok;      /*递归访问该结点的左子树*/
return error;
  }
else return ok;
}      /*后序访问二叉树函数*/
main()
{Bitree T;      /*定义二叉树根结点*/
T=Creat_Tree();      /*调用构造二叉树函数*/
preordertraverse(T);  /*前序输出该二叉树*/
printf("\n");
inordertraverse(T);    /*中序输出该二叉树*/
printf("\n");
lastordertraverse(T);  /*后序输出该二叉树*/
printf("\n");
}      /*函数执行完毕*/
（四） 试验结果：                                                                                                         
         
     
（五） 试验总结：
本次试验着重考查我们对二叉树理论知识的学习及实际使用的情况。首先是如何构造一棵树，注意对二叉树结点的定义，然后是对二叉树的几种遍历方式，我们必须搞清楚几种遍历的区别，还应该注意到几种遍历的共性，熟悉这几种调用方式。
在本次试验中，我们应该认识到递归调用在函数中好处，在该程序中，递归在好几处中用到，使函数变得简洁易懂，这是我们在这次实验中应该掌握学习的。
这次试验我们应该对二叉树有一个更加深刻的认识，对以后的学习一定会产生深远的影响。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。