C++创建二叉树及操作

《C++创建二叉树及操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#defineOK1#defineERROR0#defineOVERFLOW-2typedefcharElemType;constintMaxLength=30;//结点个数不超过30个typedefstructBiTreeNode{ElemTypedata;structBiTreeNode*lchild,*rchild;}BiTreeNode,*BiTree;voidCreateBiTree(BiTree&T){ElemTypech;cin>>ch;if(ch=='#')T=NUL

2、L;else{if(!(T=newBiTreeNode))exit(OVERFLOW);T->data=ch;//生成根结点CreateBiTree(T->lchild);//构造左子树CreateBiTree(T->rchild);//构造右子树}}//CreateBiTreevoidPreOrder(BiTree&T)//递归函数：先序遍历以T为根的二叉树。{if(T!=NULL)//递归结束条件{cout<data<<"";//访问根结点PreOrder(T->lchild);//先序遍历根的左子树PreOrder(T->rchild);//先序遍历根的右子树}}voidInO

3、rder(BiTree&T)//递归函数：中序次序遍历以T为根的子树。{if(T!=NULL)//NULL是递归终止条件{InOrder(T->lchild);//中序遍历根的左子树cout<data<<"";//访问根结点InOrder(T->rchild);//中序遍历根的右子树}}voidPostOrder(BiTree&T)//递归函数：后序次序遍历以T为根的子树。{if(T!=NULL)//NULL是递归终止条件{PostOrder(T->lchild);//后序遍历根的左子树PostOrder(T->rchild);//后序遍历根的右子树cout<data<<""

4、;//访问根结点}}voidLevelOrder(BiTreeT)//层序遍历{BiTreeQ[MaxLength];intfront=0,rear=0;BiTreep;if(T)//根结点入队{Q[rear]=T;rear=(rear+1)%MaxLength;}while(front!=rear){p=Q[front];//队头元素出队front=(front+1)%MaxLength;cout<data<<"";if(p->lchild)//左孩子不为空，入队{Q[rear]=p->lchild;rear=(rear+1)%MaxLength;}if(p->rchild)//右

5、孩子不为空，入队{Q[rear]=p->rchild;rear=(rear+1)%MaxLength;}}}boolComplete(BiTreeT){BiTreeQ[MaxLength];intfront=0,rear=0;BiTreep;if(T==NULL)//根结点入队{returntrue;}else{Q[rear]=T;rear=(rear+1)%MaxLength;while(front!=rear){p=Q[front];//队头元素出队front=(front+1)%MaxLength;if(p){Q[rear]=p->lchild;rear=(rear+1)%MaxLen

6、gth;Q[rear]=p->rchild;rear=(rear+1)%MaxLength;}else{while(front!=rear){p=Q[front];if(p){returnfalse;}else{returntrue;}}}}returntrue;}}intDepth(BiTreeT){intdepthval,depthleft,depthright;if(!T){depthval=0;}else{depthleft=Depth(T->lchild);depthright=Depth(T->rchild);depthval=1+(depthleft>depthright?de

7、pthleft:depthright);}returndepthval;}intCountleaf(BiTreeT){intm,n;if(!T){return0;}if(!T->lchild&&!T->rchild){return1;}else{m=Countleaf(T->lchild);n=Countleaf(T->rchild);return(m+n);}}intCountleafs(BiTreeT){