《二叉树的定义及基本操作.docx》由会员分享，可在线阅读，更多相关《二叉树的定义及基本操作.docx（9页珍藏版）》请在三一办公上搜索。
1、表达式二叉树附件2：北京理工大学珠海学院实验报告实验时间实验题目二叉树的定义及基本操作一、实验目的、意义（1）熟悉二叉链表表示的二叉树结构及其递归遍历。（2）掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径。（3）根据具体问题的需要，能够设计出相关算法。二、实验内容及要求说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输 入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修 改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：（1）定义二叉树的链式存储结构；（2）建立一颗二叉链表表示的二叉树；（3）对其进行前序，中序，后序输出。（
2、参见教材127页）（4）存储并写出下列表达式二叉树的前序、中序、后序输出。1. 中缀表达式（中序遍历）： a+（b*（cd）（e/f）2. 前缀表达式/波兰式（前序遍历）： +a*bcd/ef3. 后缀表达式/逆波兰式（后序遍历）： abcd*+ef/引自严蔚敏数据结构C语言版P129三、实验所涉及的知识点递归函数二叉树四、实验记录(调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。) 调试过程老是出现访问冲突的错问，通过上网查找访问冲突方面的消息，才知 道应该是指针指错地址，经过调试，最终解决了问题。调试过程中还出现了这个问题，Status CreateBiTree(BiTree
3、 T),当这样定 义时，问题就出现了，但是Status CreateBiTree(BiTree &T)这样定义就没问题 了，这个想不通。五、实验结果及分析(所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果米用截图 方式给出。)输入界面=我 c: DociiBents and Sett ingsAdinist rat orly Docuent s WisuaL Studio 20.H 请按元序裔入表这式，当结点的左子珂或看右子树为空质输入*4*FHti输X式子先序为-命.输入贵式为fittthitit*式IJ 1JI1 illi入制输斤斥斤柬几后中输出结果:*6#+5 #*+2 #3
4、 #8 #B3 fl# *6*5*2383 6523+8*+3+* 6*5+*8)+3仍式子DocmentE右子树为空时输入X*输入说明R清按先序输入表达式，当结点.的左子枫或窄 R比加输入式子先序为小玖输X朦1出测试式子 6* (5+ (2+) *8) +3)六、总结与体会(调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因 等。)每次的实验，总是很受打击。不过，在这过程中，能让我发现自己的 不足，逐渐改善，这是做实验给我最大的收获。七、程序清单（包含注释）/*通用头文件*/#define#define#define#define#define#defineTRUE 1FL
5、ASE 0OK 1ERROR 0INFREASIBLE -1OVERFLOW -2SIZE 100 /存储空间初始分配量 INCREMENT 10#define#define#define MAXSIZE 12500/#define MAXRC 12500存储空间分配增量非零元个数的最大值为三元组中元素的个数的最大值typedef int Status;typedef char ElemType;/*二叉树头文件*/#include DataStructure.h#include stdio.h#include stdlib.h#include string.h/二叉树结构体typedef s
6、truct BiTNodeElemType data;BiTNode *left, *right;）BiTNode, *BiTree;生成二叉树Status CreateBiTree(BiTree &T)ElemType ch;scanf(%c，&ch);if (ch = #)T = NULL;else if(!(T = (BiTNode *)malloc(sizeof(BiTNode) return ERROR;T-data = ch;CreateBiTree(T-left);CreateBiTree(T-right);return OK;先序输出Status PreOrderTravers
7、e(BiTree T)if(T)if(T-data != 0)printf(c，T-data);if(T-left)PreOrderTraverse(T-left);PreOrderTraverse(T-right);return OK; 中序输出int i = 1; /用于控制括号对输出的变量Status InOrderTraverse(BiTree T)int n = 0; /用于控制括号对输出的变量if( T)if(T-left)while(T-left-left)/找出叶子结点InOrderTraverse(T-left);printf(c，T-data); /输出父母结点InOrde
8、rTraverse(T-right);return OK;第一次输出结点时，不要输出括号if( i 1)(printf()；n+;i+;if (T-left-data != 0)printf(c， T-left-data);printf(%c，T-data);if(T-right-left)if(T-right-left-left)printf()；n+;InOrderTraverse(T-right);else if(T-data != 0)printf(%c，T-data);while (n 0)printf()；n-;return OK;后序输出Status AfOrderTravers
9、e(BiTree T)if( T)if(T-left)AfOrderTraverse(T-left);if(T-data != 0)printf(%c，T-data);AfOrderTraverse(T-right);return OK;/*二叉树main文件*/#include BiTree.hint main()BiTree T;printf( * *n)；printf(*输入说明*n)；printf(*请按先序输入表达式，当结点的左子树或者右 子树为空时输入# *n)；printf(*比如输入式子先序为-ab,输入形式为-a#b#*n)；printf(*nn)；printf(请输入式子：)；CreateBiTree(T);printf(先序输出：)；PreOrderTraverse(T);printf(n后序输出：)；AfOrderTraverse(T);printf(n中序输出：)；InOrderTraverse(T);return 0;
