二叉树的可视化实现

二叉树的可视化实现（精选8篇）

二叉树的可视化实现 第1篇

二叉树是数据结构非常重要的一种非线性结构，是树型结构的一种特殊形式，在计算机处理领域有着广泛的应用。况且对二叉数的大部分操作，都是在遍历过程中实现的，在许多教材中，都指出了如何对二叉数进行遍历，但并没有对如何通过二叉数的遍历序列还原二叉数作更详尽的介绍，本文就针对如何由二叉数的遍历序列还原二叉数的算法方面进行分析研究，并在turboC中实现此算法。

一、二叉数的定义

是有限元素的集合，是另一种树型结构，它可以为空，也可以由树根结点和至多两棵子树组成，每棵子树内部又是一棵二叉数。在二叉树中，每个结点的左子数的根结点被称之为左孩子，右子树的根结点被称之为右孩子。

二、二叉树的遍历

从二叉数的定义或组成可以知道，标准二叉数包括树根和左右子数三个部分。而且二叉树是递归定义的，换句话说，二叉树的每棵子树中，也是由这三个部分组成的。所以，寻找对二叉树进行遍历的规律，实际上就是研究对这三个部分访问顺序的规律。按照数学排列组合的方法，这三个部分有六种不同的访问顺序：DLR、DRL、LDR、RDL、LRD、RLD。其中D代表树根，R代表右子树，L代表左子树。但六种不同的访问顺序又可以分为从左到右和从右到左的两组，每组有三种不同的访问顺序。两组不同的访问顺序对称的，因此，只考虑其中一组即可。

这里以从左到右的一组为例，有DLR、LDR、LRD三种访问顺序，我们以访问根结点的顺序，对它们分别命名为先根遍历、中根遍历、后根遍历。

1、先根遍历（前序遍历）

若二叉树为空，则不访问任何结点。若二叉树不为空，则其访问顺序为：

(1)访问根结点

(2)先根遍历左子树

(3)先根遍历右子树

2、中根遍历（中序遍历）

若二叉树为空，则不访问任何结点，若二叉树不为空，则其访问顺序为：

(1)中根遍历左子树

(2)访问根结点

(3)中根遍历右子树

3、后根遍历 (后序遍历)

(1) 后跟遍历左子树

(2)后跟遍历右子树

(3)访问根结点

由前序和中序遍历或者由中序和后序遍历序列，可以唯一确定一颗二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。

三、还原二叉数的步骤与算法

1、由先序和中序遍历还原二叉树的步骤为：

画出先序遍历序列的第一个结点，即二叉树的根结点

在中序遍历序列中找到根结点，以此为界分别数出二叉树根结点的左、右子树的结点个数

依照左、右子树的结点个数由先序遍历序列的第二个结点数起，分别找出左、右子树的先序遍历序列

由左至右，对二叉树的非空子树重复以上步骤，直至所有结点全部画出

2、由先序和中序遍历还原二叉树的算法为：

3、由后序和中序遍历还原二叉树的步骤为：

画出后序遍历序列的最后一个结点即为二叉树的根结点

中序遍历序列中找到根结点，以此为界数出二叉树根结点的左子树结点个数

依照左子树的结点个数由后序遍历序列的第一个结点数起，则可分别找出左、右子树的后序遍历序列

从左至右，对二叉树的非空子树重复以上步骤，直至所有结点全部画出。

4、由后序和中序遍历还原二叉树的算法为：

结束语

在许多的教材中都只对二叉树的三种遍历给出了算法描述，却没有提到如何由遍历序列来确定二叉树，但掌握各个序列间的相互联系，学会利用二叉树的各种遍历序列特性去还原二叉树在实际应用中恰恰是不容忽视的问题，本文对如何还原二叉树的问题进行了说明，并用Turbo C语言编写并验证了相应的算法代码。

摘要：二叉树是一种常用的数据结构, 它的实际应用十分广泛。二叉树的遍历有三种方式, 分别为先序, 中序和后序, 本文针对如何由二叉树的遍历序列还原二叉树的问题, 提出了由先序遍历和中序遍历或后序遍历和中序遍历唯一确定一棵二叉树的算法, 并对这两种算法进行了分析描述, 并在turboC中得以实现。

关键词：先序遍历,中序遍历,后序遍历,还原,二叉树

参考文献

[1]严蔚敏、吴伟民:《数据结构》, 清华大学出版社, 2007年。

实验10 二叉树的基本操作 第2篇

课程名称

数据结构基础

实验项目名称

实验十

二叉树的基本操作

实验成绩

指导老师（签名）

日期

一.实验目的和要求

1、掌握二叉树的链式存储结构。

2、掌握在二叉链表上的二叉树操作的实现原理与方法。

3、进一步掌握递归算法的设计方法。

二.实验内容

1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。

二叉树二叉链表存储表示如下： struct BTreeNode {

ElemType data;

// 结点值域

BTreeNode *lchild , *rchild;// 定义左右孩子指针 };基本操作如下：

①void InitBTree(BTreeNode *&BT);

//初始化二叉树BT

②void CreateBTree(BTreeNode *&BT, char *a);

//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构

③int EmptyBTree(BTreeNode *BT);

//检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree(BTreeNode *BT);//求二叉树BT的深度并返回该值

⑤int FindBTree(BTreeNode *BT, ElemType x);

//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0

⑥void PreOrder(BTreeNode *BT);//先序遍历二叉树BT ⑦void InOrder(BTreeNode *BT);//中序遍历二叉树BT ⑧void PostOrder(BTreeNode *BT);

//后序遍历发二叉树BT

⑨void PrintBTree(BTreeNode *BT);

//输出二叉树BT ⑩void ClearBTree(BTreeNode *&BT);

//清除二叉树BT

2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h中，并在主函数文件test4_1.cpp中添加相应语句进行测试。①void LevelOrder(BTreeNode *BT)//二叉树的层序遍历

②int Get_Sub_Depth(BTreeNode *T , ElemType x)//求二叉树中以元素值为x的结点为根的子树的深度

3、填写实验报告，实验报告文件取名为report10.doc。

4、上传实验报告文件report10.doc、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。

三.函数的功能说明及算法思路

（包括每个函数的功能说明，及一些重要函数的算法实现思路）函数：void InitBTree(BTreeNode *&BT)功能：初始化二叉树BT 思路：将BT指向NULL

函数：void CBTree(BTreeNode *&BT)功能：输入二叉树

思路：按先序次序输入二叉树中结点的值（一个字符）特殊字符 $ 表示空树

函数：void PBTree(BTreeNode *BT,int n)功能：横向打印二叉树

思路：先递归输出右子树，按层次输出空格和“---”控制格式，再输出当前结点值，最后递归左子树

函数：void CreateBTree(BTreeNode *&BT, char *a)功能：根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构

思路：根据广义表表示的”(”,”)”和”,”等字符来构建二叉树，用栈S来存储根结点指针，用p来接收当前结点值数据并链接为栈顶元素的左/右孩子

函数：int EmptyBTree(BTreeNode *BT)功能：检查二叉树BT是否为空，空返回1，否则返回0 思路：返回判断BT是否指向NULL

函数：int DepthBTree(BTreeNode *BT)功能：求二叉树BT的深度并返回该值

思路：若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加1

函数：int FindBTree(BTreeNode *BT, ElemType x)功能：查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0

思路：类似于前序遍历，若空树则返回0。若根结点值等于查找值x则返回1，否则先调用函数本身查找左子树，还未找到则再查找右子树，所有操作完成均为找到，则返回0

函数：void PreOrder(BTreeNode *BT)功能：先序遍历二叉树BT 思路：使用“根左右”的顺序遍历二叉树

函数：void InOrder(BTreeNode *BT)功能：中序遍历二叉树BT 思路：使用“左根右”的顺序遍历二叉树

函数：void PostOrder(BTreeNode *BT)

功能：后序遍历二叉树BT 思路：使用“左右根”的顺序遍历二叉树

函数：void PrintBTree(BTreeNode *BT)

功能：输出二叉树BT 思路：按照广义表表示方法输出二叉树（与输入时相同）

函数：void ClearBTree(BTreeNode *&BT)

功能：清除二叉树BT 思路：按照先子树后根结点的顺序删除二叉树

函数（选作）：void LevelOrder(BTreeNode *BT)功能：二叉树的层序遍历

思路：初始化一个空队列，若二叉树为空，则空操作；否则，树根指针入队列。当队列非空时循环：出队首元素，并输出该元素（指针）所指结点的值；且若该结点存在左右孩子，则左右孩子指针进队列。输出结果就是层序遍历序列

函数（选作）：求二叉树中以元素值为x的结点为根的子树的深度 功能：int Get_Sub_Depth(BTreeNode *T , ElemType x)思路：在FindBTree函数的基础上修改，将找到结点时的返回值改为调用DepthBTree求出以该结点为根结点的子树深度即可

四.实验结果与分析

（包括运行结果截图、结果分析等）

测试数据：a(b(c),d(e(f,g),h(,i)))，abc$$$def$$g$$h$i$$ 结果分析：针对该二叉树，程序输出深度为4，正确；查找值f能够找到，正确；先序遍历结果为a b c d e f g h i，正确；中序遍历结果为c b a f e g d h i，正确；后续遍历结果为c b f g e I h d a，正确；输出二叉树的结果与输入一致，正确；使用先序输入二叉树和横向输出部分正确。选作部分，层序遍历结果为a b d c e h f g i，正确；以结点d为根结点的子树深度为3，正确。

五.心得体会

（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）

基于二叉树的递归程序算法实现策略 第3篇

递归在程序设计基础、数据结构以及算法设计与分析等课程的教学中都占用重要地位, 是一类重要的程序设计方法, 但递归教学一直是个难点。学生通常会对为何用递归、如何用递归以及递归程序的执行过程存在疑惑。本文旨在解决这一问题, 全文以递归为中心, 从什么是递归、为何用递归、如何用递归以及使用递归需要注意的问题四个方面组织全文, 从方法论的角度对递归程序设计进行系统的阐述。文中一方面结合汉诺塔问题和N皇后问题等经典实例介绍了递归程序设计的一般步骤和方法, 还介绍了如何通过分治和回溯等策略进行递归程序设计。

2. 递归程序的实现策略

进行递归程序设计的关键是借助递归关系的定义和递归边界构造递归函数, 但有些问题的描述中递归关系和递归边界并没有显示给出, 称此类问题为隐式递归问题。

对于显示递归问题, 如前所述, 直接根据递归关系的定义和递归边界构造出递归函数即可求解;对于隐式递归问题则要通过一定的策略来找出隐藏的递归关系和递归边界, 常见策略如降阶、分治和回溯。

2.1 分治

若操作对象可定义成由若干结构相同但规模更小的部分组成, 则对原对象的操作可递归分解到其各组成部分上分别进行, 如此递归分解直到不可再分时停止, 此类求解策略称为分治。根据分治策略很容易得到相应的递归关系定义和递归边界, 从而构造出具体的递归函数。

如非空的二叉树可看作为由根结点、根节点的左子树以及根结点的右子树三部分组成, 每一部分又都是一颗树。如右图所示二叉树T可看作由根节点A、结点B、C构成的左子树和结点D、E、F构成的右子树组成。欲设计递归函数Node Count (T) 求二叉树T的结点总数, 显然T的结点数是T的左子树结点数与T的右子树结点数之和再加1, 这实际就是递归关系的定义:

再注意到空树的结点树为0, 依次作递归边界, 即可得到表4所示所示的树结点计数的递归函数。

2.2 回溯

回溯也是一种问题求解策略, 通常指让计算机从某种可能的情况出发自动向前进行搜索, 碰到符合的情况就输出或者保存起来, 在一条路径上走到“尽头”后就回到原来的岔路口选择一条以前没有走过的路重新向前进行探测, 直到找到解或者走完所有路径为止。回溯具体编程实现时通常都用递归:“向前进行搜索”对应递归调用, “尽头”对应递归边界。

比如N皇后问题。题目是说, 一个N*N的国际象棋棋盘上主放置N个皇后, 使其不能相互攻击, 即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上, 要求输出所有可能的摆放方案。其实, 题目就是要找出所有可能的合法情况, 可以考虑用回溯法求解。

让计算机逐行前进, 每行摆放一个棋子, 若合法则前进到下一行。为此可设递归函数void NQueens (int arr[N][N], int i) ;第一个参数代表棋盘, 第二个参数代表目前标号为0的行到标号为i-1的行已经各有一个棋子, 且符合规则要求。递归函数第一次被调用时时形参i值应为0, 函数体内递归调用语句应为NQueens (arr, i+1) 。至此递归关系定义已经找到, 但还有一个问题, 即递归何时停止或者说计算机前进过程中如何判断是否“走到尽头”。分析可见共有两种情况:其一, 当前行下完一个棋子后出现了非法情况, 如同一列或同一斜线上出现了多个皇后, 此时应抹掉该行所下棋子, 在其右侧重新下一个棋子再重新检查;其二, 当前行下完一个棋子后仍然合法, 但恰巧当前行是最后一行, 这实际意味着已经得到了一种合法的摆放方案, 此时应输出该方案, 之后抹掉该行所下棋子, 在其右侧下一个棋子重新检查。由上述递归边界和递归关系定义可构造递归函数如下:

通过上例可见, 回溯法的主要特点是递归结束的条件在搜索的最后一步, 关键是找到递归边界条件。

3. 递归存在的问题

使用递归进行程序设计思路清晰、代码简洁, 但递归调用过程中, 每一次发生调用系统都要将返回地址、局部变量等信息入栈保存, 因此, 递归程序的运行效率较低, 而且递归次数过多还容易造成栈溢出。此外, 尤其要避免重复递归调用的现象发生。比如求Fibnacci数列的第n项可通过递归函数实现:

假设n=4则递归执行过程中发生的递归调用如图2所示, 可见n=4时f (1) 已经被重复调用了3次。在Core 2CPU T5500、内存1G的机器上进行测试, 计算f (40) 约需20.374秒的时间, 其主要原因在于计算f (40) 时f (1) 会被重复调用165580141次;而计算f (50) 更是需要40多分钟!

4. 结束语

本文系统讲述了递归的基本概念、使用递归进行程序设计的好处以及如何设计递归程序, 结合Hanoi塔问题、N皇后问题等经典实例介绍了通过降阶、分治及回溯构造递归函数的一般化方法, 并对递归使用过程中可能存在的问题进行了说明。总地来说, 递归作为一种重要的程序设计方法可使得编码清晰易懂, 但存在运行效率较低的问题, 在实际应用当中, 建议仅当传统方法不方便求解时使用递归。

参考文献

[1]谭浩强, C程序设计, 清华大学出版社, 北京:2005.7

二叉树的可视化实现 第4篇

数据结构中四种最基本的逻辑结构为集合、线性结构、树和图[1], 栈和二叉树分别属于线性结构和树。在实际应用中, 每种数据结构并不是独立存在的, 他们通常相互结合起来以实现某些应用, 如二叉树的非递归遍历就需要利用栈来实现。

2、用栈结构实现二叉树的非递归中序遍历算法

2.1 二叉树的遍历

非空二叉树是由根结点加上左子树和 (或) 右子树组成, 而每颗子树又都是二叉树, 不妨用L、D、R分别表示非空二叉树的左子树、根、右子树。二叉树的遍历是指按某种规律周游二叉树, 对树中的每个结点访问且仅访问一次的过程。对于二叉树的三个组成部分L、D、R, 实现遍历的方案就是将这三个组成部分进行排列组合, 共有六种遍历方法:LDR、LRD、DLR、DRL、RLD、RDL。如果限定按照先左后右的规律遍历, 则二叉树的遍历可以分为DLR、LDR、LRD, 即先根序、中根序和后根序。

2.2 二叉树的递归中序遍历

非空二叉树的中序遍历算法如下:

(1) 中序遍历左子树

(2) 访问根结点

(3) 中序遍历右子树

二叉树的中序递归算法实现如下:

以图1所示的二叉树为例说明中序遍历的过程。

图2中箭头上面的数字表示程序执行的顺序, 因此图1所示的二叉树的中序遍历序列为DBAFC。由上面递归算法的执行顺序可以看出完全符合先进后出的栈的特点, 因此可以将递归的算法转化成用栈结构的非递归的算法。

2.3 利用栈结构实现二叉树的非递归中序遍历

将二叉树的递归中序遍历转换成非递归程序需要利用栈来保存沿途的结点信息, 待叶子结点访问完后, 在按照先进后出的顺序依次出栈, 利用栈结构实现二叉树的非递归中序遍历的算法步骤如下:

(1) 建立一个空栈S;

(2) 把指示二叉树的根结点T入栈;

(3) 如果栈S不为空, 则转 (4) 遍历左子树, 否则结束返回;

(4) 读栈顶结点, 如果它不是一个空结点, 则把栈顶记录结点的左孩子 (左子树根结点) 入栈, 否则转 (5) ;

(5) 栈顶的空指针退栈;

(6) 如果当前栈S不为空, 则转 (7) , 否则转 (3) ;

(7) 栈顶元素出栈, 访问这个栈顶元素, 若访问这个栈顶元素失败, 则报错结束算法, 否则把刚访问过的才出栈的那个结点的右孩子入栈然后转 (3) 。

用C语言实现上述算法如下:

3、结束语

二叉树是普遍存在且被广泛应用的一种基本的数据结构之一, 文中例举了二叉树的遍历分类, 从遍历的过程分析入手, 结合栈的先进后出特征, 归纳了二叉树的非递归算法。

摘要：二叉树作为数据结构中的一个重要的部分, 有着广泛的应用, 其中二叉树的遍历是二叉树操作的根本。文中通过分析二叉树的中序遍历过程, 结合栈的先进后出特点, 归纳出二叉树的中序遍历非递归算法。

关键词：二叉树,中序遍历,非递归

参考文献

浅析二叉树的遍历 第5篇

二叉树是一种特殊的树, 特别适合于计算机处理。二叉树是个有限元素的集合, 该集合或者为空, 或者由一个称为根的元素及两个不相交、被分别称为左子树和右子树的二叉树组。在这里我们不讨论空树。

所谓遍历是指沿着某条搜索路线, 依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是对树的一种最基本的运算也是一种重要操作, 许多对树的操作都要基于遍历的。根据二叉树的结构特征, 可以有三类搜索路径:先上后下的按层次遍历、先左 (子树) 后右 (子树) 的遍历、先右 (子树) 后左 (子树) 的遍历。设访问根结点记做D, 遍历根的左子树记做L, 遍历根的右子树记做R, 则遍历二叉树有6种规则:DLR、DRL、LDR、LRD、RDL及层次遍历。若规定二叉树中必须先左后右 (左右顺序不能颠倒) , 则只有DLR、LDR、LRD及层次遍历四种遍历规则。所以二叉树的遍历分为:前序遍历、中序遍历、后序遍历和层次遍历。

(1) 前序遍历 (DLR) :按照“根 (D) 左子树 (L) 右子树 (R) ”的次序遍历二叉树。首先访问根, 按前序遍历左子树, 按前序遍历右子树。这是由上至下的推算过程。首先访问根, 如左图所示, A作为根首先被访问, 接着访问左结点B, 而B是DE的根, 根据DLR遍历要求, D作为B的左结点被接着访问, 而D是HI的根, 再访问过D后, H作为D的左结点被访问, 接下去访问D的右结点I。因为HI之下没有结点了, 回到被访问过的D处, E作为B的右结点被访问, J是E的左结点被访问。此时, A的左子树全部被访问, 接下去访问右子树, C是A的右结点被访问, FG作为C的左右结点被访问。所以左图的前序遍历结果序列:ABDHIEJCFG.

前序遍历递归算法如下:

(2) 中序遍历 (LDR) :按照“左子树 (L) 根 (D) 右子树 (R) ”的次序。首先遍历左子树, 访问根, 按中序遍历右子树。我们首先都考虑ABC这个二叉树, B作为A的左结点应该先被访问, 但是B又是DE的根, 所以不能先被访问, 那就看B的左结点D, 但是D是HI的根, 所以也不能被先访问。再看D的左右结点, H和I之下没有结点了, 所以访问从这里开始了。这是由上至下的推算过程, 但是遍历却是由下至上的。先考虑左子树, H作为D的左结点被最先访问, D为根, I是D的右结点被访问, 推进一层, B作为D的根被访问, 接下去应该访问B的右子树了, 但是B的右结点E有个左结点J, 根据规则左子树先根被访问, 所以J先与E被访问。这时候根A的左子树被全部访问, 根据规则A先于右子树被访问。接下去考虑A的右结点C, 但是C是FG的根节点, 所以F作为左结点先于C被访问, 接下去才是C和C的右结点G。所以上图的中序遍历结果序列为:HDIBJEAFCG

中序遍历递归算法如下:

(3) 后序遍历 (LRD) :按照“左子树 (L) 右子树 (R) 根 (D) ”的次序。考虑方法和中序遍历一样, 首先考虑ABC这个树, 按照规则B将先被访问, 但是B是DE的根, 同理可以知道D也不能先访问。考虑D的左右结点, HI之下没有结点了, 所以HI被先访问, D作为根被访问。D被访问后应该访问B的右结点E, 但是E还有个左结点J, 所以J被先访问, 然后是E和B。至此A的左子树被遍历, 现在考虑右子树, C作为A的右结点应被最先考虑, 但是C又是FG的根结点。根据规则先访问F和G, 然后是根C。A作为BC的根结点被最后访问。得到后序遍历结果序列为:HIDJEBFGCA

后序遍历递归算法如下:

(4) 层次遍历:这是二叉树遍历中最简单的遍历。按照层次访问, 即按照从上层到下层, 同层内从左到右的次序访问结点。上图的层次遍历结果序列:ABCDEFGHIJ

二叉树遍历看似简单, 但是也容易出错。最主要一点是, 在遍历过程中, 不要把结点简单的单做子结点或者根结点, 有些结点分饰几角, 有不同的身份。有些子结点也是其他结点的根结点, 要仔细考虑。当然, 只要你细心, 多方面考虑, 牢记各种遍历规则, 就能准确把握二叉树的遍历。

摘要：二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式, 即使是一般的树也能简单地转换为二叉树, 而且二叉树的存储结构及其算法都较为简单, 掌握二叉树的遍历对于二叉树的学习有重要作用。

关键词：二叉树,遍历

参考文献

表达式与二叉树的相互转换 第6篇

数学表达式求值是程序设计语言编译中的一个最基本问题。因此,数学表达式、栈的操作、二叉树的遍历,这几个概念在数据结构的教材中往往经常出现。表达式的求值过程是栈应用的一个典型例子,用它来研制出电子计算器:当用户输入一个由数据(操作数)和运算符组成的算术表达式,计算器使用一个堆栈来计算运算结果。当然表达式也有几种形式:前缀表达式、中缀表达式、后缀表达式。因此,又出现了前缀计算器、中缀计算器(常见的计算器)、后缀计算器。对于中缀表达式就是我们常用的数学表达式中去掉括号的部分表达式,是经常可看见的;但是,前缀表达式和后缀表达式是怎么得出来的呢?我们的数据结构教材中是将一个数学表达式或者中缀表达式以及其所表示的二叉树,对该二叉树的前序遍历得到前缀表达式,对该二叉树的中序遍历就得到中缀表达式,对该二叉树的后序遍历就得到后缀表达式,再根据这些表达式用堆栈来实现,以得到不同的计算器。也就是说,教材中所阐述的过程是这样的:数学表达式(中缀表达式)+该表达式的二叉树二叉树的遍历前缀表达式、中缀表达式、后缀表达式栈的实现前缀计算器、普通计算器、后缀计算器。用图形表示其过程如下:

初看起来显然是比较合理的,但是我们的教材上从来没有提到过怎样得到该“数学表达式”的“二叉树”。本文正想阐明怎样由一个“表达式”得出其相应的“二叉树”。

2 相关术语

2.1 中缀表达式

就是运算符(操作符)在两个运算对象(操作数)中间的表达式。如:A+B,C*D-E。

2.2 前缀表达式

就是在一个数学表达式中,运算符(操作符)在两个运算对象(操作数)之前的表达式。如:+AB,-*CDE。前缀表达式又称波兰式(PN,Polish Notation)。

2.3 后缀表达式

就是在一个数学表达式中,运算符(操作符)在两个运算对象(操作数)之后的表达式。如:AB+,CD*E-。后缀表达式又称逆波兰式(RPN,Reverse Polish Notation)。

2.4 表达式树

就是将一个数学表达式用一棵二叉树表示。其中,运算对象作为树的叶子结点(没有后继的结点),运算符作为树的非叶子结点。如图1,图2所示。

2.5 二叉树的三种遍历

1)先根(先序)遍历:先遍历根结点,再先根遍历左子树,再先根遍右子树。对于上面的图1、图2分别为:+AB,-*CDE。得到相应表达式的前缀表达式(波兰式(PN,Polish Notation))。

2)中根(中序)遍历:先中根遍历左子树,访问根结点,中根遍历右子树。对于上面的图1、图2分别为:A+B,C*D-E。得到相应表达式的中缀表达式。

3)后根(后序)遍历:先后根遍历左子树,再后根遍历右子树,最后访问根结点。对于上面的图1、图2分别为:AB-,CD*E-。得到相应表达式的后缀表达式(逆波兰式(RPN,ReversePolish Notation))。

3 数学表达式转换到表达式树(二叉树)

将数学表达式表示为表达式树,关键问题是:最后进行运算的运算符作为二叉树(表达式树)的树根,以该运算符作为界线,在其前面的部分(这里称子表达式1)为二叉树的左子树的表达式,在运算符后面的部分(这里称子表达式2)为右子树的表达式,再分别对子表达式1、子表达式2递归使用以上规则构建左、右子树。

例如:将表达式:((a+b)+c*(d+e)+f)*(g+h)表示成表达树。

其构造过程如下:

首先,先确定二叉的根。根据数学运算顺序知:“g”前面的“*”是最后运算的运算符,因此该“*”作为二叉树的树根如图3。子表达式1为:(a+b)+c*(d+e)+f;子表达式2为:g+h。分别递归构造左、右子树。

其次,构造二叉树的左子树。根据子表达式1:(a+b)+c*(d+e)+f,分析知:f前的“+”为整个左子树的树根,f为左子树的右子树。

再分析其左子树部分:(a+b)+c*(d+e)如图5。

子表达式1:(a+b)+c*(d+e)+f所构成的左子树为图6。

再次,构造二叉树的右子树。由子表达式2:g+h,分析知:右子树的根为:“+”,右子树的左叶子为“g”,而右叶子为:“h”。

从而得如图7。

根据图3、图6和图7。得出表达式:((a+b)+c*(d+e)+f)*(g+h)的表达式树为图8。

对图8的前根遍历得:*+++ab*c+bef+gh.。即表达式:((a+b)+c*(d+e)+f)*(g+h)的前缀表达式(波兰式)为:*+++ab*c+bef+gh.。

对图8的中根遍历得:a+b+c*d+e+f*g+h。即表达式:((a+b)+c*(d+e)+f)*(g+h)的中缀表达式为:a+b+c*d+e+f*g+h。

对图8的后根遍历得:ab+cde+*+f+gh+*。即表达式:((a+b)+c*(d+e)+f)*(g+h)的后缀表达式(逆波兰式)为:ab+cbe+*+f+gh+*。

4 前缀算术表达式(波兰式)到表达式树。

由于前缀算术表达式(波兰式)的运算符(操作符)在两个操作数(操作对象)之前,非叶子结点全为运算符。因此,可按如下规则进行构造二叉树(表达式树):

第一个运算符作为二叉树的树根;紧接着选择其后第一次满足运算符个数比操作数个数少1的部分表达式作为左子树的表达式;剩下的部分表达式为右子树的表达式。再分别对分出的两表达式递归使用以上规划。

例2:写出前缀表达式:-*a^b-+c*defg的表达式树。

解题过程如下:

第一个“-”为树根:如图9。

根据以上规则:左子树部的表达式为:*a^b-+c*def;右子树部分的表达式为:g。

构造左子树:左子树树根为:“*”,“*”的左子树为“a”如图9;右子树表达式为:^b-+c*def。递归构造可得如图10。

将图10、图11组合得左子树为:图12。

再由图9、图12以及右子树“g”得“-*a^b-+c*defg”的表达式树为图13。

对该树后序遍历可得后缀表达式(逆波兰式):abcde*+f-^*g-。

同样对该树中序遍历可得中缀表达式:a*b^c+d*e-f-g。

当然真正的数学表达式为:a*(b^((c+d*e)-f))-g图11

5 由后缀表达式(逆波兰式)到表达式树

由于后缀算术表达式(逆波兰式)的运算符(操作符)在两个操作数(操作对象)之后,非叶子结点全为运算符。因此,可按如下规则进行构造二叉树:

最后一个运算符作为二叉树的树根;紧接着从后往前选择第一次满足运算符个数比操作数个数少1的部分表达式作为右子树部分的表达式;剩下的部分表达式为左子树的表达式。再分别对两表达式递归使用以上规划;对于简单表达式(一个运算符,两个运算对象)从后往前分别是:根、右孩子、左孩子的顺序构造。

例3:用后缀表达式:ab+cde+*+f+gh+*构造表达式树,并求出其前缀和中缀表达式。

解:第一步:根据以上规则:最后一个“*”为树根;如图14。

“gh+”为表达式树的右子树部分的表达式;

“ab+cde+*+f+”为表达式树左子树部分的表达式。

第二步:右子树为:根为:“+”;右孩子为:“h”;

左孩子为:“g”;如图15。

第三步:左子树为:根为:“+”;右子树为:“f”

如图16,其左子树的表达式为:

“ab+cde+*+”;再对“ab+cde+*+”

构造子二叉树。由上规则得:该子二叉树的根为:“+”,右子树部分的表达式为:“cde+*”;左子树部分的表达式为:“ab+”,即如右图17。

综合上面四个图,表达式“ab+cde+*+f+gh+*”的二叉树为如图18所示。

因此,对该二叉树的前序遍历可得波兰式:*+++ab*c+def+gh.。对该二叉树中序遍历可得中缀表达式:a+b+c*d+e+f*g+h.。当然真正的数学表达式为:(a+b+c*(d+e)+f)*(g+h)。

6 小结

运用该文中所介绍的三种表达式与二叉树的转换规则,能顺利地由一种表达式将其转化为二叉树(表达式树),再对该二叉树(表达式树)的遍历,可得到其他的两种表达式,最后将这些表达式用于栈的操作可研制出三种不同的计算器(前缀计算器、中缀计算器(常见的计算器)和后缀计算器);为教师和学生在解答数据结构(或编译原理)中由一种表达式得出其他两种表达式的题目提供了一种构思;进一步完善了数学表达式、栈的应用、二叉树的遍历这三者之间的关系的转换过程。本文中所介绍的规则构思巧妙,但通俗易懂,实用性强。

参考文献

[1]晋良颖.数据结构[M].北京:人民邮电出版社,2002.

[2]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997.

[3]严蔚敏,吴伟民.数据结构题集[M].北京:清华大学出版社,1999.

中序遍历二叉树的教学方法研究 第7篇

由于任何树都可以转换为二叉树进行处理,而二叉树又有许多好的性质和规律,非常适合于计算机处理,因此二叉树也是数据结构研究的重点。但在教学过程中,学生普遍反映这类知识内容抽象、不容易理解,相应的算法难以实现。针对该门课程教学中所存在的这个现状,作为任课教师必然会利用实例图示跟踪、实例演示等教学方法与手段来让学生更好的理解相关知识点。

1 二叉树遍历

在二叉树的一些应用中[5],常常要求在树中查找具有某种特征的节点以及对相应节点进行某种处理,因而便提出了二叉树遍历这一概念,即如何根据某一方法或路径去访问树中的每个节点,并且每个节点又且仅有一次被访问。众所周知,遍历线性结构是很容易的,但对于具有非线性结构特性的二叉树则不尽然,因此必须寻找一定方法或规律来进行二叉树的遍历,使树上的节点能排列在一个线性队列上,从而便于访问所有节点。

根据二叉树的定义可知[1],一棵非空的二叉树由根节点、左子树和右子树三部分组成。因此,只要依次遍历这三部分,就可以遍历整棵二叉树。若以N、L、R分别表示访问根节点、遍历根节点的左子树和遍历根节点的右子树,则二叉树的遍历方式有如下6种:NLR、LNR、LRN、NRL、RNL和RLN。前三种和后三种是对称的,如果限定先左后右,则有NLR(先序遍历)、LNR(中序遍历)和LRN(后序遍历)三种遍历方式。

2 传统二叉树中序遍历方法

2.1 中序遍历定义

若二叉树非空,则先中序遍历左子树,再访问根节点,最后中序遍历右子树。二叉树的遍历是一个递归的过程,左右子树均为遍历,根节点为访问。

2.2 传统中序遍历方法

以图1所示的二叉树为例进行中序遍历,中序遍历的递归过程是:若二叉树为空,则遍历结束。否则:

1)中序遍历根节点的左子树;

2)访问根节点;

3)中序遍历根节点的右子树。

详细的遍历流程如图2所示。

根据访问顺序可以得出该二叉树的中序遍历结果序列为:DBGEACHFI。二叉树作为一种重要的数据结构,诸多教材均对其进行了详细的讲解,但学生对于二叉树中序遍历的方法和算法实现的理解有难度。下面介绍一种简单的方法用于获取二叉树的中序遍历结果序列。

3 简易二叉树中序遍历方法下压法

通过上述的传统的中序遍历的方法可以看出,过程繁琐,而且学生在学习过程中,该遍历的递归调用及返回对他们来说是较难掌握的知识,很多学生进入递归后就不知道该如何层层返回,最终难以得出正确的中序遍历结果。

结合以上情况,在此补述一种简单的二叉树中序遍历的直观方法:下压法。结合传统中序遍历的方法来分析中序遍历的实质,即若二叉树非空,则先中序遍历左子数,再访问根节点,最后中序遍历右子树。我们不难发现,从直观上可以看出处于二叉树最左下方的节点应该是第一个要访问的节点。同时,二叉树是有序的,即其具有严格的左右子树之分的。基于以上特性我们得出简易的二叉树遍历方法下压法。

首先如图3所示将所需遍历的二叉树构造为一棵符合要求的二叉树,即在每一层上,将所有非空左子树完全位于当前根节点的左方,将所有非空右子树完全位于当前根节点的右方,同时构造该二叉树时一定注意,若当前节点有左(右)子树,则在构造时,左(右)子树不能超过当前根节点的上一层根节点的左边界。例如图示中的节点E、G、H三个节点的位置的准确摆放。然后如图4所示在该二叉树下放画一条水平直线。最后将树中各节点一起下压到这条水平线上,此时该水平直线上得到的节点序列即为该二叉树的中序遍历序列。我们以上图1为例,利用下压法进行操作,如图4所示,从而得到该二叉树的中序遍历序列为DBGEACHFI,与传统方法遍历的结果一致。

通过采用下压法,学生对理解二叉树的中序遍历比较直观,避免了学生对遍历的递归调用和返回的理解所存在的困难,以利于学生进行更深入的学习。

4 中序遍历二叉树的算法实现

下面以二叉链表作为存储结构,分别讨论中序遍历二叉树的递归算法和非递归算法。

定义二叉树的链式存储结构:

typedef struct BiTreeNode

{elemtype data;

struct BiTreeNode*lchild,*rchild;

}BiTreeNode,*BiTree;

定义一个空栈:

elemtype data[100];

int top;

}Stack;

Stack S;

4.1 递归算法

根据二叉树的递归定义[1],可得中序遍历二叉树的遍历过程是:若二叉树为空,则遍历结束。否则,

1)中序遍历根节点的左子树;

2)访问根节点;

3)中序遍历根节点的右子树。

根据以上可得其递归算法如下:

InOrder(bt->lchild);

Visit(bt->data);

InOrder(bt->rchild);

}

编译程序对上述程序代码进行编译时[8],将为递归调用建立一个递归工作栈,该栈的每一个元素包含两个域,分别为返回地址域和参数域。对图1中的二叉树进行递归遍历时的栈内变化如表1所示。

可以看出中序遍历该二叉树时,访问节点的顺序为DBGEACHFI,与前述结果一致。因此,在教学过程中结合栈的思想进行讲授能让学生更直观的理解中序遍历二叉树的递归算法。

5.2 非递归算法

在实际的应用中,考虑到递归算法的时间复杂度大,效率低,因此在必要时,可采用非递归算法去解决相应的问题,以节省计算机执行算法的时间和空间。同样可利用栈结构来实现,具体算法如下:

在上述算法中,整个遍历过程没有涉及到递归的应用,而是通过循环语句以及终止条件来进行控制。算法思路清晰,易于理解。在讲授过程中伴以演示图例等将更利于学生直观的理解与掌握。

6 小结

综上所述,在这类知识点的讲授中,不一定拘泥于教材,可根据实际内容和学生情况,有针对性的选择和补充一些更利于学生理解的方法与思路。在实际的教学过程中,教师通过下压法讲授二叉树的中序遍历,直观明了,同时,结合相关演示软件利用栈的思想去理解二叉树的中序遍历,演示过程形象易懂,逻辑清晰,便于学生的学习与理解。

摘要：结合教学中学生难以理解与掌握中序遍历二叉树这一实际情况,本文提出利用下压法进行二叉树的中序遍历,同时,利用栈的思想推导中序遍历二叉树的递归算法和非递归算法,清晰直观,便于学生更好的学习与理解。

关键词：二叉树,中序遍历,教学方法

参考文献

[1]邓文华.数据结构(第2版)[M].北京:清华大学出版社,2007:88-91.

[2]王昆仑,李红.数据结构与算法[M].北京:中国铁道出版社,2007:208-213.

[3]崔俊凯.计算机软件基础[M].北京:机械工业出版社,2007:164-165.

[4]徐孝凯.数据结构实用教程[M].北京:清华大学出版社,1999:175-178.

[5]袁宇丽,胡玲.数据结构中二叉树中序遍历的教学分析[J].内江师范学院学报,2005.21(4):109-111.

[6]张亚萍,陈得宝,侯俊钦.二叉树遍历教学方法研究[J].牡丹江师范学院学报(自然科学版),2010.73(4):69-70.

[7]郭金华,占明.浅议二叉树的遍历[J].科技信息,2010(17):65.

遍历二叉树的递归与非递归算法浅析 第8篇

1 递归算法

递归是指在定义自身的同时, 又出现了对自身的引用。如果一个算法直接或间接调用自己, 则称这个算法是一个递归算法。在遍历二叉树时, 递归就是将二叉树的元素分为根结点、左结点和右结点, 按照左根右、根左右或左右根的顺序依次访问结点并对其做各种处理。为了使初学者更容易理解, 我们可以借助二叉树的图示来讲解。对于三种遍历方法:前序、中序、后序, 我们将二叉树拆分为根 (T) 和左 (L) 、右 (R) 子树, 此时我们发现, 无论是哪种遍历方法, 左子树均在右子树之前被访问, 因此可以将根结点 (T) 与其左、右子树拆分开来, 确定了遍历的顺序, 即确定了访问根结点 (T) 的时间是在左子树之前还是之后。

例如求下图 (1) 所示二叉树的中序遍历序列。首先, 先确定根结点 (A) 及其左右子树 (B) 、 (C) , 按照中序遍历LTR的顺序, 任一结点在以其为根的子树中的访问顺序为左子树、根结点、右子树。而对于以B、C为根结点的两个子树, 还可继续将其拆分为左、右子树, 按左中右的顺序, 遍历左子树直到其只有一个结点或为空为止, 然后遍历右子树, 直到其右子树只有一个结点或为空为止。此步骤可借助图1来讲解。

图 (1) 可拆分为根结点A和图 (2) 、 (3) , 其中图 (2) 为根结点A的左子树, 图 (3) 为A的右子树;接下来, 图 (2) 是以B为根结点的二叉树, 我们可继续将其拆分为根结点B和图 (4) 、 (5) ;同样地, 图 (3) 是以C为根结点的二叉树, 可最终将其拆分为根结点C和图 (6) 、 (7) 。

首先, 按照中序遍历LTR的顺序遍历A的左子树, 即图 (2) 。其中结点B的左子树为D, D没有左子树, 因此直接遍历结点D;然后遍历该左子树的根结点B;接下来遍历B的右子树即图 (5) , 其中G为E的左子树, 且G本身无左子树, 因此直接遍历G, 然后遍历其根结点E。此时二叉树根结点A的左子树即图 (2) 已遍历完毕, 遍历的顺序为DBGE。

接下来应该按照中序遍历的顺序访问根结点A, 然后继续遍历右子树即图 (3) 。

图 (3) 中以C为根结点的二叉树无左子树, 因此首先遍历其根结点C, 然后遍历其右子树即图 (6) ;按照LTR的顺序遍历图 (6) 应依次访问结点HFI, 此处注意图 (7) 为结点I的右子树, I无左子树, 因此遍历I的顺序必然在图 (7) 之前;接下来考虑图 (7) 的遍历顺序, 其中K为J的左子树, 因此应优先遍历, 访问顺序应为KJ。最终图 (3) 的访问序列应为HFIKJ。

由此可得到图 (1) 所示二叉树的中序遍历序列 (LTR) 为DBGEAHFIKJ。同理, 还可根据拆分法得出其先序遍历序列 (TLR) 为ABDEGCFHIJK, 后序遍历序列 (LRT) 为DGEBHKJIFCA。使用此类借助图示的拆分法讲解二叉树的遍历, 可以将遍历二叉树这一比较抽象的问题分解为若干小问题, 便于学生理解;同时, 学生们掌握了这种方法后, 将会更容易理解遍历的递归算法中递归调用和返回的过程。

2 非递归算法

遍历二叉树使用递归算法固然清晰、易理解, 但递归算法解题的运行效率较低, 递归调用函数的次数过多容易造成栈溢出等缺点, 使我们在实际应用中更多地使用非递归算法来设计程序。使用非递归算法遍历二叉树时, 首先设置一个栈, 并将根结点压入其中。对于二叉树中的任一结点均执行扩展和访问两种操作:所有未扩展、未访问的新节点全部入栈, 然后每个结点依次出栈, 出栈后扩展它, 将它的左右子树的根结点 (未扩展、未访问) 及它自身 (已扩展、未访问) 按访问次序压入栈中, 当此结点第二次出栈时就可以直接访问它了。

这个过程如下图所示:设A为一个新结点, 第一次入栈如图 (8) 所示;A第一次出栈后, 扩展它, 将它的左、右子树的根结点分别记为AL、AR, 并为A做上标记 (用*A表示) , 则先序、中序、后序遍历分别将A、AL、AR以不同的顺序压入栈中, 如图 (9) 、 (10) 、 (11) 。

算法可描述如下:

1) 设置栈s, 将二叉树的根结点A压入栈中;

2) 当栈非空时, 弹出栈顶元素A, 并判断该结点是否已被扩展:

(1) 如已扩展则直接访问A;

(2) 否则, 扩展该结点 (记为*A) , 并得到A的左右子树根结点AL和AR, 判断AL、AR是否为空:

ⅰ.为空则不访问;

ⅱ.不空则按照先序、中序、后序遍历的顺序分别将*A、AL、AR入栈, 得到结果如图 (9) 、 (10) 、 (11) 。

3) 继续执行步骤2) 。

由图可看出, 先序遍历二叉树的过程中, 在根结点彻底出栈 (被扩展、被访问) 之前, 其左子树是不会出栈的, 即不会被访问;同理, 中序、后序遍历也能够保证完全按照规定的顺序依次访问结点。

3 总结

现实世界中多种问题都可归纳成为树和森林的模型, 而树和森林又可以用二叉链表作媒介同二叉树进行相互转换, 因此, 学好二叉树对学习程序设计、利用计算机解决实际问题特别重要;二叉树的各种复杂运算大都是建立在其三种遍历之上的, 因此, 掌握好二叉树的遍历算法是极有必要的。本文分别选取了两种较简单的递归和非递归算法来分析二叉树的三种遍历过程, 使初学者更易于理解二叉树的遍历算法。

摘要：二叉树是数据结构中最常见的一种存储形式, 而遍历二叉树又是二叉树中最重要的操作。该文分别以递归和非递归两种不同的算法来分析遍历二叉树的过程, 旨在用简单明了的方法来实现二叉树的遍历, 且先序、中序、后序三种遍历方式都可通过这两种算法实现。

关键词：二叉树,遍历,递归,非递归

参考文献

[1]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997:121-131.

[2]胡元义, 邓亚玲, 罗作民, 等.数据结构 (C语言) 实践教程[M].西安:西安电子科技大学出版社, 2002:77-85.

[3]李春葆.数据结构习题与解析[M].2版.北京:清华大学出版社, 2004:311.