logo资料库

广州大学 数据结构实验报告 实验二 二叉树的操作与实现.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.20M 资料格式：doc 举报 版权申诉
第1页 / 共20页
第2页 / 共20页
第3页 / 共20页
第4页 / 共20页
第5页 / 共20页
第6页 / 共20页
第7页 / 共20页
第8页 / 共20页
资料共20页，剩余部分请下载后查看
    广州大学学生实验报告 开课实验室：计算机科学与工程实验（电子楼 517） 学院 计 算 机 科 学 与 网 络 工 程 学院 年级、专 业、班 实验课程 实验项目 一、实验目的： 姓名 数据结构实验 实验二 二叉树的操作与实现 学号 成绩 指导 老师 1、二叉树的基本操作算法实现 2、二叉树的各种遍历算法实现 3、线索二叉树的遍历 4、构造哈夫曼树和哈夫曼编码的算法实现 二、使用仪器、器材 微机一台 操作系统：WIN10 编程软件：C++ 三、实验内容及原理 利用二叉树的二叉链式存储结构设计并实现各种操作算法。 1. 二叉树的基本操作算法实现 （1）利用二叉树字符串“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建二叉树的二 叉链式存储结构； （2）输出该二叉树； （3）输出‘H’节点的左、右孩子结点值； （4）输出该二叉树的结点个数、叶子结点个数、二叉树的度和高度； （1）第一步操作为二叉树的创建。默认用户是通过先序次序输入这一串字符串，通过递 归的方法来建立这个二叉树，以“#”作为作为递归结束的标志，首先建立根节点，将根 节点的值置为 s，再通过先序次序先递归创建左子树，后递归建立右子树；
    （2）第二步操作为二叉树的输出。采用先序遍历的方法进行递归处理，若二叉树不为空， 先输出根节点的值，再进行先序遍历左子树，再先序遍历右子树，如此进行递归处理； （3）第二步操作为二叉树的查找。采用先序遍历的方法进行递归处理，若二叉树不为空， 先判断根节点的值是否与查找的值相同，若不相同，先进行先序遍历左子树，再先序遍 历右子树，如此进行递归处理，直到找到该节点并输出其左右孩子结点的值； （4）计算二叉树的结点个数、叶子结点个数、二叉树高度都先序遍历的方法进行递归处 理。 计算二叉树的结点个数时返回值为根节点左子树的先序结果加右子树的先序结果再加 一，实现二叉树结点个数的计算； 计算叶子结点个数若根结点的左右孩子都为空，返回值为；否则返回根结点的左子树先 序结果加右子树的先序结果； 计算二叉数的高度，分别递归计算左子树和右子树的深度，比较两个值的大小，二叉树 的高度为两个值的较大值加一的结果； 2. 二叉树的各种遍历算法实现 实现上述二叉树的先序、中序和后序遍历的递归和非递归算法； （1）二叉树先序遍历递归： 若二叉树非空，则先输出根结点的值，再先序遍历左子树，最后先序遍历右子树； （2）二叉树中序遍历递归： 若二叉树非空，则先中序遍历左子树，再输出根结点的值，最后中序遍历右子树； （3）二叉树后序遍历递归： 若二叉树非空，则先后序遍历左子树，再后序遍历右子树，最后输出根结点的值； （4）二叉树先序遍历非递归： 非递归的实现方法需要结合链栈压栈和出栈操作，通过压栈保留二叉树，并通过后 面出栈操作以达到和递归相同的效果。先创建一个二叉树，等于原二叉树，再新建一个 链栈，对此二叉树进行操作。当二叉树或链栈不为空时进行一个循环，在循环中再建立 一个当二叉树不为空的循环，满足此条件时，二叉树一直转向左孩子并将其沿途结点打 印出后压入链栈中，直至此循环结束；循环结束后若链栈不为空时，进行出栈操作，将
    其中栈顶指针保留二叉树弹出链栈，返回栈顶指针保留的新的二叉树，并随后此二叉树 转向其右孩子，此为一次总的循环操作，依次类推，直至先序遍历输出整个二叉树； （5）二叉树中序遍历非递归： 方法与先序遍历的相似，但更改为在出栈后打印二叉树的结点； （6）二叉树后序遍历非递归： 需要新建两个链栈，基本操作与先序遍历的相似，但同时对两个链栈进行压栈操作， 但一开始与先序遍历相似只对其中一个进行出栈操作。第二个循环中改为转向其右孩子， if 语句中出栈操作结束后，将二叉树改为转向其左孩子。由于后序操作是在后序遍历左 孩子和右孩子后再在输出根结点的值，所以另外一个链栈的作用是一开始不进行出栈操 作，将每一步遍历得到的二叉树的结果压入栈内，在最后时才对此链栈进行出栈操作， 输出每一个二叉树的根结点。 3. 线索二叉树的遍历 中序线索化上述二叉树并找出根结点的前驱和后继。 （1）中序线索化二叉树 根据线索二叉树的定义，将按照先序输入的二叉树中序线索化，其过程与中序遍历 的递归方法相似，修改其中结点处理的代码。 首先新建一个全局变量，达到保留其前驱的结果，首先建立一个头指针，其指向我 们先序输入的字符串的根结点，其中右孩子指针默认作为一个线索，初始化右孩子指向 自己，当二叉树为非空时，将头指针指向根节点再给全局变量赋值为头指针，接着调用 中序线索化的算法将二叉树线索化。最后需要进行收尾工作，将全局变量的右孩子指向 投掷症，并作为线索，而头指针的右孩子指向全局变量。 中序线索化的具体算法为以下内容。首先当二叉树不为空时，进行左 子树递归线索 化，直到其根结点的左孩子为空，给根结点施加一个做线索，将全局变量始终指向刚刚 访问过的结点，然后将左孩子的指针指向全局变量，为前驱；由于未访问结束的结点是 并不知道其后继结点为哪个，所以只有当访问结束后，返回操作这个全局变量即刚刚访 问过的这个结点，来确定其后继结点，若全局变量为空，则给根结点施加一个做线索， 然后将右孩子的指针指向根结点，为后继。最后保持全局变量指向刚才得到的前驱，并
    最后进行右子树的递归线索化。 （2）查找根结点的前驱和后继 ①查找根结点的前驱： 若根结点的 LTag 为 1，则根结点的左链指示其前驱； 若根结点的 LTag 为 0，则说明根结点有左子树，结点的前驱是遍历左子树时最后访 问的一个结点。 ②查找根结点的后继： 若根结点的 LRag 为 1，则根结点的右链指示其后继； 若根结点的 LRag 为 0，则说明根结点有右子树，结点的后继是遍历右子树时访问的 第一个结点。 4. 构造哈夫曼树和哈夫曼编码的算法实现 统计下面一段英文的不同字符个数和每个字符的出现频率，利用统计数据构造构造哈 夫曼树和哈夫曼编码。 The Chinese official said he viewed the Trump Presidency not as an aberration but as the product of a failing political system. This jibes with other accounts. The Chinese leadership believes that the United States, and Western democracies in general, haven’t risen to the challenge of a globalized economy, which necessitates big changes in production patterns, as well as major upgrades in education and public infrastructure. In Trump and Trumpism, the Chinese see an inevitable backlash to this failure. （1） 第一步为哈夫曼树的初始化； 统计出这段英文的字符一共有 n=35 种，定义一个为有 m=2*n-1 个元素的数组，由于零号 元素不用，所以实际定义是要加一。首先将 1~m 号单元的双亲和左右孩子的下标均置为 零，由于叶子结点集中储存在前面部分 1~n 号单元，而后面的 n-1 个位置为非叶子结点， 然后再输入 1~n 号单元的元素设置好其权值。
    （2） 第二步为哈夫曼树的构建； 需要进行 n-1 次合并，产生 n-1 个新结点，将新产生的结点放在 n+1~2n-1 号单元，在 1~n 中未选过的根结点，即双亲为 0 的结点中选取两个权最小，修改其双亲的值，新的 结点则由这两个结点作为其左右孩子产生，这个新结点的权重则为这两个左右孩子权重 的和； （3）第三步为哈夫曼编码的实现。由于编码的特点，为简单实现操作，从叶子结点开始 操作，即从 1~n 中进行处理，生成这个 n 个字符的哈夫曼编码。从叶子节点反复地向上 回溯，直至根结点，通过判断双亲域是否 0，若为 0，则结束；不为 0，则继续。每一次 的回溯判断其左孩子是否与我们需要找的点是否一样，一样时，若寻找的结点为回溯结 点的左孩子则生成代码 0，右孩子则生成代码 1，回溯到根结点后，得到这个字符额编码， 每一个字符都有若干 0、1 组成的哈夫曼的编码，即 n 个字符就有 n 个由 0、1 组成的字 符串，需要建立一个由字符串构成的数组，由于每一字符编码的长度不能确定，为了节 省空间，先建立一个一维数组用于临时存放这个字符的编码，最后将这个编码的长度分 配给原先的字符串数组，最后再将编码复制到这个数组中，保留这个字符的编码，由于 求得的编码是由叶子结点开始的，所以需要一个复制函数，将编码从后往前复制到数组 中。 四、实验过程原始数据记录 1、二叉树的基本操作算法实现 （1） void CreatBitTree(BiTree *t)//创建二叉树 { char s; cin >> s; if (s == '#') {
    *t = NULL; } else { *t = (BiTNode *)malloc(sizeof(BiTNode));//生成一个BiTNode结构的结点，强制类型转换为 BiTNode的指针 (*t)->data = s; CreatBitTree(&(*t)->lchild);//默认用户用前序遍历的方式输入数据 CreatBitTree(&(*t)->rchild); } } （2） void PreOrderTraverse(BiTree t)//输出操作 if (t) { } cout << t->data; PreOrderTraverse(t->lchild); PreOrderTraverse(t->rchild); { } （3） void visit(BiTree t,char i)//查找操作 { if (t) {
    if (t->data == i) { if (t->lchild && t->rchild ) { cout << "左孩子结点为：" << t->lchild->data << " " << "右孩子结点为：" << t->rchild->data << endl; } else if (t->lchild==NULL&& t->rchild!=NULL) { } cout << "无左孩子结点" << " " << "右孩子结点为：" << t->rchild->data << endl; else if (t->lchild != NULL && t->rchild == NULL) { } cout << "无右孩子结点" << " " << "左孩子结点为：" << t->lchild->data << endl; else if (t->lchild == NULL && t->rchild == NULL) { } cout << "该结点为叶子结点，无左右孩子结点" << endl; } else { } } } visit(t->lchild, i); visit(t->rchild, i);
    （4） int Depth(BiTree t)//计算深度 { if (t==NULL) return 0; { } else { int m = Depth(t->lchild); int n = Depth(t->rchild); if (m > n) { } else return m + 1; return n + 1; } } ________________________________________________________________________________________________ int LeafCount(BiTree t)//计算叶子结点 { if (t == NULL) return 0; { } else {
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料