2022年树和二叉树实验报告 .pdf

《2022年树和二叉树实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年树和二叉树实验报告 .pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验内容：实 验 三树 和 二 叉 树1. 编 写 函 数 , 输 入 字 符 序 列 , 建 立 二 叉 树 的 二 叉 链 表 。2. 编 写 函 数 , 实 现 二 叉 树 的 中 序 递 归 遍 历 算 法 。 ( 最 好 也 能 实 现 前 缀 和 后 缀 遍 历 算法 ) 3. 编 写 函 数 , 实 现 二 叉 树 的 中 序 非 递 归 遍 历 算 法 。4. 编 写 函 数 , 借 助 队 列 实 现 二 叉 树 的 层 次 遍 历 算 法 。5. 编 写 函 数 , 求 二 叉 树 的 高 度 。6. 编 写 函 数 , 求 二 叉 树 的 结 点 个 数 。7. 编 写

2、函 数 , 求 二 叉 树 的 叶 子 个 数 。8. 编 写 函 数 , 交 换 二 叉 树 每 个 结 点 的 左 子 树 和 右 子 树 。9. 编 写 一 个 主 函 数 , 在 主 函 数 中 设 计 一 个 简 单 的 菜 单 , 分 别 调 试 上 述 算 法 。实验目的及要求：1. 掌 握 二 叉 树 的 存 储 实 现2. 掌 握 二 叉 树 的 遍 历 思 想3. 掌 握 二 叉 树 的 常 见 算 法 的 程 序 实 现实验内容、方法与步骤： （使用附页填写并附在本页后）见 附 页实验结果：见 附 页小结：通 过 本 次 实 验 ， 我 基 本 掌 握 了 二 叉 树 的

3、 存 储 实 现 和 二 叉 树 的 遍 历 思 想 ，并 且 实 现 了 二 叉 树 的 几 种 常 见 算 法 。分数：批阅老师：200 年月日第1 页 / 共13 页实 验 报告 （附 页）#include #include #define OK 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - #define ERROR 0 #define OVERFLOW -2 typedef int status; typede

4、f struct BiNode/二叉链表 char Data; struct BiNode* lChild; struct BiNode* rChild; BiNode,*pBiNode; typedef struct SNode/*链栈的结点类型*/ pBiNode elem; /*栈中的元素是指向二叉链表结点的指针*/ struct SNode *next; SNode; struct link /队列链表 struct BiNode *p; struct link *next; ; status CreateTree(BiNode* pTree); status PreOrderTrav

5、al(BiNode* pTree);/前序递归status InOrderTraval(BiNode* pTree);/中序递归status PostOrderTraval(BiNode* pTree);/后序递归status st_InOrderTraverse(BiNode* pTree);/中序非递归遍历void TreeLink(BiNode* pTree); /队列实现层次遍历int TreeHeight (BiNode* pTree);/二叉树的高度int Count(BiNode* pTree);/结点个数int TreeNumber(BiNode* pTree);/叶子个数vo

6、id Exchange (BiNode* pTree);/交换左右子树status Visit(char Data); void Display(BiNode* pTree,int Level); BiNode *pRoot=NULL; status CreateTree(BiNode* pTree) /*Input Example: abd#e#cf#g#*/ char ch; scanf(%c,&ch); if(ch=#) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，

7、共 13 页 - - - - - - - - - (*pTree)=NULL; else if(!(*pTree)=(BiNode*)malloc(sizeof(BiNode) exit(OVERFLOW); (*pTree)-Data=ch; CreateTree(&(*pTree)-lChild); CreateTree(&(*pTree)-rChild); return OK; status PreOrderTraval(BiNode* pTree)/前序递归 if(pTree) if(Visit(pTree-Data) if(PreOrderTraval(pTree-lChild) i

8、f(PreOrderTraval(pTree-rChild) return OK; return ERROR; else return OK; status InOrderTraval(BiNode* pTree)/中序递归 if(pTree) if(InOrderTraval(pTree-lChild) if(Visit(pTree-Data) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - if(InOrderTraval

9、(pTree-rChild) return OK; return ERROR; return ERROR; else return OK; status PostOrderTraval(BiNode* pTree)/后序递归 if(pTree) if(PostOrderTraval(pTree-lChild) if(PostOrderTraval(pTree-rChild) if(Visit(pTree-Data) return OK; return ERROR; return ERROR; else return OK; status st_InOrderTraverse(BiNode* p

10、Tree)/中序非递归遍历 BiNode *p; SNode *q,*Stop=NULL; /*用不带头结点的单链表作为栈的存储结构*/ p=pTree; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - while(p!=NULL|Stop!=NULL) /*不是空树 */ if(p!=NULL) q=(SNode*)malloc(sizeof(SNode); if(q=NULL)return ERROR; q-next=St

11、op; q-elem=p; Stop=q; /*根结点指针入栈 */ p=p-lChild; /*进入根的左子树*/ else q=Stop;Stop=Stop-next; /*栈顶元素出栈 */ printf(%c ,q-elem-Data);/*访问根结点 */ p=q-elem-rChild; /*进入根的右子树 */ free(q); /*释放原栈顶元素的结点空间*/ return OK; void TreeLink(BiNode* pTree) /队列实现层次遍历 struct link *head,*rear,*temp; head=(struct link *)malloc(si

12、zeof(struct link); head-p=pTree; head-next=NULL; rear=head; do if(head-p-lChild!=NULL) temp=(struct link *)malloc(sizeof(struct link); temp-p=head-p-lChild; temp-next=NULL; rear-next=temp; rear=temp; if(head-p-rChild!=NULL) temp=(struct link *)malloc(sizeof(struct link); temp-p=head-p-rChild; temp-n

13、ext=NULL; rear-next=temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - rear=temp; temp=head; printf(%c ,head-p-Data); head=head-next; free(temp); while(head!=NULL); int TreeHeight(BiNode* pTree)/二叉树的高度 int hl ,hr ; /左右子树的高度if (pTree = N

14、ULL) return 0 ; else hl = TreeHeight(pTree- lChild); hr = TreeHeight (pTree- rChild); if (hlhr) return (hl +1); else return (hr +1); int Count(BiNode* pTree)/结点个数 return pTree = NULL ? 0 : Count(pTree-lChild) + Count(pTree-rChild) + 1; int TreeNumber(BiNode* pTree)/叶子个数 if (pTree=NULL) return 0; if

15、(pTree-lChild =NULL & pTree-rChild = NULL) return 1; return TreeNumber(pTree-lChild)+TreeNumber(pTree-rChild);/+1就可以求出结点个数 void Exchange (BiNode* pTree )/交换左右子树 BiNode* temp; if ( pTree-lChild != NULL | pTree-rChild != NULL ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

16、- - 第 6 页，共 13 页 - - - - - - - - - temp = pTree-lChild; pTree-lChild = pTree-rChild; pTree-rChild = temp; Exchange ( pTree-lChild ); Exchange ( pTree-rChild ); status Visit(char Data) printf(%c ,Data); return OK; void Display(BiNode* pTree,int Level)/显示整个树 int i; if(pTree=NULL) return; Display(pTree

17、-rChild,Level+1); for(i=0;i=1) printf(-); printf(%cn,pTree-Data); Display(pTree-lChild,Level+1); void CmdList() / 显示命令列表 printf(n_n); printf( 请选择操作 : n); printf( 1.前序递归遍历 n); / 前序递归遍历printf( 2.中序递归遍历 n); / 中序递归遍历printf( 3.后序递归遍历 n); / 后序递归遍历printf( 4.中序非递归遍历n); / 中序非递归遍历printf( 5.层次遍历 n); / 层次遍历prin

18、tf( 6.求二叉树高度 n); / 二叉树高度printf( 7.求结点个数 n); / 二叉树的结点个数printf( 8.求叶子个数 n); / 二叉树的叶子个数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - printf( 9.交换左右子树 n); / 交换左右子树printf( 0.退出程序 n); / 退出printf(n_n); void init() system (cls); printf(* * * * *

19、 * * * * * * * * * * * * * * * * * * * *n); printf(实验三树和二叉树 n); printf(03计本 3 班n); printf(樊海军 2B0324151138n); printf(* * * * * * * * * * * * * * * * * * * * * * * * *n); printf(本程序实现二叉树的常见算法。n); printf(=n); printf(请输入二叉树各元素:( 例如 abd#e#cf#g#)n); /例如 abd#e#cf#g# CreateTree(&pRoot); Display(pRoot,0); C

20、mdList(); void ReadCommand(char &c) do c=getchar(); while (c!=0&c!=1&c!=2&c!=3&c!=4&c!=5&c!=6&c!=7&c!=8&c!=9); void Interpret(char &c) switch(c) case 1: printf(n前序递归遍历 :n); PreOrderTraval(pRoot); CmdList(); break; case 2: printf(n中序递归遍历 :n); InOrderTraval(pRoot); CmdList(); 名师资料总结 - - -精品资料欢迎下载 - -

21、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - break; case 3: printf(n后序递归遍历 :n); PostOrderTraval(pRoot); CmdList(); break; case 4: printf(n中序非递归遍历 :n); st_InOrderTraverse(pRoot); CmdList(); break; case 5: printf(n层次遍历 :n); TreeLink(pRoot); CmdList(); break; case

22、 6: printf(n二叉树高度 :n); printf(%dn,TreeHeight(pRoot); CmdList(); break; case 7: printf(n结点个数 :n); printf(%dn,Count(pRoot); CmdList(); break; case 8: printf(n叶子个数 :n); printf(%dn,TreeNumber(pRoot); CmdList(); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共

23、13 页 - - - - - - - - - case 9: printf(n交换左右子树 :n); Exchange(pRoot); printf(n交换后的二叉树 :n); Display(pRoot,0); CmdList(); break; case 0: printf(程序结束，按任意键退出!n); void main() /主函数 char cmd; init(); do ReadCommand(cmd); Interpret(cmd); while (cmd!=0&cmd!=0); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

24、- - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 分数：批阅老师：200 年月日第 13 页 / 共 13 页名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -