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

/*实验三：二叉树遍历操作验证*/#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)char 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);preOrderTraverse(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)/输出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)stack 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()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)/目的：找到后序遍历要输出的结点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) hl=PostTreeDepth(T-lchild); /求左子树的深度 hr=PostTreeDepth(T-rchild); /求右子树的深度 max=hlhr?hl:hr; /得到左、右子树深度较大者 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;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)cout输入二叉树结点值空格表示空树：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非递归后序遍历：;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#define 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(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);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)/输出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)stack 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()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)/目的：找到后序遍历要输出的结点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) hl=PostTreeDepth(T-lchild); /求左子树的深度 hr=PostTreeDepth(T-rchild); /求右子树的深度 max=hlhr?hl:hr; /得到左、右子树深度较大者 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;idata); PrintTree(T-lchild,nLayer+1);/叶子结点的个数以及元素int T