二叉树创建和遍历.doc

实验4 二叉树创建、遍历操作与应用1实验目的(1) 掌握使用先序方式创建二叉树；(2) 掌握使用递归的方式对二叉树进行先序、中序和后序遍历操作；(3) 掌握层次遍历；(4) 二叉树的具体应用，如计算叶子结点个数，计算二叉树的深度。2实验内容(1) 以先序方式创建二叉链表存储结构的二叉树；(2) 对二叉树进行先序、中序和后序遍历操作；(3) 层次遍历二叉树。(4) 求二叉树的深度以及叶子结点个数；【测试数据】自定参考程序如下：# include # include # include # include # define OK 1# define ERROR 0# define OVERFLOW 0# define MAXQSIZE 100typedef char TElemType;typedef struct BiTNode/define binary tree data struct TElemTypedata; struct BiTNode*lchild,*rchild;BiTNode, *BiTree;typedef BiTree QElemType;typedef struct SqQueue/define structure SqQueue QElemType* base; int front; int rear;SqQueue;int CreateBiTree(BiTree &T)/createBiTree() by preorder TElemType ch;cinch;if(ch=) T=NULL;else if(!(T=(BiTNode *)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);/create lchildCreateBiTree(T-rchild);/create rchildreturn (OK); /CreateBiTree() endint PreOrderTraverse(BiTree T)/PreOrderTravers sub-function if(T)coutdata;/visite TPreOrderTraverse(T-lchild);/traverse lchildPreOrderTraverse(T-rchild);/traverse rchildreturn (OK); /if endelsereturn (OK); /PreOrderTraverse() endint InOrderTraverse(BiTree T)/InOrderTravers sub-functionif(T)InOrderTraverse(T-lchild);/traverse lchildcoutdata;/visite TInOrderTraverse(T-rchild);/traverse rchildreturn (OK); /if endelsereturn (OK); /InOrderTraverse() endint PostOrderTraverse(BiTree T)/PostOrderTravers sub-functionif(T)PostOrderTraverse(T-lchild);/traverse lchildPostOrderTraverse(T-rchild);/traverse rchildcoutdata; /visit Treturn (OK); /if endelsereturn (OK); /PostOrderTraverse() endint Depth_BT ( BiTree T )/return the depth of the Tree int d,depth_r,depth_l; if ( !T )/ if tree is null, its depth is 0return ( 0 ); else depth_l = Depth_BT ( T-lchild );/ return the depth of its left child treedepth_r = Depth_BT ( T-rchild );/ return the depth of its right child treeif ( depth_l = depth_r )d = depth_l;elsed = depth_r;return ( 1+d ); / else end / Depth_BTint Leaf ( BiTree T ) / count the number of leaf on the BiTree by recursive method int n,m; if ( T = NULL )return ( 0 );/ if Tree is empty, the leaf is 0 else if ( ( T-lchild = NULL ) & ( T-rchild = NULL ) )return ( 1 );/ if both lchild and rchild are NULL, then it is a leaf node else / lchild or rchild is not NULL n = Leaf ( T-lchild );/ count leaf number on T-lchild sub-treem = Leaf ( T-rchild );/ count leaf number on T-rchild sub-treereturn ( n+m );/ return the leaf node number of Bitree / else end / Leaf/=Sequence Queue implment=int InitQueue(SqQueue &Q)/InitQueue() sub-function Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); if(!Q.base)exit(OVERFLOW); Q.front=Q.rear=0; return (OK); /InitQueue() endint EnQueue(SqQueue &Q,QElemType e)/EnQueue() sub-function if(Q.rear+1)%MAXQSIZE=Q.front)exit(OVERFLOW); Q.baseQ.rear=e; Q.rear=(Q.rear+1)%MAXQSIZE; return (OK); /EnQueue() endint DeQueue(SqQueue &Q,QElemType &e) /DeQueue sub-function if(Q.front=Q.rear) return ERROR; e=Q.baseQ.front; Q.front=(Q.front+1) % MAXQSIZE; return OK;int isEmpty(SqQueue &Q) if(Q.front = Q.rear) return OK; else return ERROR;/=void levelTraverse(BiTree T) SqQueue q;InitQueue(q); if(T!=NULL) coutdata; /visit node EnQueue(q, T); /Enqueue node while(!isEmpty(q) DeQueue(q,T); / if(T-lchild!=NULL) /if lchild is not NULL, visit then enqueue. coutlchild-data; EnQueue(q, T-lchild); if(T-rchild!=NULL) /if rchild is not NULL, visit then enqueue coutrchild-data; EnQueue(q, T-rchild); /while end /translevelvoid main()/main() functionBiTree T; coutcreate the binary tree by pre-order: nn;coutplease input the element of binTree,( is blank),such as ABDGEHIKCFJendl; if(CreateBiTree(T)/ CreateBiTree()coutnn create the binary tree successfully! endl;coutpre-order tranvers the binary tree:n ;PreOrderTraverse(T);coutNULLendl;coutIn-order tranvers the binary tree:n ;InOrderTraverse(T);coutNULLendl;coutpost-order tranvers the binary tree:n ;PostOrderTraverse(T);coutNULLendl; coutLevel tranvers the binary tree: en