二叉树的创建与访问算法设计

二叉树的创建与访问算法设计（精选6篇）

二叉树的创建与访问算法设计 第1篇

数据结构课程设计报告

题目名称： 二叉树的应用问题 专业班级： 计算机科学与技术

学生姓名：

学生学号：

指导教师：

目录

一、题目要求..............................................二、需求分析..............................................三、概要设计..............................................四、详细设计..............................................五、调试分析.............................................六、心得体会.............................................一、题目要求

实现二叉树，求解若干二叉树应用问题

 实现二叉链表表示的二叉树，包括下列运算：

 建立一棵二叉树；

 按先序、中序和后序遍历二叉树；  按层次遍历；

 求一棵二叉树的高度；

 交换一棵二叉树的左右子树；

 设计一个菜单驱动程序，测试上述算法

二、需求分析

建立一棵二叉树：

int CreateBiTree(BiTree &T)按先序遍历二叉树：

void PreOrder(BiTree &T)按中序遍历二叉树：

void InOrder(BiTree &T)按后序遍历二叉树：

void PostOrder(BiTree &T)按层次遍历：

void LevelOrder(BiTree &T)求一棵二叉树的高度：

int Depth(BiTree &T)交换一棵二叉树的左右子树：int PreOrderTraverse(BiTree T)菜单驱动程序：

void menu()

三、概要设计

定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树。

先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。

中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；

（3）中序遍历右子树。

后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。

层次遍历二叉树的操作选用队列的存储结构。先建立一个长度为1的队列，利用while循环，将根结点放入队首，再将队列长度加一。然后依次遍历左子树和右子树，每遍历一次，2、先序遍历二叉树：

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

3、中序遍历二叉树：

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

4、后序遍历二叉树：

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

5、按层次遍历：

void LevelOrder(BiTree &T){ BiTree queue[100];int front,rear;if(T==NULL)return;front=-1;rear=0;queue[rear]=T;while(front!=rear){ front++;cout<data<<“ ”;if(queue[front]->left_child!=NULL){ rear++;queue[rear]=queue[front]->left_child;

cin>>a;if(a>=0||a<=7){ switch(a){ case 0:

{

cout<<“建立后的二叉树为：n”;

Output(T);

cout<

}

system(“pause”);

break;case 1:

cout<<“该树的树深为: ”<

system(“pause”);

break;case 2:

{

cout<<“该树以先序遍历输出为：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;case 3:

{

cout<<“该树以中序遍历输出为:n”;

InOrder(T);

cout<

}

system(“pause”);

break;case 4:

{

cout<<“该树以后序遍历输出为：n”;

PostOrder(T);

cout<

}

system(“pause”);

break;case 5:

{

cout<<“该树的层次遍历：n”;

LevelOrder(T);

cout<

（二）详细程序代码：{ if(!T){

cout<<“空树!n”;

return;} cout<data<<“ ”;if(T->left_child)Output(T->left_child);if(T->right_child)Output(T->right_child);}

int Depth(BiTree &T){ int i,j;if(!T)return 0;i=Depth(T->left_child);j=Depth(T->right_child);return(i>j?i:j)+1;}

void PreOrder(BiTree &T){ if(!T)

return;cout<data<<“ ”;PreOrder(T->left_child);PreOrder(T->right_child);}

void InOrder(BiTree &T){ if(!T)return;InOrder(T->left_child);cout<data<<“ ”;InOrder(T->right_child);}

void PostOrder(BiTree &T){ if(!T)return;PostOrder(T->left_child);PostOrder(T->right_child);cout<data<<“ ”;}

void LevelOrder(BiTree &T)

cout<<“<<

1.二叉树树深

>>”<

cout<<“<<

2.二叉树的先序遍历

>>”<

cout<<“<<

3.二叉树的中序遍历

>>”<

cout<<“<<

4.二叉树的后序遍历

>>”<

cout<<“<<

5.二叉树的层次遍历

>>”<

cout<<“<<

6.左右孩子交换

>>”<

cout<<“<<

7.退出

>>”<

cout<<“*******************************************************************”<

void main(){

int br,a;BiTree T;br=CreateBiTree(T);

while(1){

menu();

cout<<“请输入选择的命令-->”;

cin>>a;

if(a>=0||a<=7)

{

switch(a)

{

case 0:

{

cout<<“建立后的二叉树为：n”;

Output(T);

cout<

}

system(“pause”);

break;

case 1:

cout<<“该树的树深为: ”<

system(“pause”);

break;

case 2:

{

cout<<“该树以先序遍历输出为：n”;

PreOrder(T);

cout<

}

system(“pause”);

break;

case 3:

{

cout<<“该树以中序遍历输出为:n”;

（一）先序输入二叉树：

（二）建立一棵二叉树：

1后序遍历：

（四）按层次遍历：

3中序遍历交换后的二叉树：

六、心得体会

这次数据结构课程设计我选择的题目是二叉树的应用操作，题目要求中最难的部分是二叉树的层次遍历。在实现这个要求的时候我想了很久，最后通过在CSDN上找到了解决思路，就是用队列的方式。虽然是二叉树的题目，但是和其他知识点都有很多内在的联系。经过这次的实验，我不仅在二叉树的应用操作层面上更加熟悉，对二叉树的理解更加深刻，更重要的是我认识到知识要融会贯通才是它的价值所在。我的C语言基础不是很扎实，所以在写代码的时候也遇到很大的困难。像很基础的“j?i:j”也是通过翻阅以前的书籍才找到答案。还有在编程过程中的习惯也不是很好，函数及变量的命名等细节问题，如果不加以注意的话，会对后面的编译调试造成很多不必要的麻烦。我应该在以后的学习中加强实践，这样才能更扎实地掌握所学知识点，更有效地将书本上的知识变成解决实际问题的经验。

二叉树的创建与访问算法设计 第2篇

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

平衡排序二叉树的C＋＋算法实现 第3篇

二叉树的创建与访问算法设计 第4篇

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.

二叉树的创建与访问算法设计 第5篇

树是一种重要的存储结构,在计算机算法研究和设计中起着非常重要的作用,根据树和二叉树的性质,任何一棵树都可以转换成对应唯一的一棵二叉树,且二叉树的操作相对其它多叉树来讲也是最简单的,具有一定的代表性。所谓二叉树的遍历,指的是按照一定的次序访问二叉树中的所有结点,并且每个结点仅被访问一次的过程。

假设一棵简化的二叉树如图1所示。

根据遍历的特点,对这棵二叉树进行遍历有以下六种,DLR,DRL,LDR,LRD,RDL,RLD,在数据结构中,有约定对左右子树的访问按照先左后右的方式进行,在这个约定之下,遍历方式变成DLR,LDR,LRD三种,这三种遍历方式根据根节点位置的不同,分别称为先序、中序和后序。根据以上三种遍历方式,很容易得到一棵二叉树对应的遍历序列,反过来,根据二叉树遍历的特点,可以由其中的两种遍历结果得到对应的二叉树,而其中一种必须是中序。因为只有中序能把左子树和右子树分开。

根据先序和中序确定一棵二叉树

先序遍历一棵二叉树的方法是“首先访问根节点,然后依次访问左子树和右子树”,因此在一个遍历序列中,第一个结点即整棵二叉树的根节点,如有先序序列“ABDGCEFH”和中序序列“DGBAECHF”可知,整棵二叉树的根节点为“A”,然后在中序序列中找到“A”结点,根据A结点可将该中序序列分成左右两个部分,左边“DGB”和右边“ECHF”,左边即左子树,右边即右子树,此时二叉树示意图如(a)所示,再针对右子树上结点“ECHF”,在先序中找到这四个结点的顺序为“CEFH”,用同样的方法可知右子树根结点为“C”,然后在中序序列中由“C”结点,分出左子树结点“E”和右子树结点“HF”,示意图如(b)所示。

在算法实现过程中,用C语言描述的以二叉链表作为存储结构的结构体定义如下:

假设在完成本算法之前,已经将先序序列和中序序列分别存储在pre[]和in[]数组中,n表示二叉树的结点个数,则可用如下算法实现由先序和中序序列对应的一棵二叉树:

以上算法是一个递归实现的过程,其基本思想是:首先根据先序序列的第一个结点找到根结点,然后中序序列中找到该跟结点,将左右子树区分出来,最后两个语句表示用同样的方法处理左子树和右子树。

根据后序和中序确定一棵二叉树

根据以上先序和中序序列确定的二叉树,针对同样这棵二叉树,其后序序列为“GDBEHFCA”,中序序列仍然为“DGBAECHF”,由后序序列的遍历规则“先访问左子树,再访问右子树,最后访问根结点”的规则,其根结点为后序遍历中的“A”结点,再在中序遍历序列中找到“A”结点,将其左边部分“DGB”称为左子树,右边部分“ECHF”称为右子树,示意图如(a)所示。针对其右子树上结点序列“ECHF”,其对应的后序遍历序列为“EHFC”,可知,其右子树上根结点为最后一个“C”,然后在中序序列中找出“C”结点的左孩子序列“E”和右孩子序列“HF”,示意图如(b)所示。

用同样的方法给出根据后序和中序序列确定二叉树的算法(假设中序序列存储在in[]和后序序列post[]中,left1和right1表示中序序列的第一个和最后一个结点的下标,left2和right2表示后序序列的第一个和最后一个结点的下标):

结束语

二叉树的创建与访问算法设计 第6篇

二叉树是一种重要的树形结构,其结构规整。许多实际问题抽象出来的数据结构往往是二叉树的形式,而且其存储结构及运算都较为简练,因此,二叉树在数据结构课程中显得特别重要,这里我们先了解一下二叉树。

二叉树是由结点的有限集合构成,这个有限集合或者为空集,或者是由一个根节点及两棵互不相交的分别称之为这个根的左子树和右子树的二叉树组成。从定义来看,二叉树定义是一个递归定义,但由于学生对递归算法的理解存在一些误区,同时递归算法效率较低,并且在实际应用中有些问题也不允许调用递归算法,故有关二叉树的试题通常要求采用非递归算法,这就使得掌握二叉树的生成及遍历的非递归算法成为必要。

二、二叉树的生成

建立一个二叉树是指在内存中建立二叉树的存储结构,这里讨论建立一个二叉链表的方式生成一个二叉树。要建立一个二叉链表,需按照完全二叉树的层次顺序,依次输入结点信息建立二叉链表。对于一般的二叉树,必须添加一些虚结点,使其成为完全二叉树。我用@表示虚结点,#表示输入结束标志。同时设置一个队列,队列是一个指针类型的数组,保存已输入的结点的地址。根据对为指针奇偶数的判断,来决定把字符放到左孩子结点中还是右孩子结点中,这样就能生成想要的二叉树。

三、二叉树的先序、中序、后序遍历

上面虽然已经生成二叉树,但实际上用户生成的二叉树是抽象,用户并不太确信已经生成的二叉树是否是自己想要的,于是,可以编制输出程序进一步验证这个已经存在的二叉树的正确性。

二叉树的遍历就是对二叉树的每一个结点访问一次且仅访问一次。我们通过二叉树的序遍历的非递归算法来验证其正确性。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。

1、先序遍历

使用一个栈,首先将根结点入栈,开始循环;从战中退出当前结点,先访问它,然后将其右结点入栈,再将其左结点入栈,如此直到栈空为止。

2、后序遍历

先将根结点的所有左结点并入栈,出栈一个结点,将该结点的右结点入栈,再将该结点的左结点入栈,当一个结点的左右子树均访问后再访问该结点,如此,直到栈空为止。

3、中序遍历

先将根结点的所有左结点并入栈,出栈一个结点,访问该结点,将该结点的右结点入栈,再将该结点的左结点入栈,当一个结点的左子树均访问后再访问该结点,最后访问右结点。如此,直到栈空为止。

四、总结

二叉树在计算机科学中有着重要的作用,现实世界中有好多问题都是用树这种数据结构描述的,而二叉树在计算机中操作和实现都非常方便,因此在二叉树的建立及其遍历是非常重要的。同时二叉树的三种遍历算法是二叉树运算的基础,大多数二叉树上的复杂运算都是建立在这三种遍历之上的。因此,要深刻理解这三种遍历算法是十分必要的。

参考文献

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

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

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