数据结构——二叉树的操作(遍历及树形输出).doc

《数据结构——二叉树的操作(遍历及树形输出).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/*实验三：二叉树遍历操作验证*/#include#include#include#include#include

2、tBiTNode*lchild,*rchild;//左右孩子}BiTNode,*BiTree;//先序输入二叉树结点的值，空格表示空树voidcreateBiTree(BiTree&T){charch;//输入结点时用scanf("%c",&ch);if(ch=='')//若输入空格，该值为空,且没有左右孩子{T=NULL;}else{T=(BiTNode*)malloc(sizeof(BiTNode));//分配结点空间if(!T)//分配失败{exit(OVERFLOW);}T->data=ch;

3、//生成根结点createBiTree(T->lchild);//构造左子树createBiTree(T->rchild);//构造右子树}}//递归方法先序遍历二叉树voidpreOrderTraverse(BiTreeT){if(T)//若非空{if(T->data){//输出printf("%c",T->data);}preOrderTraverse(T->lchild);preOrderTraverse(T->rchild);}}//递归方法中序遍历二叉树voidinOrderTraverse

4、(BiTreeT){if(T)//若非空{preOrderTraverse(T->lchild);if(T->data){//输出printf("%c",T->data);}preOrderTraverse(T->rchild);}}//递归方法后序遍历二叉树voidpostOrderTraverse(BiTreeT){if(T)//若非空{preOrderTraverse(T->lchild);preOrderTraverse(T->rchild);if(T->data){//输出printf("%

5、c",T->data);}}}//层序遍历二叉树voidLevelTraverse(BiTreeT){queueq;//建队q.push(T);//根节点入队BiTreep;while(!q.empty()){p=q.front();//获得队列的首元素q.pop();//首元素出队cout<data<<"";//输出结点的值if(p->lchild!=NULL)//若结点的左孩子不空{q.push(p->lchild);}if(p->rchild!=NULL)//若结点的右孩

6、子不空{q.push(p->rchild);}}}//非递归方法前序遍历二叉树voidstackPreOrderTraverse(BiTreeT){stacks;//建栈s.push(T);//根结点入栈BiTreep;//栈首元素while(!s.empty()){while((p=s.top())&&p){printf("%c",p->data);s.push(p->lchild);//左孩子入栈,直到走到尽头}s.pop();//空指针出栈if(!s.empty()){p=s.t

7、op();//获得栈顶元素s.pop();//出栈s.push(p->rchild);//右孩子入栈}}}//非递归方法中序遍历二叉树voidstackInOrderTraverse(BiTreeT){stacks;//建栈s.push(T);//入栈BiTreep;//栈首元素while(!s.empty()){while((p=s.top())&&p){s.push(p->lchild);//左孩子入栈,直到走到尽头}s.pop();//空指针出栈if(!s.empty()){p=

8、s.top();s.pop();//出栈printf("%c",p->data);s.push(p->rchild);//右孩子入栈}}}//非递归方法后序遍历二叉树voidstackPostOrderTraverse(BiTreeT){stacks;//建栈mapm;//标记结点是否已经输出BiTreep;//栈首元素if(T)//若不是空树{s.push(T);//根结点入栈}while(!s.empty()