实验六二叉树及应用的实验

《实验六二叉树及应用的实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验六二叉树及应用的实验【实验目的】掌握二叉树的左右链存储实现,二叉树的建立方法,二叉树的遍历算法,哈夫曼树的程序实现。【实验说明】1、存储结构定义及库文件#include#include#defineTRUE1#defineFALSE0#defineStack_Size50typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BiTNode,*BiTree;2、建立二叉树voidCreateBiTree(BiTree*bt){ch

2、arch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)->data=ch;CreateBiTree(&((*bt)->lchild));CreateBiTree(&((*bt)->rchild));}}1、先序递归遍历二叉树voidPreOrder(BiTreeroot)//root指向二叉树根结点{if(root!=NULL){printf("%c",root->data);PreOrder(root->lchild);PreOrder(root->rch

3、ild);}}4、中序非递归遍历二叉树voidinorder(BiTreeroot){BiTNode*p;inttop;BiTreeS[Stack_Size];top=0;p=root;//printf("ZYZ");do{while(p!=NULL){if(top>Stack_Size-1){printf("栈满");return;}else{top=top+1;S[top]=p;p=p->lchild;};}if(top!=0){p=S[top];top=top-1;printf("%c",p->data);p=p->rchild;}}while(p!=NU

4、LL

5、

6、top!=0);}1、主控菜单处理调试程序voidmain(){BiTreeT=NULL;intxz=1;charch;while(xz){printf("二叉树的建立及遍历");printf("==========================");printf("1、建立二叉树存储结构");printf("2、二叉树的前序遍历(递归)");printf("3、二叉树的中序遍历（非递归）");printf("0、退出系统");printf("===========================");printf("请选择：0－－

7、3");scanf("%d",&xz);switch(xz){case0:printf("再见!");return;case1:ch=getchar();printf("按扩展先序遍历序列输入二叉树各结点值：");CreateBiTree(&T);printf("二叉树的链式存储结构建立完成!");printf("");break;case2:printf("二叉树先序遍历序列为：");if(T)PreOrder(T);elseprintf("空树");printf("");printf("");break;case3:printf("二叉树

8、中序遍历序列为：");inorder(T);printf("");break;}}return;}//main【实验内容】⑴二叉树的遍历算法（非递归实现先序遍历，用递归实现中序遍历，用非递归实现后序遍历，层次遍历）⑵二叉树采用二叉链表方式存储，找到二叉树中度为0的结点个数。⑶二叉树采用二叉链表方式存储，找到二叉树中任两个结点的最近公共祖先。算法提示：①先按先序序列建立二叉树；②再分别采用递归算法找结点到根之间的路径，并将其存到一个数组中；③比较两个数组中元素，找到最近公共祖先。【实验要求】利用所给的实验说明完成实验内容中⑴――⑶要求的任一个程序，并参照实验说明完成调

9、试。写出试验报告并在实验完成后一周内交实验报告。//1、存储结构定义及库文件#include#include#defineTRUE1#defineFALSE0#defineStack_Size50typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;}BiTNode,*BiTree;//2、建立二叉树voidCreateBiTree(BiTree*bt){charch;ch=getchar();if(c