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

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

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

2、ructBiTNode*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->da

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

4、rTraverse(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){/

5、/输出printf("%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

6、!=NULL)//若结点的右孩子不空{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

7、(!s.empty()){p=s.top();//获得栈顶元素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();//空

8、指针出栈if(!s.empty()){p=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()