二叉树的实现(C语言).doc

#include#includestruct Tree;typedef Tree* BinTree;typedef char BinTreeNode;struct Treechar data;BinTree left; BinTree right; ;BinTree createEmptyBinTree(void) /创建一棵空的二叉树。BinTree p;p=(BinTree)malloc(sizeof(Tree);return p;int isNull ( BinTree t ) /判断二叉树t是否为空。if(t=NULL)printf(此二叉树为空！n);return 0;else return 1;BinTree consBinTree()/建立一棵二叉树，其根结点是root，左右二叉树分别为left和rightBinTree root; char ch; scanf(%c,&ch); if (ch=A&ch=a&chdata=ch; root-left=consBinTree(); root-right=consBinTree(); elseroot=NULL; return root;BinTreeNode root( BinTree t )/返回二叉树t的根结点。若为空二叉树，则返回一特殊值。if(t=NULL)return NULL;elsereturn t-data;void visit(BinTreeNode c)printf(%c ,c);BinTree leftChild( BinTree t )/返回t结点的左子树，当指定结点没有左子树时，返回一个特殊值。if(t-left=NULL)return NULL;elsereturn t-left;BinTree rightChild( BinTree t)/返回p结点的右子树，当指定结点没有右子树时，返回一个特殊值。if(t-right=NULL)return NULL;elsereturn t-right;void preOrder( BinTree t)/显示先根周游序列 if(t!=NULL)visit(root(t);preOrder(leftChild(t);preOrder(rightChild(t);void inOrder(BinTree t)/显示中根周游序列if (t!=NULL)inOrder(leftChild(t);visit(root(t);inOrder(rightChild(t);void postOrder(BinTree t)/显示后根周游序列if (t!=NULL) postOrder(leftChild(t);postOrder(rightChild(t);visit(root(t);void show(BinTree t,int len)/数的形状 if (t!=NULL) show(t-right,len+1); for (int i=1;idata); show(t-left,len+1); int main()BinTree p1;int k=1,num; while(k)printf(n&输入序号执行相应操作&n);printf( 输入1，建立一个二叉树！ n);printf(-n);printf( 输入2，查看建立的二叉树！n);printf(-n);printf( 输入3，先根周游二叉树！n);printf(-n);printf( 输入4，中根周游二叉树！n);printf(-n);printf( 输入5，后根周游二叉树！n);printf(-n);printf( 输入其他，退出操作！n);printf(-n);scanf(%d,&num); switch (num)case 1 :while(!(p1=consBinTree()printf(请按照先根顺序输入二叉树元素(大小写字母),空格代表子树为空n);if(p1)printf(二叉树建立成功！n);elseprintf(二叉树建立失败！n); break;case 2 : printf(建立的二叉树形状为：nn);if(isNull(p1)show(p1,0); break; case 3 : printf(先根周游序列为：n); preOrder(p1); printf(n); break; case 4 : printf(中根周游序列为：n); inOrder(p1); printf(n); break;case 5 : printf(后根周游