二叉树的遍历学习心得（精选4篇）
篇1：二叉树的遍历学习心得
实验报告
课程名：数据结构（C语言版）实验名：二叉树的遍历 姓名：
班级：
学号：
时间：2014.11.03
一 实验目的与要求
1.掌握二叉树的存储方法 2.掌握二叉树的三种遍历方法
3.实现二叉树的三种遍历方法中的一种 二 实验内容
• 接受用户输入一株二叉树
• 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序 三 实验结果与分析
//*********************************************************** //头文件
#include
#define OK 1 #define ERROR 0 #define OVERFLOW 0
//***********************************************************
typedef struct BiTNode { //二叉树二叉链表存储结构 char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值，空格表示空树 //构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==)T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} }
//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构，后序遍历二叉树的递归算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} }
//*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树
printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);}
图1:二叉树的遍历运行结果
篇2：二叉树的遍历学习心得
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.运行结果需要截图，写出补充方法体的内容，附加实验只给方法即可。 树形结构在许多方面有应用,可表示层次关系、从属关系和并列关系等。在计算机科学领域中,树形结构是一种非常重要的非线形结构。计算机应用中常出现的嵌套数据,在各种算法问题中,如文件管理、数据库、编译等系统中的算法,都可用树形结构得来表示。二叉树是树形结构的另一种重要类型,许多算法问题用二叉树形式来解决简单灵活,而且树形结构都可以转换成一棵与之对应的二叉树。因此,二叉树是树形结构的关键组成部分,有关二叉树的各种算法也是学习数据结构课程的的重点和难点。数据结构及其算法的教学难点在于它们的抽象性和动态性,我们在学习二叉树的算法时就遇到了难题:首先基于结构化的程序设计思想的算法比较烦琐,同时由于传统的程序设计将数据与操作分开,是孤立地看待问题,对于记录每个顶点的状态,维持各顶点之间的联系比较麻烦。用C或Pascal描述数据结构,不能很好地实现抽象数据类型的思想,只有用C++或Java的类才能很自然地实现抽象数据类型的思想,这为改良教学内容,促进软件复用和设计良好的软件架构,打下了坚实的基础[1];其次学生上机验证二叉树的建立算法时无从知道建立的二叉树是否与所想建立的一致;另外先序、中序和后序三种遍历的动态过程也无法形象直观的得以展现。因此我们若采用面向对象方法描述二叉树,并为学生提供一些接口,能在屏幕上将学生建立的二叉树可视化的显示,并将先序、中序和后序三种遍历算法实现动态同步可视化,这将对学生的学习提供莫大的帮助,同时也可激发学生更浓厚的学习兴趣。 1 二叉树的面向对象描述 1.1 顶点类的设计 顶点类的基本成员有left、right和data,left表示结点的左子树,right表示结点的右子树,data表示结点的数据域。为将复杂的数据结构以直观易懂的形式展现在屏幕上,应设计可视数据结构。可视数据结构就是在顶点类的基本属性和操作的基础上,增加可视属性(如顶点大小,颜色,坐标值等),并提供可视化接口供程序调用[2]。因此为了实现二叉树的可视化增加三个成员id、x和y,id表示结点的完全化编号,x,y表示结点的可视化坐标。 1.2 二叉树的二叉链表实现——二叉链表类的设计 其中root成员表示二叉树的根;cursor成员表示当前结点,称光标; 方法LinkedBinaryTree()构造一棵空二叉树 方法LinkedBinaryTree(String s)构造一棵二叉树,字符串s是二叉树的广义表形式,如a(b(c,d(e,f)),i(j,k(x,y))) 方法LinkedBinaryTree(String s)构造一棵二叉树,字符串s是二叉树的先序遍历序列,如abc**de*g**f***,其中“*”表示子树为空 方法drawNode()在绘图区域绘制二叉树中的结点 方法drawEdge()在绘图区域绘制二叉树的边 方法show()在指定的窗体上可视显示二叉树, 2 二叉树的可视化实现 2.1 完全二叉树的可视化实现 由于屏幕的大小是确定的,所以要将二叉树绘制在这片弹丸之地并非易事。对于教学而言达到教学的目的就可以了,所以我们可对二叉树的高度加以限制,限制二叉树的高度最多为6层,如此二叉树的大小也就限定了,最多有26-1=63个结点,即满二叉树。 满二叉树可采用顺序结构来存储。如果对一棵有n个结点的满二叉树(其深度为log2(n+1))的结点按层次依次编号(从第一层到第log2(n+1)层,每层从左到右),则对任一结点i(1≤i≤n),有: (1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲Parent(i)是结点[i/2]。 (2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子LChild(i)是结点2i。 (3)如果2i+1>n,则结点i无右孩子;否则其右孩子RChild(i)是结点2i+1。 所以现在的问题转化为将含63个结点的满二叉树实现可视化,而可视化的关键是为63个结点设置坐标,结点坐标保存在point类型的数组p[1～63]中,point类有两个成员x和y。我们利用完全二叉树的的特点来实现,方法如下:例如在一个图形框PictureBox上绘制,可将绘图区域分成6层,每一层确定坐标的结点个数和高度为6的完全二叉树的每层结点个数相同,即第一层1个,第二层2个,第三层4个,第四层8个,第五层16个,第六层32个。先确定第六层各个结点的坐标,将绘图区域x轴平分为33份,得到32个坐标即p[32]～p[63]的x坐标为PictureBox.size.x/33*1～32。第五层各个结点的坐标用第六层各个结点的坐标计算得到,计算出第六层每两个结点横坐标的中点坐标,即Parent[i].x=⌊(LChild[2i].x+RChild[2i+1].x)/2⌋(p[i].x=(p[2i]+p[2i+1].x)/2),依此类推,各层结点的横坐标便可确定。每层的结点的纵坐标一样,需要说明的是为了保证视觉效果各层的纵坐标应拉开一定的距离,即LChild[2i].y=RChild[2i+1].y,Parent[i].y=LChild[2i].y-40=RChild[2i+1].y-40,依此类推。这一过程由createPoint()方法来实现。createPoint()方法建立63个点坐标向量,每个点有x和y两个坐标,如此一棵满二叉树的可视化坐标就建立好了。接下来就是绘制结点和边的问题了,由方法drawNode()和drawEdge()来实现。完全二叉树的可视化实现如图1所示。根据图我们可以发现任何两个同层结点都不会相交。 2.2 非完全二叉树的可视化实现 对于非完全二叉树,由于形态各异,为了实现起来简单而且对各种形态的二叉树均适用,运用非完全二叉树完全化的思想来实现,在结点类中增加了一个完全化编号成员,根结点的完全化编号为1,则LChild[2i].id=2*Parent[i].id,RChild[2i+1].id=2*Parent[i].id+1。各结点的坐标采用完全二叉树中对应结点的坐标,如为结点q设置坐标可用如下方法q.setX(p[q.getID()].x);q.setY(p[q.getID()].y,如此非完全二叉树的可视化坐标便可轻松获得,非完全二叉树的可视化就实现了。非完全二叉树的可视化实现如图2所示。 2.3 窗口刷新问题 另外在绘图的过程中,如果直接在窗口绘图,那么当发生窗口刷新(比如窗口最小化后恢复正常)或窗口被覆盖等情况时,所绘图形将被擦除。为避免这种情况发生,可先在绘图区域加载一副背景图片,在图片上进行绘制,如此便不会出现所绘图形将被擦除的情况。 2.4 二叉树可视化的应用 2.4.1 广义表形式建立二叉树 要生成二叉树实例,必须先知实例结点的结构。这必须区分一般数据和实例结点的左右子女链接信息,如指针。这里我们可利用编译技术来解决:把实例结点结构作为字符串参数传入函数,从中分离出各项目及数据类型。在文本框中输入二叉树的广义表形式,如a(b(c,d(e,f)),i(j,k(x,y))),调用LinkedBinaryTree(String s)方法建立二叉树,然后调用show方法可视化显示二叉树。所建二叉树如图3所示。 2.4.2 先序次序输入字符序列建立二叉树 在文本框中先序次序输入字符序列(如abc**de*g**f***,其中“*”表示子树为空),调用LinkedBinaryTree(String s,int pred)方法建立二叉树,然后调用show方法可视化显示二叉树。所建二叉树如图4所示。 2.4.3 动态可视遍历过程和算法的动态演示同步进行的实现 我们在设计动画时采用基于形状的动画。基于形状的动画也称为“子画面”动画,是更强大一种动画技术,在基于形状的动画中,每一个图形对象都成为子画面。并且可以随时间使位置发生变化[3]。以中序遍历为例,上面的窗口是遍历时的动态演示,利用椭圆、直线、文字、填充颜色等手段描绘出顶点,如将当前访问的结点描画成粗线条红色来体现遍历的动态过程;左下窗口是算法执行的动态演示,用字符的反显来体现算法的执行位置;上下窗口的动画演示是动态同步可视化进行的。中序遍历实现相对先序遍历较复杂,中序遍历左子树,访问根结点,然后中序遍历右子树。所以需设四个计时器timer1、timer2、timer3和timer4。遍历的同时还应体现出遍历过程中走过的路径,因此可将中序遍历递归算法中栈的变化情况捕获并加以显示。从栈的变化序列我们能够看出结点的值第一次出现表示结点进栈,该结点不被访问,第二次出现表示结点出栈,即该结点被访问。timer1控制算法的动态演示,timer2用来控制中序遍历的动态可视遍历过程,由于中序遍历的特点算法中访问结点visit(b.data)的图片显示由timer 5来控制,timer4用来控制栈的变化序列的显示,结点进栈则启动timer3,结点出栈则启动timer3。timer3显示了算法中访问结点visit(b.data)的图片后即启动timer2绘制被访问结点,如此便实现了两者的同步。算法的动态演示是通过循环图片来实现的,左右子树的图片不同;中序遍历的动态可视遍历过程是将被访问的结点用红色粗线条重新绘制,并同时在中序遍历序列文本框中显示被访问的结点值。中序遍历序列文本框中的文本变化、栈的变化序列文本框中的文本变化、中序遍历的动态可视遍历过程和算法的动态演示都是同步进行的。 3 实现二叉树可视化的意义 一方面解决了可视显示二叉树的问题,形象直观地将所建二叉树展现在用户眼前,解决了上机难的问题,“百闻不如一见”,介绍或学习抽象概念和训练抽象思维都需要自然和直观的方法。不管对“鱼”进行多么生动的描述,都不如亲眼看一看鱼的动态形象,而且后者能给人留下更深刻的印象。另一方面,实现周游二叉树算法的计算可视化,把周游的过程动态呈现了出来,数据结构及其算法的教学难点在于它们的抽象性和动态性,在课堂授课中采用图示可以在一定程度上化抽象为直观,但很难展现对象的瞬间动态特性和算法的动态执行过程,而这一点我们通过二叉树的可视化做到了。第三个方面,在数据结构中有各种各样的二叉树,如二叉排序树、平衡二叉树、Huffman树、堆、二叉判定树等等,二叉树可视化的实现为这些特殊的二叉树的可视化提供了可能。 摘要：在计算机科学领域中,二叉树是一种非常重要的非线形结构,实现其可视化具有重要意义。本文运用面向对象方法,利用完全二叉树特点实现了二叉树的可视化,实现了周游二叉树算法的计算可视化,实现了动态可视遍历过程和算法的动态演示同步进行。 关键词：二叉树,可视化,面向对象,数据结构,完全二叉树 参考文献 [1]殷人昆,邓俊辉.清华大学“数据结构”精品课程建设[J].计算机教育2006,(5). [2]苏莹,吴伟民,数据结构可视化类库的设计与实现[J].计算机技术与发展,2006. 关键词：二叉树;二叉树的遍历;二叉排序树;还原 中图分类号：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总结 在二叉树的一些应用中，如平衡二叉树、红黑树等，常常要观察二叉树的形态，对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。 参考文献 【二叉树的遍历学习心得】相关文章： 二叉树的遍历实验报告04-17 由二叉树遍历序列确定二叉树及其算法09-10 流形元覆盖系统的有向图遍历生成算法研究04-18 知识树的学习心得05-16 学习心得：学习《条例》心得体会04-18 机器学习学习心得07-06 行动学习学习心得07-20 行动学习学习心得05-10 管理沟通学习学习心得11-26 教师网络学习学习心得12-31篇3：二叉树的可视化实现
篇4：二叉树的遍历研究及还原研究