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

1、/*实验三：二叉树遍历操作验证*/#include<iostream>#include<stdio.h>#include<stdlib.h>#include<stack>#include<map>#include<queue>#include<math.h>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2int LeafNum;/叶子结点个数/定义结构体typedef struct BiTNodechar data;/存放值st

2、ruct 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(OVERFLOW);T->data=ch;/生成根结点createBiTree(T-&g

3、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);if(T

4、->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<BiTree>

5、 q;/建队 q.push(T);/根节点入队 BiTree p; while(!q.empty() p=q.front(); /获得队列的首元素 q.pop(); /首元素出队 cout<<p->data<<" " /输出结点的值 if(p->lchild!=NULL) /若结点的左孩子不空 q.push(p->lchild); if(p->rchild!=NULL)/若结点的右孩子不空 q.push(p->rchild); /非递归方法前序遍历二叉树void stackPreOrderTraverse(BiTree

6、T)stack<BiTree> 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)st

7、ack<BiTree> 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->rchild);/右孩子入栈/非递归方法后序遍历二叉树void stackPostOrderTraverse(BiTree T)stack<BiTre

8、e> s;/建栈map<BiTree,bool> 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)

9、/若最左孩子的右孩子未输出且非空，则入栈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); /求右子树的深度 ma

10、x=hl>hr?hl:hr; /得到左、右子树深度较大者 return(max+1); /返回树的深度 else return(0); /如果是空树，则返回0/*按竖向树状打印的二叉树代码是为了实现二叉树的横向显示问题。 这种树形要求先打印右子树，再打印根，最后打印左子树，顺序恰为逆中序顺序。 这种输出格式，结点的左右位置与结点的层深有关， 故算法中设置了一个表示当前根节点层深的参数，以控制输出结点的左右位置。 */void PrintTree(BiTree T,int nLayer) int i; if(T=NULL) return; PrintTree(T->rchild,nL

11、ayer+1); for(i=0;i<nLayer;i+) printf(" "); printf("%cn",T->data); PrintTree(T->lchild,nLayer+1);/叶子结点的个数以及元素int TreeLeaf(BiTree T) if(T) if(!T->lchild&&!T->rchild) LeafNum+; cout<<T->data<<" " TreeLeaf(T->lchild); TreeLeaf(T->

12、rchild);return LeafNum;int main()BiTree T;/定义结点int layer=0;/层数while(true)cout<<"输入二叉树结点值空格表示空树："<<endl;createBiTree(T);cout<<"递归先序遍历:"preOrderTraverse(T);cout<<endl;cout<<"递归中序遍历:"inOrderTraverse(T);cout<<endl;cout<<"递归后序遍历

13、:"postOrderTraverse(T);cout<<endl;cout<<"层序遍历："LevelTraverse(T);cout<<endl;cout<<"非递归先序遍历："stackPreOrderTraverse(T);cout<<endl;cout<<"非递归中序遍历："stackInOrderTraverse(T);cout<<endl;cout<<"非递归后序遍历："stackPostOrde

14、rTraverse(T);cout<<endl; cout<<"叶子结点为：" cout<<"叶子结点个数为："<<TreeLeaf(T)<<endl;cout<<"树的的深度："layer=PostTreeDepth(T);cout<<layer<<endl;cout<<"二叉树的树形结构图："<<endl;PrintTree(T,layer);return 0;/*实验三：二叉树遍历操作验证*

15、/#include<iostream>#include<stdio.h>#include<stdlib.h>#include<stack>#include<map>#include<queue>#include<math.h>using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2int LeafNum;/叶子结点个数/定义结构体typedef struct BiTNodechar data;/存放值struct BiTNode *lc

16、hild,*rchild;/左右孩子BiTNode,*BiTree;/先序输入二叉树结点的值，空格表示空树void createBiTree(BiTree &T)char ch;/输入结点时用scanf("%c",&ch);if(ch=' ')/若输入空格，该值为空,且没有左右孩子T=NULL;elseT=(BiTNode *)malloc(sizeof(BiTNode);/分配结点空间if(!T)/分配失败exit(OVERFLOW);T->data=ch;/生成根结点createBiTree(T->lchild);/构造左子树

17、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);if(T->data)/输出pri

18、ntf("%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<BiTree> q;/建队 q.push(T)

19、;/根节点入队 BiTree p; while(!q.empty() p=q.front(); /获得队列的首元素 q.pop(); /首元素出队 cout<<p->data<<" " /输出结点的值 if(p->lchild!=NULL) /若结点的左孩子不空 q.push(p->lchild); if(p->rchild!=NULL)/若结点的右孩子不空 q.push(p->rchild); /非递归方法前序遍历二叉树void stackPreOrderTraverse(BiTree T)stack<BiTre

20、e> 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<BiTree>

21、; 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->rchild);/右孩子入栈/非递归方法后序遍历二叉树void stackPostOrderTraverse(BiTree T)stack<BiTree> s;/建栈map&l

22、t;BiTree,bool> 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)/若最左孩子的右孩子未输出且非空

23、，则入栈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=hl>hr?hl:hr

24、; /得到左、右子树深度较大者 return(max+1); /返回树的深度 else return(0); /如果是空树，则返回0/*按竖向树状打印的二叉树代码是为了实现二叉树的横向显示问题。 这种树形要求先打印右子树，再打印根，最后打印左子树，顺序恰为逆中序顺序。 这种输出格式，结点的左右位置与结点的层深有关， 故算法中设置了一个表示当前根节点层深的参数，以控制输出结点的左右位置。 */void PrintTree(BiTree T,int nLayer) int i; if(T=NULL) return; PrintTree(T->rchild,nLayer+1); for(i=0

25、;i<nLayer;i+) printf(" "); printf("%cn",T->data); PrintTree(T->lchild,nLayer+1);/叶子结点的个数以及元素int TreeLeaf(BiTree T) if(T) if(!T->lchild&&!T->rchild) LeafNum+; cout<<T->data<<" " TreeLeaf(T->lchild); TreeLeaf(T->rchild);return LeafNum;int main()BiTree T;/定义结点i