数据结构实验报告- 答案汇总

//========NLR 先序遍历============= void Preorder(BinTree T) {

if(T) { printf(\ //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } }

//========LNR 中序遍历=============== void Inorder(BinTree T) {

if(T) { Inorder(T->lchild); //中序遍历左子树 printf(\ //访问结点 Inorder(T->rchild); //中序遍历右子树 } }

//==========LRN 后序遍历============ void Postorder(BinTree T) {

if(T) { Postorder(T->lchild); //后序遍历左子树 Postorder(T->rchild); //后序遍历右子树 printf(\ //访问结点 } }

//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法======== int TreeDepth(BinTree T) {

int hl,hr,max; if(T){ hl=TreeDepth(T->lchild); //求左深度 hr=TreeDepth(T->rchild); //求右深度 max=hl>hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求结点数 if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。 return(max+1); }

else return(0); }

//====利用\先进先出\（FIFO）队列，按层次遍历二叉树========== void Levelorder(BinTree T) {

int front=0,rear=1;

BinTNode *cq[Max],*p; //定义结点的指针数组cq cq[1]=T; //根入队 while(front!=rear) { front=(front+1)%NodeNum; p=cq[front]; //出队 printf(\ //出队，输出结点的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild; //左子树入队 } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild; //右子树入队 } } }

//====数叶子节点个数========== int countleaf(BinTree T) { int hl,hr; if(T){ hl=countleaf(T->lchild); hr=countleaf(T->rchild); if(hl==0&&hr==0) //若左右深度为0，即为叶子。 return(1); else return hl+hr; } else return 0; }

//==========主函数================= void main() {

BinTree root; char i; int depth; printf(\

printf(\； Input preorder:\输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点

do { //从菜单中选择遍历方式，输入序号。

printf(\ printf(\ printf(\ printf(\ printf(\ printf(\按层次遍历之前，先选择4，求出该树的结点数。 printf(\ printf(\ fflush(stdin); scanf(\ //输入菜单序号（0-5） switch (i-'0'){ case 1: printf(\ Preorder(root); //先序遍历 break; case 2: printf(\ Inorder(root); //中序遍历 break; case 3: printf(\ Postorder(root); //后序遍历 break; case 4: depth=TreeDepth(root); //求树的深度及叶子数 printf(\ BinTree Node number=%d\ printf(\ BinTree Leaf number=%d\ break; case 5: printf(\ Levelorder(root); //按层次遍历 break; default: exit(1); } printf(\ } while(i!=0); }

实验结果：

Creat Bin_Tree； Input preorder:ABD###CE##F## ********** select ************ 1: Preorder Traversal 2: Iorder Traversal 3: Postorder traversal 4: PostTreeDepth,Node number,Leaf number

5: Level Depth 0: Exit ******************************* 1 Print Bin_tree Preorder: ABDCEF 2 Print Bin_Tree Inorder: DBAECF

3 Print Bin_Tree Postorder: DBEFCA

4 BinTree Depth=3 BinTree Node number=6 BinTree Leaf number=3 5 LevePrint Bin_Tree: ABCDEF 0 Press any key to continue 二叉树示意图

A B C D E F

心得体会：

这次实验加深了我对二叉树的印象，尤其是对二叉树的各种遍历操作有了一定的了解。同时认识到，在设计程序时辅以图形化的描述是非常有用处的。