北京邮电大学软件学院2019-2020学年第1学期实验报告课程名称：算法与数据结构课程设计实验名称：树及其应用实验完成人：日期： 2019 年 11月 10 日一、实验目的树是一种应用极为广泛的数据结构，也是这门课程的重点。
它们的特点在于非线性。
广义表本质上是树结构。
本章实验继续突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。
遍历逻辑的（或符号形式的）结构，访问动作可是任何操作。
本次实验希望帮助学生熟悉各种存储结构的特征，以及如何应用树结构解决具体问题（即原理与应用的结合）。
二、实验内容必做内容1）二叉树的建立与遍历[问题描述]建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
[基本要求]从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
[测试数据]ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA2）打印二叉树结构[问题描述]按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下边，二叉树的右子树在屏幕的上边。
例如：[测试数据]由学生依据软件工程的测试技术自己确定。
注意测试边界数据，如空二叉树。
[实现提示]（1）利用RDL遍历方法；（2）利用结点的深度控制横向位置。
选做内容采用非递归算法实现二叉树遍历。
三、实验环境Windows下利用vs 2019完成,语言c++四、实验过程描述首先构造Tree类，内含树的结构体BiTree，以及本实验所要用到的一些操作typedef struct BiTNode{TElemType data;int degree, depth, level; //度，高度，高度差struct BiTNode* lchild, * rchild; /* 左右孩子指针 */}BiTNode, * BiTree;实现相应功能:1、二叉树的建立与遍历构造二叉树：前序构造，先赋值，然后递归构造左子树，递归构造右函数BiTNode* Tree::CreatBiTree(BiTree T) {TElemType ch;cin >> noskipws >> ch; //不跳过空格if (ch == ' ')T = NULL; //输入空格表示空子树else {T = new BiTNode; //分配空间if(!T) //分配失败就退出throw new std::bad_alloc;T->degree = 0; //记录度(T)->data = ch;T->depth++; //度增加T->lchild=CreatBiTree(T->lchild); //递归创建左子树T->rchild=CreatBiTree(T->rchild); //递归创建右子树if (T->lchild != NULL)T->degree++; //有一个孩子度就加一if (T->rchild != NULL)T->degree++;}return T;}销毁二叉树：后序递归销毁左右子树（需要先查找到子树，销毁再销毁父亲树）void Tree::Release(BiTree T) {if (T != NULL) {Release(T->lchild); //递归销毁左子树Release(T->rchild); //递归销毁右子树delete T;}}//前序遍历void Tree::PreOrderTraverse(BiTree T, void(Tree::*Visit)(BiTree)) { if (T) /* T不空 */{(this->*Visit)(T); /* 先访问根结点 */PreOrderTraverse(T->lchild, Visit); /* 再先序遍历左子树 */PreOrderTraverse(T->rchild, Visit); /* 最后先序遍历右子树 */ }}//中序遍历void Tree::InOrderTraverse(BiTree T, void(Tree::*Visit)(BiTree)) {if (T){InOrderTraverse(T->lchild, Visit); /* 先中序遍历左子树 */(this->*Visit)(T); /* 再访问根结点 */InOrderTraverse(T->rchild, Visit); /* 最后中序遍历右子树 */ }}//后序遍历void Tree::PostOrderTraverse(BiTree T, void(Tree::*Visit)(BiTree)) {if (T){PostOrderTraverse(T->lchild, Visit); /* 先中序遍历左子树 */PostOrderTraverse(T->rchild, Visit); /* 最后中序遍历右子树 */(this->*Visit)(T); /* 再访问根结点 */}}//查找深度int Tree::TreeDepth(BiTree T) {int i, j;if (!T)return 0; /* 空树深度为0 */if (T->lchild)i = TreeDepth(T->lchild); /* i为左子树的深度 */elsei = 0;if (T->rchild)j = TreeDepth(T->rchild); /* j为右子树的深度 */elsej = 0;T->depth = i > j ? i + 1 : j + 1;return T->depth;}//得到层数void Tree::getLevel(BiTree T, int level){if (T){T->level = level;getLevel(T->lchild, level + 1); //得到左子树的层数，左子树根节点的层数比此节点多一getLevel(T->rchild, level + 1); //得到右子树的层数，右子树根节点的层数比此节点多一}}//非递归中序遍历void Tree::NoRecInOrderTraverse(BiTree T, void(Tree::*Visit)(BiTree)) {LinkedStack<BiTree> S;BiTree p = T;while (p || !S.isEmpty()) {if (p) {S.Push(p); //当节点不为空时就压栈，然后判断左孩子p = p->lchild;}else {p=S.Pop(); //返回到父节点(this->*Visit)(p); //访问p = p->rchild; //然后指向右节点}}}实验二：2、打印二叉树结构//中序遍历RDLvoid Tree::InOrderTraverseRDL(BiTree T, void(Tree::* Visit)(BiTree)) {if (T){InOrderTraverseRDL(T->rchild, Visit); /* 先中序遍历左子树 */(this->*Visit)(T); /* 再访问根结点 */InOrderTraverseRDL(T->lchild, Visit); /* 最后中序遍历右子树 */ }}//打印二叉树图形打印图形时，需要中序遍历RDL（先遍历右节点，再遍历右节点）。
