二叉树的操作.doc

#include iostream.h#include stdlib.h#include stdio.htypedef char ElemType;/定义二叉树结点值的类型为字符型const int MaxLength=10;/结点个数不超过10个typedef struct BTNode ElemType data; struct BTNode *lchild,*rchild;BTNode,* BiTree;void CreateBiTree(BiTree &T)/按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树/ if(T) return; char ch; ch=getchar(); /不能用cin来输入，在cin中不能识别空格。 if(ch= ) T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) coutdata=ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); void PreOrderTraverse(BiTree T)/先序遍历 if(T) coutdatalchild); PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T)/中序遍历 if(T) InOrderTraverse(T-lchild); coutdatarchild); void PostOrderTraverse(BiTree T)/后序遍历 if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutdata ; void LevelOrderTraverse(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; /非递归的先序遍历算法void NRPreOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) coutdata; stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop; p=p-rchild; /非递归的中序遍历算法void NRInOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top0) while(p!=NULL) stacktop=p; top+; p=p-lchild; if (top0) top-; p=stacktop;coutdata; p=p-rchild; /非递归的后序遍历算法/*bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。首先将bt和tag(为1)入栈，遍历左子树；返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。*/typedef struct BiTree ptr; int tag;stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt; int top; if(bt!=NULL) top=0;p=bt; do while (p!=NULL) /遍历左子树 stop.ptr = p; stop.tag = 1; /标记为左子树 top+; p=p-lchild; while (top0 & stop-1.tag=2) x = s-top; p = x.ptr; coutdata; /tag为R，表示右子树访问完毕，故访问根结点 if (top0) stop-1.tag =2; /遍历右子树 p=stop-1.ptr-rchild; while (top0);/PostOrderUnrecint BTDepth(BiTree T)/求二叉树的深度 if(!T) return 0; else int h1=BTDepth(T-lchild); int h2=BTDepth(T-rchild); if(h1h2) return h1+1; else return h2+1; int Leaf(BiTree T)/求二叉树的叶子数 if(!T) return 0; else if(!T-lchild&!T-rchild) return 1; else return(Leaf(T-lchild)+Leaf(T-rchild);int NodeCount(BiTree T)/求二叉树的结点总数 if(!T) return 0; else return NodeCount(T-lchild)+NodeCount(T-rchild)+1;void main() BiTree T; T=NULL; int select; /cout请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):endl;/ CreateBiTree(T); while(1) coutnn请选择要执行的操作:n; cout1.创建二叉树n; cout2.二叉树的递归遍历算法（前、中、后）n; cout3.二叉树的层次遍历算法n; cout4.求二叉树的深度n; cout5.求二叉树的叶子结点n; cout6.求二叉树的结点总数n; cout7.二叉树的非递归遍历算法（前、中、后）n; /此项可选做 coutselect; switch(select) case 0:return; case 1: cout请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):endl; CreateBiTree(T); break; case 2: if(!T) cout未建立树，请先建树！; else coutn先序遍历:n; PreOrderTraverse(T); coutn中序遍历:n; InOrderTraverse(T); coutn后序遍历:n; PostOrderTraverse(T); break; case 3: coutn层序遍历:n; LevelOrderTraverse(T); break; case 4: cout二叉树的深度为:n; coutBTDepth(T); break; case 5: coutn叶子节点数:n; coutLeaf(T); break; case 6: cout总节点数:n; coutNodeCount(T); break; case 7: if(!T) cout未建立树，请先建树！; else coutn先序遍历:n; NRPreOrder(T); coutn中序遍历:n;