实验三、二叉树的基本操作.doc

实验三 二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一：二叉树的基本操作实现 （必做题）问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；(选做)4. 将二叉树每个结点的左右子树交换位置。（选做） 基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），测试数据如输入：ABCDEGF（其中表示空格字符）则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG选作内容采用非递归算法实现二叉树遍历。三、 算法设计 1、 主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后用指针对树进行操作，重点掌握二叉树的结构和性质。2、 本程序包含四个模块：（1） 结构体定义 （2） 创建二叉树 （3） 对树的几个操作 （4） 主函数四、 调试分析这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰五、 实验结果六、 总结此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。七、源程序#include#includeusing namespace std;#define TElemType char#define Status int#define OK 1#define ERROR 0typedef struct BiTNodeTElemType data;struct BiTNode * lchild, *rchild;BiTNode,* BiTree;Status CreateBiTree(BiTree &T)TElemType ch;cin ch;if (ch = #)T = NULL;elseif (!(T = (BiTNode *)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data = ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;Status PreOrderTraverse(BiTree T)if (T)cout data;if (PreOrderTraverse(T-lchild)if (PreOrderTraverse(T-rchild)return OK;return ERROR;elsereturn OK;Status InOrderTraverse(BiTree T)if (T)InOrderTraverse(T-lchild);cout data;InOrderTraverse(T-rchild);return OK;Status PostOrderTraverse(BiTree T)if (T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);cout data;return OK;Status leOrderTraverse(BiTree T)std:queue Q;if (T = NULL)return ERROR;elseQ.push(T);while (!Q.empty()T = Q.front();Q.pop();cout data;if (T-lchild != NULL)Q.push(T-lchild);if (T-rchild != NULL) Q.push(T-rchild);return OK;Status change(BiTree T)BiTree temp = NULL;if (T-lchild = NULL & T-rchild = NULL)return OK;elsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;if (T-lchild)change(T-lchild);if (T-rchild)change(T-rchild);return OK;int FindTreeDeep(BiTree T)int deep = 0;if (T)int lchilddeep = FindTreeDeep(T-lchild);int rchilddeep = FindTreeDeep(T-rchild);deep = lchilddeep = rchilddeep ? lchilddeep + 1 : rchilddeep + 1;return deep;int main()BiTree T;CreateBiTree(T);cout 先序遍历顺序为：;PreOrderTraverse(T);cout endl;cout 中序遍历顺序为：;InOrderTraverse(T);cout endl;cout 后序遍历顺序为：;PostOrderTraverse(T);cout endl;cout 层序遍历顺序为：;leOrderTraverse(T);cout