实验四树的遍历

《实验四树的遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验题目:树的遍历实验描述：从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。程序设计：#defineok1#defineerror0#defineoverflow-1#include#includetypedefstructBitnode{chardata;structBitnode*lchild,*rchild;}Bitnode,*Bitree;/*定义树中结点的类型*/intvisit(

2、chare){printf(“％c”,e);returnok;}/*定义visit函数*/BitreeCreat_Tree(){charc;BitreeT;佯定义二叉树的根结点勺c=getchar();/*输入字符*/if(c==-)T二NULL;/*如果第一个字符是“”，则该二叉树为空树*/else{T=(Bitree)malloc(sizeof(Bitnode));if(!T)exit(overflow);/*如果不是，为该结点分配空间*/T->data=c;T->lchild=Creat_Tree();/*对左子树进

3、行递归调用Creat_Tree函数*/T->rchild=Creat_Tree();/*对右子树进彳亍递归调用Creat_Tree函数*/}returnT;/*返冋该二叉树的根结点*/}/*按前序序列输入构造一棵二叉树函数*/intpreordertraverse(BitreeT){if(T){if(visit(T->data))/*先访问根结点*/if(preordertraverse(T->lchild))/*再递归访问该结点的左子树*/if(preordertraverse(T->rchild))returnok;/

4、*再递归访问该结点的右子树*/returnerror;}elsereturnok;}/*前序访问二叉树函数*/intinordertraverse(BitreeT){if(T){if(inordertraverse(T->lchild))/*先递归访问该结点的左子树*/if(visit(T->data))/*再访问根结点*/if(inordertraverse(T->rchild))returnok;/*再递归访问该结点的右子树*/retunierror;}elsereturnok;}/*屮序访问二叉树函数*/intlas

5、tordertraverse(BitreeT){if(T){if(lastordertraverse(T->lchild))/*递归访问该结点的左子树*/if(lastordertraverse(T->rchild))/*再递归访问该结点的右子树*/if(visit(T->data))returnok;/*递归访问该结点的左子树*/returnerror;}elsereturnok;}/*后序访问二叉树函数*/main(){BitreeT;/*定义二叉树根结点*/T=Creat_Tree();/*调用构造二叉树函数*/pr

6、eordertraverse(T);/*前序输出该二叉树*/printf(Hn);inordertraverse(T);/*屮序输出该二叉树*/printf(Hn);lastordertraverse(T);/*后序输出该二叉树*/printf(HH);}/*函数执行完毕*/测试数据：输入ABC巾巾DE巾G巾巾Fd)d)d)(其中d)表示空格字符)输出:先序:ABCDEGF屮序：CBEGDFA后序：CGEFDBA［选作内容］采用非递归算法实现二叉树遍历。程序设计：#include#includ

7、e#defineM20typedefstructnode}〃链式存储的指针类型和结点定义chardata;structnode*lchild,*rchild;JBTnode;BTnode*create()//建立二叉树{BTnode*t;charch;scanf(”％c",&ch);if(ch==*')t=NULL;elset=(BTnode*)malloc(sizeof(BTnode));t->data=ch;t->lchild=create();t->rchild=create();}returnt

8、;}/*屮序遍历二叉树*/voidInorder(BTnode*t){inti=0;BTnode*s[M];do{while(t!=NULL){s[i++]=t;t=t->lchild;}if(i>0){t=s[-i];printf("%ct't->data);t=t->rchild;}}while