实现二叉树的各种基本运算的算法

实

验

报

告

课 程 数据结构教程

班 级 信息管理与信息系统

学 号

姓 名

实验项目数 １

2014年05月 说明：

1.实验预习：通过实验预习，明确实验目的要求、实验原理及相关知识点、实验方法、步骤以及操作注意事项等；对设计性实验要事先设计实验方案；根据需要合理设计实验数据记录表格。

2.实验过程：实际采用的实验方法、步骤、操作过程或实验设计方案（设计型实验）的描述。对于实验结果的表述一般有以下两种方法，在撰写实验报告时，可任选其中一种或两种方法并用，以获得最佳效果。

（1）文字表述:

根据实验目的将原始资料系统化、条理化，用准确的专业语言客观

（2）图表或图形表示: 利用表格、坐标图、绘画或利用记录仪器描绘出的曲线图，使实验结果突出、清晰、形象、直观。

3.数据分析、实验结论

（1）根据相关的理论知识对所得到的实验结果进行解释和分析，包括实验成功或失败的原因。

（2）不能因实验结果与预期的结果或理论不符而随意取舍甚至修改实验原始数据和伪造实验结果。如果实验失败，应找出原因及今后应注意的事项。

4. 任课老师可结合学科和专业课程特点，对实验报告内容作科学合理的调整。

5．学生在课程结束后将本门课程所有实验报告装订成册，任课教师负责收齐交实验室存档 实验 七 （实验项目序号）

数据结构教程 课程实验报告 实验地点：

实 验

名 称 实现二叉树的各种基本运算的算法 指 导 教 师 实验时间 2014-5-21

姓 名 学号 成绩

一、实验、训练目的

1. 了解如何创建二叉链；

2. 了解如何使用算法计算二叉链的宽度,节点个数,叶子节点个数；

一 、实验目的和要求

(1)掌握树的相关概念，包括树、节点的度、树的度、分支节点、叶子节点、孩子节点、双亲节

点、树的深度、森林等定义。

(2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。

(3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。

(4)掌握二叉树的性质。

(5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。

(6)重点掌握二叉树的基本运算和各种遍历算法的实现。

(7)掌握线索二叉树的概念和相关算法的实现。

(8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码的产生方法。

(9)掌握并查集的相关概念和算法。

(10)灵活运用二叉树这种数据结构解决一些综合应用问题。

二、实验内容

注：二叉树b为如图7-123所示的一棵二叉树

图7-123+

实验7.1 编写一个程序algo7-1.cpp,实现二叉树的各种运算，并在此基础上设计一个程序

exp7-1.cpp完成如下功能：

(1)输出二叉树b;

(2)输出H节点的左、右孩子节点值；

(3)输出二叉树b的深度；

(4)输出二叉树b的宽度；

(5)输出二叉树b的节点个数；

(6)输出二叉树b的叶子节点个数。

实验7.2设计一个程序exp7-2.cpp,实现二叉树的先序遍历、中序遍历和后序遍历和非递归算法，

以及层次变量里的算法。并对图7-123所示的二叉树b给出求解结果。

b+

A

C

F G

I

K

L+

N M+ E+

Hd

J D ₄ B 实验7.3对如图7-123所示的二叉树，设计一个程序exp7-3.cpp,完成如下功能：

(1)输出所有的叶子节点；

(2)输出所有从叶子节点到根节点的路径；

(3)输出(2)中的第一条最长的路径。

三 、 实验过程描述

实现二叉树的各种的基础程序algo7-1.cpp如下：

的1501-1.CPP

include《stdio.h》

巧妙地⽤⼆叉树完成算式计算算法计算器，⼆叉树，C++，独辟

蹊径

#01、引⾔，我们知道算式计算的问题是栈⾥⾯⼀个⾮常经典的题⽬。但是⽤栈来实现是⼀个⾮常⿇烦的过程，第⼀要解决算式判断，是否

为符合规则的算式，第⼆要由中最表达式转化为后缀表达式。这两个部分是栈实现计算算式表达式的⽐较复杂的地⽅。不仅如此，栈实现⾥

⾯的各种运算符的优先级，各种条件判断，可以说是⿇烦的要命。但是，实际上有⼀种数据结构⽐栈更适合解决这类问题。可以说是得天独

厚的优势。对，就是⼆叉树。例如⼀个表达式：1+2*3-4/5我们构造这样⼀个⼆叉树

当构造这样⼀个⼆叉树之后，解决表达式的值的⽅法，也就浮出⽔⾯了，把2和3相乘，存到*的节点中，然后再和1相加，存到+的节点中.....

最后根节点-节点中存放的就是最后的计算结果。就是叶⼦节点执⾏其双亲节点的运算，结果存到双亲节点中。

#02、选⼆叉树作为算法的存储结构有什么好处。

这主要有两个⽅⾯的好处，这也是针对于栈算法的两个⿇烦的地⽅。

<1>//免除了算式表达式的检查过程。为什么能免除检查，表达式的规范性呢？并不是不需要检查，⽽是检查的过程就包含在创建⼆叉树的过

程。认真分析这棵⼆叉树，我们会发现，所有的叶⼦节点必须是操作数节点，⽽所有的⾮叶⼦节点必须是运算符节点，否则表达式的结构⼀

点不正确，创建⼆叉树的过程就可以对表达式经⾏检查。表达式是否正确也只取决于两个⽅⾯，第⼀、表达式的结构是否正确，⽐如不能出

现2*+6这样的表达式，第⼆、表达式的数据是否正确，例如不能出现1+2.2.3这样的表达式，2.2.3不是⼀个符合规则的数据。⽽数据的检

查，也可以在给叶⼦节点赋值的时候检查。所以避免的单独经⾏表达式检查的繁琐。

<2>//不需要转化为后缀表达式再经⾏表达式结果的计算，这也是得益于⼆叉树这种结构的天然优势，⾃我感觉就完全是为这种算法题设计

的，天造地设嘛！

#03、算法实现

0x001、数据结构的定义：

信息学奥赛培训之『树——二叉树』

- 1 - 树——二叉树

引：为何要重点研究二叉树？

（1）二叉树的结构最简单，规律性最强；

（2）可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

一、二叉树基础

1. 二叉树的定义

二叉树是一类非常重要的树形结构，它可以递归地定义如下：

二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点以及分别称为左子树和右子树的两棵互不相交的二叉树。

因此，二叉树的根可以有空的左子树或空的右子树，或者左、右子树均为空。

二叉树有5种基本形态，如图1所示。

图1 二叉树的5种基本形态

在二叉树中，每个结点至多有两个儿子，并且有左、右之分。因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子。

注意：二叉树与树和有序树1的区别

二叉树与度数不超过2的树不同，与度数不超过2的有序树也不同。在有序树中，

1 如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。 信息学奥赛培训之『树——二叉树』

- 2 - 虽然一个结点的儿子之间是有左右次序的，但若该结点只有一个儿子时，就无须区分其左右次序。而在二叉树中，即使是一个儿子也有左右之分。例如图2-1中(a)和(b)是两棵不同的二叉树。虽然它们与图2-2中的普通树(作为无序树或有序树)很相似，但它们却不能等同于这棵普通的树。若将这3棵树均看作是有序树，则它们就是相同的了。

图2-1 两棵不同的二叉树

图2-2 一棵普通的树

由此可见，尽管二叉树与树有许多相似之处，但二叉树不是．．树的特殊情形。

2. 二叉树的性质

图3 二叉树

性质１： 在二叉树的第i层上至多有12i结点(i>=1)。

性质２： 深度为k的二叉树至多有12k个结点(k>=1)。