二叉树的定义及基本操作

1、表达式二叉树附件2:北京理工大学珠海学院实验报告实验时间实验题目二叉树的定义及基本操作-、实验目的、意义（1）熟悉二叉链表表示的二叉树结构及其递归遍历。（2）掌握建立二叉链表要领，深入理解递归遍历二叉链表的执行路径（3）根据具体问题的需要，能够设计出相关算法。二、实验内容及要求说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输 入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修 改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。具体要求：（1）定义二叉树的链式存储结构；（2）建立一颗二叉链表表示的二叉树；（3）对其进行前序，中序，后序输出。（参

2、见教材127页）（4）存储并写出下列表达式二叉树的前序、中序、后序输出。1. 中缀表达式（中序遍历）：a+（b*（c-d）-（e/f）2. 前缀表达式/波兰式（前序遍历）：-+a*b-cd/ef3. 后缀表达式/逆波兰式（后序遍历）：abcd-*+ef/-引自严蔚敏数据结构C语言版P129三、实验所涉及的知识点 递归函数 二叉树四、实验记录(调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。 ) 调试过程老是出现访问冲突的错问， 通过上网查找访问冲突方面的消息， 才知 道应该是指针指错地址，经过调试，最终解决了问题。调试过程中还出现了这个问题， Status CreateBiTre

3、e(BiTree T) ，当这样定 义时，问题就出现了，但是 Status CreateBiTree(BiTree &T) 这样定义就没问题 了，这个想不通。五、实验结果及分析(所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图 方式给出。，输入界面c: D o cuMent s and Sett ingsAdKini st rat or ly Dacinent sWisual Studio 20. . . H 回 * H ! ME,議! *! )H.输入说明p*请按先序尊入表达式,当结 、 卜*h ttnSu入式子先序肯f h -输入形式Sj-fi titt hi*s-+a

4、*bGdZef abed*ef/-输出结果u c: D ocusents and SettingsAdMinisi rat orBy DociiBentsV1 sual Studio 2D. .请挨先序歸茂養黠盂?|右子桝为空叶輸入嗨二输入喊式为-a4#bBtt*序抽山：*6+5*+2383 底输刊 6523*8*+3*，辛输岀：&*5+*8+3测试式子 6* (5+ (2+) *8) +3)六、总结与体会(调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因 等。)每次的实验，总是很受打击。不过，在这过程中，能让我发现自己的 不足，逐渐改善，这是做实验给我最大的收获。七、程序

5、清单 （包含注释 ）*通用头文件*#define TRUE 1#define FLASE 0#define OK 1#define ERROR 0#define INFREASIBLE -1#define OVERFLOW -2#define SIZE 100 / 存储空间初始分配量#define INCREMENT 10/存储空间分配增量#define MAXSIZE 12500/非零元个数的最大值为/#define MAXRC 12500/三元组中元素的个数的最大值typedef int Status; typedef char ElemType;/* 二叉树头文件*/#include D

6、ataStructure.h#include stdio.h#include stdlib.h#include string.h / 二叉树结构体 typedef struct 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-d

7、ata = ch;CreateBiTree(T-left);CreateBiTree(T-right);return OK;/ 先序输出 Status PreOrderTraverse(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; / 用

8、于控制括号对输出的变量if (T)if (T-left)while (T-left-left)/ 找出叶子结点 InOrderTraverse(T-left);printf( %c, T-data); / 输出父母结点 InOrderTraverse(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)pri

9、ntf( ( ); n+; InOrderTraverse(T-right); else if (T-data != 0)printf( %c, T-data);while (n 0)printf( ) );n-;return OK;/ 后序输出Status AfOrderTraverse(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.h int main()BiTree T;printf(*);*nprintf(叶卄输入说明*n);printf(叶卄请按先序输入表达式，当结点的左子树或者右子树为空时输入 #*n);printf(叶卄比如输入式子先序为 -ab, 输入形式);为-a#b#*n );printf(H*nnnprint