《数据结构——二叉树的操作(遍历及树形输出).doc》由会员分享，可在线阅读，更多相关《数据结构——二叉树的操作(遍历及树形输出).doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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非递归后序
11、遍历：;stackPostOrderTraverse(T);coutendl; cout叶子结点为：; cout叶子结点个数为：TreeLeaf(T)endl;cout树的的深度：;layer=PostTreeDepth(T);coutlayerendl;cout二叉树的树形结构图：endl;PrintTree(T,layer);return 0;/*实验三：二叉树遍历操作验证*/#include#include#include#include#include#include#includeusing namespace std;#define OK 1#define ERROR 0#defi
12、ne OVERFLOW -2int LeafNum;/叶子结点个数/定义结构体typedef struct BiTNodechar data;/存放值struct BiTNode *lchild,*rchild;/左右孩子BiTNode,*BiTree;/先序输入二叉树结点的值，空格表示空树void createBiTree(BiTree &T)char ch;/输入结点时用scanf(%c,&ch);if(ch= )/若输入空格，该值为空,且没有左右孩子T=NULL;elseT=(BiTNode *)malloc(sizeof(BiTNode);/分配结点空间if(!T)/分配失败exit(
13、OVERFLOW);T-data=ch;/生成根结点createBiTree(T-lchild);/构造左子树createBiTree(T-rchild);/构造右子树/递归方法先序遍历二叉树void preOrderTraverse(BiTree T)if(T)/若非空if(T-data)/输出printf(%c,T-data);preOrderTraverse(T-lchild);preOrderTraverse(T-rchild);/递归方法中序遍历二叉树void inOrderTraverse(BiTree T)if(T)/若非空preOrderTraverse(T-lchild);i
14、f(T-data)/输出printf(%c,T-data);preOrderTraverse(T-rchild);/递归方法后序遍历二叉树void postOrderTraverse(BiTree T)if(T)/若非空preOrderTraverse(T-lchild);preOrderTraverse(T-rchild);if(T-data)/输出printf(%c,T-data);/层序遍历二叉树void LevelTraverse(BiTree T) queue q;/建队 q.push(T);/根节点入队 BiTree p; while(!q.empty() p=q.front();
15、 /获得队列的首元素 q.pop(); /首元素出队 coutdatalchild!=NULL) /若结点的左孩子不空 q.push(p-lchild); if(p-rchild!=NULL)/若结点的右孩子不空 q.push(p-rchild); /非递归方法前序遍历二叉树void stackPreOrderTraverse(BiTree T)stack s;/建栈s.push(T);/根结点入栈BiTree p;/栈首元素while(!s.empty()while(p=s.top()&p)printf(%c,p-data);s.push(p-lchild);/左孩子入栈,直到走到尽头s.p
16、op();/空指针出栈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()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-
17、rchild);/右孩子入栈/非递归方法后序遍历二叉树void stackPostOrderTraverse(BiTree T)stack s;/建栈map m;/标记结点是否已经输出BiTree p;/栈首元素if(T)/若不是空树s.push(T);/根结点入栈while(!s.empty()while(true)/目的：找到后序遍历要输出的结点while(p=s.top()&p-lchild&!mp-lchild)/若左孩子未输出，将左孩子入栈，直到尽头，不包括空指针s.push(p-lchild);if(p=s.top()&p-rchild&!mp-rchild)/若最左孩子的右孩子未
18、输出且非空，则入栈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) hl=PostTreeDepth(T-lchild); /求左子树的深度 hr=PostTreeDepth(T-rchild); /求右子树的深度 max=hlhr?hl:hr; /得到左、右子树深度较大者 return(max+1); /返回树的
19、深度 else return(0); /如果是空树，则返回0/*按竖向树状打印的二叉树代码是为了实现二叉树的横向显示问题。 这种树形要求先打印右子树，再打印根，最后打印左子树，顺序恰为逆中序顺序。 这种输出格式，结点的左右位置与结点的层深有关， 故算法中设置了一个表示当前根节点层深的参数，以控制输出结点的左右位置。 */void PrintTree(BiTree T,int nLayer) int i; if(T=NULL) return; PrintTree(T-rchild,nLayer+1); for(i=0;idata); PrintTree(T-lchild,nLayer+1);/叶
20、子结点的个数以及元素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)cout输入二叉树结点值空格表示空树：endl;createBiTree(T);cout递归先序遍历:;preOrderTraverse(T);coutendl;cout递归中序遍历:;inOrderTraverse(T);coutendl;cout递
21、归后序遍历:;postOrderTraverse(T);coutendl;cout层序遍历：;LevelTraverse(T);coutendl;cout非递归先序遍历：;stackPreOrderTraverse(T);coutendl;cout非递归中序遍历：;stackInOrderTraverse(T);coutendl;cout非递归后序遍历：;stackPostOrderTraverse(T);coutendl; cout叶子结点为：; cout叶子结点个数为：TreeLeaf(T)endl;cout树的的深度：;layer=PostTreeDepth(T);coutlayerendl;cout二叉树的树形结构图：endl;PrintTree(T,layer);return 0;