二叉树遍历实验（通用6篇）
二叉树遍历实验 篇1
一、二叉链表的声明.BinaryNode
public T data;
//数据域，存储数据元素
public BinaryNode
//链域，分别指向左、右孩子结点
//构造结点，参数分别指定元素和左、右孩子结点
publicBinaryNode(T data, BinaryNode
{ this.data = data;this.left = left;this.right = right;
}
public BinaryNode(T data)
//构造指定值的叶子结点
{ this(data, null, null);
} publicBinaryNode()
{ this(null, null, null);
}
//可声明以下方法 public String toString()
{ returnthis.data.toString();
}
public boolean equals(Object obj)
//比较两个结点值是否相等，覆盖Object
//类的equals(obj)方法
{ returnobj==this || objinstanceofBinaryNode&&this.data.equals(((BinaryNode
}
public booleanisLeaf()
//判断是否叶子结点
{ returnthis.left==null &&this.right==null;
} } 二、二叉树中的遍历方法的声明.BinaryTree
public BinaryNode
//根结点，结点结构为二叉链表
public BinaryTree()
//构造空二叉树
{ this.root=null;
}
public booleanisEmpty()
//判断二叉树是否空
{ returnthis.root==null;
}
//二叉树的先根、中根和后根次序遍历算法
public void preOrder()
//先根次序遍历二叉树
{ System.out.print(“先根次序遍历二叉树：
”);preOrder(root);//调用先根次序遍历二叉树的递归方法 System.out.println();
}
public void preOrder(BinaryNode
//先根次序遍历以p结点为根的子二叉
//递归方法
{ if(p!=null)
//若二叉树不空
{ System.out.print(p.data.toString()+“ ”);//访问当前结点
preOrder(p.left);
//按先根次序遍历当前结点的左子树，//递归调用 preOrder(p.right);
//按先根次序遍历当前结点的右子树
//递归调用
}
}
public String toString()
//返回先根次序遍历二叉树所有结点的描述字符串
{ returntoString(root);
}
private String toString(BinaryNode
//返回先根次序遍历以p为根的子树描述字
//符串，递归算法
{ if(p==null)return “";
return p.data.toString()+” “ + toString(p.left)+ toString(p.right);//递归调用
}
public void inOrder()
//中根次序遍历二叉树
{ System.out.print(”中根次序遍历二叉树：
“);inOrder(root);System.out.println();
}
public void inOrder(BinaryNode
//中根次序遍历以p结点为根的子二叉
//递归方法
{ if(p!=null)
{ inOrder(p.left);
//中根次序遍历左子树，递归调用 System.out.print(p.data.toString()+” “);inOrder(p.right);
//中根次序遍历右子树，递归调用
}
}
public void postOrder()
//后根次序遍历二叉树
{ System.out.print(”后根次序遍历二叉树：
“);postOrder(root);System.out.println();
}
public void postOrder(BinaryNode
//后根次序遍历以p结点为根的子二叉树，//递归方法
{ if(p!=null)
{ postOrder(p.left);postOrder(p.right);System.out.print(p.data.toString()+” “);
}
}
public BinaryTree(T[] prelist, T[] inlist)
//以先根和中根序列构造二叉树
{ this.root = create(prelist, inlist, 0, 0, prelist.length);
} //以先根和中根序列创建一棵子树，子树根结点值是prelist[preStart]，n指定子序列长度.//返回所创建子树的根结点
privateBinaryNode
{ System.out.print(”prelist:“);print(prelist, preStart, n);System.out.print(”，inlist:“);print(inlist, inStart, n);System.out.println();
if(n<=0)return null;
T elem=prelist[preStart];
//根结点值 BinaryNode
//创建叶子结点 inti=0;while(i //在中根序列中查找根值所在位置 i++;p.left = create(prelist, inlist, preStart+1, inStart, i); //创建左子树 p.right = create(prelist, inlist, preStart+i+1, inStart+i+1, n-1-i);//创建右子树 return p; } private void print(T[] table, int start, int n) { for(inti=0;i } public BinaryTree(T[] prelist) //以标明空子树的先根序列构造二叉树 { this.root = create(prelist); } //以标明空子树的先根序列构造一棵子二叉树，子树的根值是prelist[i]，返回所创建子树的根结点 privateinti=0;privateBinaryNode { BinaryNode { T elem=prelist[i];i++;if(elem!=null)//不能elem!=”^“，因为T不一定是String { p = new BinaryNode //创建叶子结点 p.left = create(prelist); //创建p的左子树 p.right = create(prelist); //创建p的右子树 } } return p; } } 三、运行程序 .BinaryTree_make //运用二叉链表及先根和中根遍历确立并构造二叉树 public class BinaryTree_make { public static BinaryTree //构造给定的一棵二叉树 { BinaryTree BinaryNode } public static void main(String args[]) { BinaryTree //先根次序遍历二叉树 bitree.inOrder();//中根遍历 bitree.postOrder(); //后根遍历 String[] prelist = {”A“,”B“,”D“,”G“,”C“,”E“,”F“,”H“};//采用先根中根两种遍历 String[] inlist = {”D“,”G“,”B“,”A“,”E“,”C“,”H“,”F"}; //确定一颗二叉树 BinaryTree bitree1.preOrder();// 先根遍历 bitree1.inOrder();//中根遍历 bitree1.postOrder(); } } //后根遍历 四、运行结果 五、实验内容 1.根据图示的二叉树，运用二叉链表及先中根遍历构造二叉树，并在控制台上显示出二叉树：先中后根遍历 六、附加实验内容 在上述实验中，只通二叉链表及先根和中根遍历确立构造二叉树。没有给出中根和后根遍历二叉树的方法。现要求同学们写出中根和后根遍历确立二叉树的方法（只写方法）。 七、实验报告要求 1.运行结果需要截图，写出补充方法体的内容，附加实验只给方法即可。 2.心得体会不可为空（可写对此次实验的看法，亦可写自己近来学习数据结构的感受等等，内容不限） 关键词：二叉树,遍历二叉树,搜索路径 遍历是二叉树最重要的运算之一,是对二叉树进行其他运算的基础。 1 遍历方案 遍历(Traverse)是指沿着某条搜索路线,依次对树中每个节点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。 从二叉树的递归定义可知,一个非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作: 1)访问根结点(D); 2)遍历该结点的左子树(L); 3)遍历该结点的右子树(R) 以上三种操作有六种执行次序:DLR、LDR、LRD、DRL、RDL、RLD。 2 遍历的命名 根据访问根结点操作发生位置命名: DLR:先序遍历(Preorder Traverse,亦称前序遍历)访问根结点的操作发生在其左右子树之前。 LDR:中序遍历(Inorder Traverse)访问根结点的操作发生在其遍历左右子树之中(间)。 LRD:后序遍历(Postorder Traverse)访问根结点的操作发生在遍历其左右子树之后。 注意:由于访问是根据根结点D操作位置命名,所以DLR、LDR、LRD分别又称为先根遍历、中根遍历、后根遍历。 3 遍历方法 第一,如何通过给定的二叉树,写出三种遍历序列; 第二,如何通过给定的其中两中遍历序列,求出另一种序列以及画出对应的二叉树图。 下面通过具体的例题给出具体的解答: 如:假设一棵二叉树的先序序列为124536,中序序列为425136。请写出该二叉树的后序序列及其画出对应二叉树 解答过程如下: 1)由先序序列124536,可以得出根结点为1; 2)结合1),由中序序列425136,可以得出425为左子树(中序遍历),36为右子树(中序遍历); 3)结合2),根据先序序列124536,可以得出左子树245采取先序遍历根结点为2(即根结点1的左子树为2);右子树36采取先序遍历根结点为3(即根结点1的右子树为3);再由2),根据425采取中序遍历得出2的左子树为4,右子树为5;再由2,根据36采取中序遍历得出3的右子树为6 所以可以得出:1为根结点,2、3为1的左右子树,4、5为2的左右子树,6为3的右子树; 对应的二叉树如下: 4)根据二叉树图,结合后序遍历的规则LR1,L为根据L也是采取后序遍历为452,R也是采取后序遍历63,代入LR1,得出后序序列为452631。 同理,根据给出的二叉树,采取相同的方法,可以得出先序序列为124536,中序序列为425136。 参考文献 [1]安训国.数据结构[M].4版.大连:大连理工大学出版社,2009:96-101. 关键词：二叉树;二叉树的遍历;二叉排序树;还原 中图分类号：G42文献标识码：A文章编号：16723198（2007）11022101 二叉树是最为常用的数据结构，它的实际应用非常广泛。二叉树的遍历方式有三种，前序遍历、中序遍历、后序遍历。先序遍历的顺序为：NLR，即先根结点，然后左子树、右子树；中序遍历顺序为：LNR先左子树，然后根结点、右子树；后序遍历顺序为：LRN先左子树、然后右子树、根结点。由前序和中序遍历、由中序和后序遍历序列可以唯一确定一棵二叉树，而由前序和后序遍历序列不能唯一确定一棵二叉树。 二叉排序树对二叉树作了进一步的限定：根结点的权值大于（或小于）左子树中所有结点的权值；根结点的权值小于（或大于）其右子树中所有结点的权值。 那么如何根据三种遍历序列之间的关系及二叉排序树来快速还原一棵二叉树？下面以二叉树的前序和中序遍历序列为基础，利用二叉排序树的性质，给出快速还原二叉树的方法。 1由给定前序和中序序列或中序和后序序列还原二叉树的方法 例：前序序列：ABDECFGH中序序列：DEBACGFH（后序序列：EDBGHFCA） （1）给中序序列中的每个结点从小到大、从左到右赋以权值，如下： D（1）E（2）B（3）A（4）C（5）G（6）F（7）H（8） （2）还原时读入的序列为前序序列，从左到右依次读入序列中的各个结点值和相应的权值； （3）由读入的序列，根据第1）步中给定的权值按照二叉排序树的构造规则构造二叉排序树。第一个读入的结点为根结点，其他结点分别为左右子树中的结点。设根结点为TT，权值为NN，当前读入结点为SS，权值为MM，若MM （4）将SS插入到TT的左子树或右子树的过程中，仍然遵循3）中的规则，直至左子树或右子树为空时止。 （5）读入序列结束时，二叉树还原成功。还原后的二叉树如下图。 （6）对于由中序序列和后序序列还原二叉树是，读入的序列为后序序列，从右向左读入，构造规则同上。还原结果与上述结果完全一致。 2还原方法的确定依据 二叉树遍历过程中，在中序序列中，根结点的左子树中的所有结点都在根结点的左侧，根结点的右子树中的所有结点都在根结点的右侧，这个特点恰好与二叉排序树具有相同的性质；在读入序列时，前序序列则从左向右读，这恰好与遍历二叉树的顺序相同；后序序列从右向左读，则按照根结点、右子树、左子树的顺序还原。 （1）设二叉树共有N个结点（N为大于1的正整数），我们按照还原方法给中序序列中的这N个结点分别赋予权值1,2…N，设根结点的权值为M（1 （2）由二叉树的遍历规则可知，权值为1,2…M-1的结点为根结点的左子树中的结点，而权值为M+1,…N的结点为根结点的右子树中的结点。 （3）将这N个结点划分成3个子集AA＝（1,2…M-1）BB＝（M）CC＝（M+1,…N），由于前序序列第一个读入的结点必定为二叉根的根结点，所以BB为根结点，AA集为左子树，CC集为右子树。 （4）同理不断读入前序序列中的结点，依次递归还原BB对应的左子树和CC对应的右子树，最后将三棵子树合并成以BB为根结点、AA的根结点为BB的左子树、CC的根结点为BB的右子树的一棵二叉排序树。 （5）同理可以得出，由中序序列和后序序还原二叉树的规则也成立。 （6）在还原过程中，读入序列的顺序也遵循也先根结点，后子树的规律。 3总结 在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。 参考文献 一、导入 树是一类重要的非线性数据结构，是以分支关系定义的层次结构。在日常生活同学们经常见到树。树有一个树根。有许多树枝，在树枝上长有很多树叶。就象我们今天要讲的树，是一种层次结构。 二、新授(一)树 1． 树的定义 树（tree）是由 n(n≥0)个结点组成的有限集合。它是树型结构的简称，是一种重要的非线性数据结构，应用广泛。如：磁盘上的文件目录结构、家族成员关系、单位的组织机构、书的内容组织、算术表达式等。任何一棵非空树是一个二元组： Tree =（root，F）其中：root被称为根结点，F被称为子树森林 2． 基本术语 森 林：是m（m≥0）棵互不相交的树的集合 有 向 树：有确定的根，树根和子树根之间为有向关系（自上到下，自左到右）有 序 树：树中结点的各子树从左到右是有次序的，不能互换 无 序 树：树中结点的各子树从左到右是没有次序的 子 女：结点的子树的根是该结点的孩子 双 亲：孩子结点的根结点 兄 弟：具有同一双亲的结点 堂 兄 弟：双亲在同一层的结点 祖 先：从根到该结点所经历分支上的所有结点 子 孙：以某结点为根的子树中的任一结点 学生活动：请同学门总结树形与线形的异同 (二)二叉树 1.二叉树的定义 二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 2．二叉树的五种基本形态 二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。 3．二叉树不是树的特例（1）二叉树与无序树不同 二叉树中，每个结点最多只能有两棵子树，并且有左右之分。 二叉树并非是树的特殊情形，它们是两种不同的数据结构。 （2）二叉树与度数为2的有序树不同 在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 4、满二叉树和完全二叉树是二叉树的两种特殊情形。 a、满二叉树 一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点： （1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 （2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 b、完全二叉树(Complete BinaryTree)若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。 特点： （1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 5、二叉树的性质 性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。 性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。 性质4 具有n个结点的完全二叉树的深度为 遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。 二叉树遍历方法可分为两大类，一类是“宽度优先”法，即从根结点开始，由上到下，从左往右一层一层的遍历;另一类是“深度优先法”，即一棵子树一棵子树的遍历。 从二叉树结构的整体看，二叉树可以分为根结点，左子树和右子树三部分，只要遍历了这三部分，就算遍历了二叉树。设D表示根结点，L表示左子树，R表示右子树，则DLR的组合共有6种，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左后右，则只有DLR，LDR，LRD三种，分别称为先(前)序法(先根次序法)，中序法(中根次序法，对称法)，后序法(后根次序法)。三种遍历的递归算法如下： 1.先序法(DLR) 若二叉树为空，则空操作，否则：访问根结点，先序遍历左子树，先序遍历右子树。 2.中序法(LDR) 若二叉树为空，则空操作，否则：中序遍历左子树，访问根结点，中序遍历右子树. 3.后序法(LRD) 若二叉树为空，则空操作，否则：后序遍历左子树，后序遍历右子树，访问根结点。 ▶完全二叉树中有关结点个数计算 完全二叉树的定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。 完全二叉树的叶子数为(n + 1) / 2取下整。 ▶森林与二叉树之间的转换以及转换过程中结点之间的关系 将一棵树转换为二叉树的方法是： 1.树中所有相邻兄弟之间加一条连线。 2.对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。 3.以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。 森林转换为二叉树的方法如下： 1.将森林中的每棵树转换成相应的二叉树。 2.第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。 树和森林都可以转换为二叉树，二者的不同是:树转换成的二叉树,其根结点必然无右孩子，而森林转换后的二叉树，其根结点有右孩子。将一棵二叉树还原为树或森林，具体方法如下： 1.若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、……都与该结点的双亲结点用线连起来。 2.删掉原二叉树中所有双亲结点与右孩子结点的连线。 3.整理由1、2两步所得到的树或森林，使之结构层次分明。 OpenMP是一个业界的标准，是共享内存的编程模型，可以在C/C++中使用OpenMP[2]。它很容易的引入多线程。OpenMP的重要性在于，它能够为编写多线程程序提供一种简单的方法，而无需程序员进行复杂的线程创建、同步、负载平衡和销毁工作。大多数要进行计算的程序的运行时间都是花费在循环上，因此循环并行化在OpenMP应用程序中是一个相对独立且非常重要的组成部分。本文中通过实现非递归后序遍历二叉树的循环并行化，与并行之前的串行程序进行比较，分别求出串并行时间，并得出加速比。 1 串行算法设计 1.1 后序遍历二叉树的过程 从根节点开始，沿左子树一直遍历到没有左孩子的节点为止，并将所经节点的地址第一次进栈;当遍历到没有左孩子的节点时，此节点的左子树已访问完毕;从栈顶退出该节点，判断该节点是否为第一次进栈，假如是，再将所经节点的地址第二次进栈，并沿该节点的右子树一直走到没有右孩子的节点为止，如果不是，则访问该节点;此时，该节点的左、右子树都已全部遍历完，将指针 1.2 构造非递归后序遍历函数 2 并行算法设计 2.1 并行原理 一些可同时执行的多个进程的集合，这些进程相互作用并且协调动解决某问题。使用消息传递并行程序设计是用户必须通过显式地发送和接收消息来实现处理机间的数据交换。在这种并行编程中，每个并行进程均有自己独立的地址空间，相互之间访问不可以直接进行，必须通过显示地消息传递来实现。 2.2 并行算法[3] 3 运行结果 加速比=串行最优时间/并行时间 运行结果如下所示： 一般结点数比较大的时候使用并行算法运行时间都小于使用串行算法运行时间，但是这不是绝对的，运行时发现结点数等于2500时，并行时间大于串行时间，这种结果也许是因为软硬件原因导致。但是从全局来看改变结点数加速比增长的规律不是很大，只在零点几之间小幅度的增加，加速比一直保持在1～2之间(2表示2核计算机)。多核下的并行程序在一般情况下应该比单CPU的串行程序运行节省时间，这就增加了CPU的利用率，多线程之间的并发提高了内存利用率与系统存储量。 4 结束语 根据运行结果可推出多核环境下并行运行程序通常都比串行运行程序快。所以利用并行化执行程序可明显缩短程序运行所需要的时间，同时也增加了的资源利用率。所以在程序中添加并行化是可以提高程序的运行效率的。 摘要：在串行程序中添加了循环并行化指导语句,实现了程序的并行化。这样有利于提高二叉树后序非递归遍历的运行速度,达到让程序运行花费更短时间的目的。该文提出了一种有利于提高CPU的利用率、加快程序运行速度的非递归后序遍历二叉树的算法。 关键词：并行程序,串行程序,非递归后序遍历二叉树算法,多核程序设计,加速比 参考文献 [1]严蔚敏,吴伟民.数据结构(C语言)[M].北京:清华大学出版社,1997. [2]奎因著,陈文光.MPI与OpenMP并行程序设计[M].北京:清华大学出版社,2004. 【二叉树遍历实验】推荐阅读： 图的遍历实验报告07-18 三种实现方法实现数据表中遍历寻找子节点06-25 实验虚拟机实验07-31 虚拟实验替代动物实验07-23 实验能力与实验素养09-03 移位运算实验实验报告05-21 数点实验报告实验三06-10 实验室实验报告08-11 化学实验室实验守则07-02二叉树遍历实验 篇2
二叉树的遍历研究及还原研究 篇3
树和二叉树教案1 篇4
计算机数据结构核心考点之二叉树 篇5
二叉树遍历实验 篇6