数据结构——二叉树的操作(遍历及树形输出).doc
《数据结构——二叉树的操作(遍历及树形输出).doc》由会员分享,可在线阅读,更多相关《数据结构——二叉树的操作(遍历及树形输出).doc(13页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、/*实验三:二叉树遍历操作验证*/#include#include#include#include#include#include#includeusing namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2int LeafNum;/叶子结点个数/定义结构体typedef struct BiTNodechar data;/存放值struct BiTNode *lchild,*rchild;/左右孩子BiTNode,*BiTree;/先序输入二叉树结点的值,空格表示空树void createBiTree(BiTree &T)c
2、har ch;/输入结点时用scanf(%c,&ch);if(ch= )/若输入空格,该值为空,且没有左右孩子T=NULL;elseT=(BiTNode *)malloc(sizeof(BiTNode);/分配结点空间if(!T)/分配失败exit(OVERFLOW);T-data=ch;/生成根结点createBiTree(T-lchild);/构造左子树createBiTree(T-rchild);/构造右子树/递归方法先序遍历二叉树void preOrderTraverse(BiTree T)if(T)/若非空if(T-data)/输出printf(%c,T-data);preOrder
3、Traverse(T-lchild);preOrderTraverse(T-rchild);/递归方法中序遍历二叉树void inOrderTraverse(BiTree T)if(T)/若非空preOrderTraverse(T-lchild);if(T-data)/输出printf(%c,T-data);preOrderTraverse(T-rchild);/递归方法后序遍历二叉树void postOrderTraverse(BiTree T)if(T)/若非空preOrderTraverse(T-lchild);preOrderTraverse(T-rchild);if(T-data)/
4、输出printf(%c,T-data);/层序遍历二叉树void LevelTraverse(BiTree T) queue q;/建队 q.push(T);/根节点入队 BiTree p; while(!q.empty() p=q.front(); /获得队列的首元素 q.pop(); /首元素出队 coutdatalchild!=NULL) /若结点的左孩子不空 q.push(p-lchild); if(p-rchild!=NULL)/若结点的右孩子不空 q.push(p-rchild); /非递归方法前序遍历二叉树void stackPreOrderTraverse(BiTree T)s
5、tack s;/建栈s.push(T);/根结点入栈BiTree p;/栈首元素while(!s.empty()while(p=s.top()&p)printf(%c,p-data);s.push(p-lchild);/左孩子入栈,直到走到尽头s.pop();/空指针出栈if(!s.empty()p=s.top();/获得栈顶元素s.pop();/出栈s.push(p-rchild);/右孩子入栈/非递归方法中序遍历二叉树void stackInOrderTraverse(BiTree T)stack s;/建栈s.push(T);/入栈BiTree p;/栈首元素while(!s.empty
6、()while(p=s.top()&p)s.push(p-lchild);/左孩子入栈,直到走到尽头s.pop();/空指针出栈if(!s.empty()p=s.top();s.pop();/出栈printf(%c,p-data);s.push(p-rchild);/右孩子入栈/非递归方法后序遍历二叉树void stackPostOrderTraverse(BiTree T)stack s;/建栈map m;/标记结点是否已经输出BiTree p;/栈首元素if(T)/若不是空树s.push(T);/根结点入栈while(!s.empty()while(true)/目的:找到后序遍历要输出的结
7、点while(p=s.top()&p-lchild&!mp-lchild)/若左孩子未输出,将左孩子入栈,直到尽头,不包括空指针s.push(p-lchild);if(p=s.top()&p-rchild&!mp-rchild)/若最左孩子的右孩子未输出且非空,则入栈s.push(p-rchild);elsebreak;/找到结点跳出循环if(p=s.top()&!mp)printf(%c,p-data);mp=true;/标记已经输出s.pop();/退栈/后序遍历求二叉树的高度递归算法int PostTreeDepth(BiTree T) int hl,hr,max;if(T!=NULL)
8、 hl=PostTreeDepth(T-lchild); /求左子树的深度 hr=PostTreeDepth(T-rchild); /求右子树的深度 max=hlhr?hl:hr; /得到左、右子树深度较大者 return(max+1); /返回树的深度 else return(0); /如果是空树,则返回0/*按竖向树状打印的二叉树代码是为了实现二叉树的横向显示问题。 这种树形要求先打印右子树,再打印根,最后打印左子树,顺序恰为逆中序顺序。 这种输出格式,结点的左右位置与结点的层深有关, 故算法中设置了一个表示当前根节点层深的参数,以控制输出结点的左右位置。 */void PrintTree
9、(BiTree T,int nLayer) int i; if(T=NULL) return; PrintTree(T-rchild,nLayer+1); for(i=0;idata); PrintTree(T-lchild,nLayer+1);/叶子结点的个数以及元素int TreeLeaf(BiTree T) if(T) if(!T-lchild&!T-rchild) LeafNum+; coutdatalchild); TreeLeaf(T-rchild);return LeafNum;int main()BiTree T;/定义结点int layer=0;/层数while(true)c
10、out输入二叉树结点值空格表示空树:endl;createBiTree(T);cout递归先序遍历:;preOrderTraverse(T);coutendl;cout递归中序遍历:;inOrderTraverse(T);coutendl;cout递归后序遍历:;postOrderTraverse(T);coutendl;cout层序遍历:;LevelTraverse(T);coutendl;cout非递归先序遍历:;stackPreOrderTraverse(T);coutendl;cout非递归中序遍历:;stackInOrderTraverse(T);coutendl;cout非递归后序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 二叉 操作 遍历 树形 输出
限制150内