《数据结构上机实验二叉树的操作和实现》由会员分享，可在线阅读，更多相关《数据结构上机实验二叉树的操作和实现（4页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 实 验 指 导 书 第 1 页 共 4 页 实验实验三三 二叉树操作设计和实现 实验题目实验题目：二叉树操作设计和实现二叉树操作设计和实现 实验目的实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求：实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤：实验主要步骤： 1、分析、理解程序。 2、调试程序， 设计一棵二叉树， 输入完全二叉树的先序序列， 用#代表虚结点 （空指针） ， 如 ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列， 求所有叶子及
2、结点总数。 /参考程序 #include“stdio.h“ #include“stdlib.h“ #include“string.h“ #define Max 20 /结点的最大个数 typedef struct node char data; struct node *lchild,*rchild; BinTNode; /自定义二叉树的结点类型 typedef BinTNode *BinTree; /定义二叉树的指针 int NodeNum,leaf; /NodeNum 为结点数，leaf 为叶子数 /=基于先序遍历算法创建二叉树= /=要求输入先序序列，其中加入虚结点“#“以示空指针的位置
3、= BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar()=#) return(NULL); /读入#，返回空指针 else T= (BinTNode *)malloc(sizeof(BinTNode); /生成结点 T-data=ch; T-lchild=CreatBinTree(); /构造左子树 T-rchild=CreatBinTree(); /构造右子树 return(T); /=NLR 先序遍历= void Preorder(BinTree T) 2 if(T) printf(“%c“,T-data); /访问结
4、点 Preorder(T-lchild); /先序遍历左子树 Preorder(T-rchild); /先序遍历右子树 /=LNR 中序遍历= void Inorder(BinTree T) if(T) Inorder(T-lchild); /中序遍历左子树 printf(“%c“,T-data); /访问结点 Inorder(T-rchild); /中序遍历右子树 /=LRN 后序遍历= void Postorder(BinTree T) if(T) Postorder(T-lchild); /后序遍历左子树 Postorder(T-rchild); /后序遍历右子树 printf(“%c“
5、,T-data); /访问结点 /=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法= int TreeDepth(BinTree T) int hl,hr,max; if(T) hl=TreeDepth(T-lchild); /求左深度 hr=TreeDepth(T-rchild); /求右深度 max=hlhr? hl:hr; /取左右深度的最大值 NodeNum=NodeNum+1; /求结点数 if(hl=0 /若左右深度为 0，即为叶子。 return(max+1); else return(0); /=利用“先进先出“（FIFO）队列，按层次遍历二叉树= void Levelo
6、rder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组 cq cq1=T; /根入队 while(front!=rear) 3 front=(front+1)%NodeNum; p=cqfront; /出队 printf(“%c“,p-data); /出队，输出结点的值 if(p-lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-lchild; /左子树入队 if(p-rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-rchild;
7、/右子树入队 /=数叶子节点个数= int countleaf(BinTree T) int hl,hr; if(T) hl=countleaf(T-lchild); hr=countleaf(T-rchild); if(hl=0 else return hl+hr; else return 0; /=主函数= int main() BinTree root; char i; int depth; printf(“n“); printf(“Creat Bin_Tree； Input preorder:“); /输入完全二叉树的先序序列， / 用#代表虚结点，如 ABD#CE#F# root=C
8、reatBinTree(); /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。 printf(“t* select *n“); printf(“t1: Preorder Traversaln“); printf(“t2: Iorder Traversaln“); printf(“t3: Postorder traversaln“); printf(“t4: PostTreeDepth,Node number,Leaf numbern“); printf(“t5: Level Depthn“); /按层次遍历之前，先选择 4，求出该树的结 点数。 printf(“t0: Exi
9、tn“); 4 printf(“t*n“); fflush(stdin); /刷新标准输入缓冲区，把输入缓冲区里的东西丢弃 scanf(“%c“, /输入菜单序号（0-5） switch (i-0) case 1: printf(“Print Bin_tree Preorder: “); Preorder(root); /先序遍历 break; case 2: printf(“Print Bin_Tree Inorder: “); Inorder(root); /中序遍历 break; case 3: printf(“Print Bin_Tree Postorder: “); Postorde
10、r(root); /后序遍历 break; case 4: depth=TreeDepth(root); /求树的深度及叶子数 printf(“BinTree Depth=%d BinTree Node number=%d“,depth,NodeNum); printf(“ BinTree Leaf number=%d“,countleaf(root); break; case 5: printf(“LevePrint Bin_Tree: “); Levelorder(root); /按层次遍历 break; default: exit(1); printf(“n“); while(i!=0); system(“pause“); return 0;
