二叉树创建和遍历.doc

实验4 二叉树创建、遍历操作与应用 1实验目的 掌握使用先序方式创建二叉树； 掌握使用递归的方式对二叉树进行先序、中序和后序遍历操作； 掌握层次遍历； 二叉树的具体应用，如计算叶子结点个数，计算二叉树的深度。 2实验内容 以先序方式创建二叉链表存储结构的二叉树； 对二叉树进行先序、中序和后序遍历操作； 层次遍历二叉树。 求二叉树的深度以及叶子结点个数； 【测试数据】自定 参考程序如下： # include malloc.h # include iostream.h # include conio.h # include stdlib.h # define OK 1 # define ERROR 0 # define OVERFLOW 0 # define MAXQSIZE 100 typedef char TElemType; typedef struct BiTNode //define binary tree data struct { TElemType data; 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 lchild CreateBiTree(T-rchild); //create rchild } return (OK); } //CreateBiTree() end int PreOrderTraverse(BiTree T) //PreOrderTravers sub-function { if(T) { coutT-data-; //visite T PreOrderTraverse(T-lchild); //traverse lchild PreOrderTraverse(T-rchild); //traverse rchild return (OK); } //if end else return (OK); } //PreOrderTraverse() end int InOrderTraverse(BiTree T) //InOrderTravers sub-function { if(T) { InOrderTraverse(T-lchild); //traverse lchild coutT-data-; //visite T InOrderTraverse(T-rchild); //traverse rchild return (OK); } //if end else return (OK); } //InOrderTraverse() end int PostOrderTraverse(BiTree T) //PostOrderTravers sub-function { if(T) { PostOrderTraverse(T-lchild); //traverse lchild PostOrderTraverse(T-rchild); //traverse rchild coutT-data-; //visit T return (OK); } //if end else return (OK); } //PostOrderTraverse() end int 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 0 return ( 0 ); else { depth_l = Depth_B