C++创建二叉树及操作.doc

#include #include #include #define OK 1#define ERROR 0#define OVERFLOW -2typedef char ElemType;const int MaxLength=30;/结点个数不超过30个typedef struct BiTreeNodeElemType data;struct BiTreeNode *lchild,*rchild;BiTreeNode,*BiTree;void CreateBiTree(BiTree &T) ElemType ch; cinch; if(ch=#) T = NULL; elseif (!(T = new BiTreeNode) exit(OVERFLOW);T-data = ch; / 生成根结点CreateBiTree(T-lchild); / 构造左子树CreateBiTree(T-rchild); / 构造右子树 / CreateBiTreevoid PreOrder(BiTree &T)/递归函数：先序遍历以T为根的二叉树。if(T !=NULL) /递归结束条件 coutdatalchild); /先序遍历根的左子树PreOrder(T-rchild); /先序遍历根的右子树void InOrder(BiTree &T)/递归函数：中序次序遍历以T为根的子树。if(T !=NULL) /NULL是递归终止条件InOrder(T-lchild); /中序遍历根的左子树coutdatarchild); /中序遍历根的右子树void PostOrder(BiTree &T)/递归函数：后序次序遍历以T为根的子树。if(T !=NULL) /NULL是递归终止条件PostOrder(T-lchild); /后序遍历根的左子树PostOrder(T-rchild); /后序遍历根的右子树 coutdata ; /访问根结点void LevelOrder(BiTree T)/层序遍历BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T)/根结点入队Qrear=T;rear=(rear+1)%MaxLength; while(front!=rear) p=Qfront; /队头元素出队 front=(front+1)%MaxLength; coutdatalchild)/左孩子不为空，入队 Qrear=p-lchild; rear=(rear+1)%MaxLength; if(p-rchild)/右孩子不为空，入队 Qrear=p-rchild; rear=(rear+1)%MaxLength; bool Complete(BiTree T)BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T=NULL)/根结点入队return true;elseQrear=T;rear=(rear+1)%MaxLength; while(front!=rear) p=Qfront; /队头元素出队 front=(front+1)%MaxLength; if(p) Qrear=p-lchild; rear=(rear+1)%MaxLength; Qrear=p-rchild; rear=(rear+1)%MaxLength;elsewhile(front!=rear)p=Qfront;if(p)return false;elsereturn true;return true;int Depth(BiTree T)int depthval,depthleft,depthright;if(!T)depthval=0;elsedepthleft = Depth(T-lchild);depthright = Depth(T-rchild);depthval = 1 +(depthleftdepthright ? depthleft:depthright);return depthval;int Countleaf(BiTree T)int m,n;if(!T)return 0;if(!T-lchild & !T-rchild)return 1;elsem = Countleaf(T-lchild);n = Countleaf(T-rchild);return (m+n);int Countleafs(BiTree T)int m,n;if(!T)return 0;if(!T-lchild & !T-rchild)return 1;elsem = Countleafs(T-lchild);n = Countleafs(T-rchild);return (m+n+1);BiTree.cpp文件#include BiTree.hvoid main()coutMade by Fly!endl;cout请输入二叉树序列,如：AB#C#D#endl;BiTree tree;CreateBiTree(tree);cout二叉树创建完成！endl;cout先序遍历二叉树输出结果：;PreOrder(tree);coutendl;cout中序遍历二叉树输出结果：;InOrder(tree);coutendl;cout后序遍历二叉树输出结果：;PostOrder(tree);coutendl;cout层次遍历二叉树输出结果：;LevelOrder(tree);coutendl;cout层次遍历二叉树判定是否为完全二叉树：endl;bool t = Complete(tree);if(t)cout此二叉树是完全二叉树。endl;elsecout此二叉树不是完全二叉树。endl;cout此二叉树的深度为：;i