汉扬编程 C语言入门 C语言编程之二叉树的遍历图解

C语言编程之二叉树的遍历图解

C语言编程之二叉树的遍历图解

1、先序遍历(先访问根节点)先访问根节点

C语言编程之二叉树的遍历图解

再先序遍历左子树

C语言编程之二叉树的遍历图解

再先序遍历右子树

C语言编程之二叉树的遍历图解

例:下图:先访问根节点A,再先序访问A的左子树B。A的左子树B是一个树 ,所以先访问树B的根节点B,再访问B的左子树D。B的左子树D是一个树,所以先访问D的根节点D,再访问D的左子树,D没有左子树,再访问D的右子树,D没有右子树,那么D访问完毕。再访问D的父亲B的右子树。B没有右子树,那么B访问完毕。这样A的左子树访问完毕,序号为ABD。再访问A的右子树C。先访问C的根节点C,再访问C的左子树E,由于E没有左子树和右子树,所以E访问完毕。再访问C的右子树F。F也是树,所以先访问F的根节点F,再访问F的左子树G。G也是一个数,所以先访问G的根节点G,而G没有左右子树,G访问完毕。再访问G的父亲F的右子树。F没有右子树,所以F访问完毕。因为F是C的右子树,所以F访问完毕则C访问完毕。C访问完毕则整个树访问完毕!

C语言编程之二叉树的遍历图解

C语言编程之二叉树的遍历图解

先序b遍历

2、中序遍历(中间访问根节点)中序遍历左子树

再访问根节点

再中序遍历右节点

例:如下图:

第一步中序遍历A的左子树B,由于左子树B也是树,所以要先访问B的左子树D。由于左子树D也是树,所以要先访问D的左子树,D的左子树为空,所以第1个访问的是左子树的根节点D,再访问D的右子树,D的右子树为空。所以D访问完毕。D访问完毕则B的左子树访问完毕。第2个访问树B的根节点B。再访问B的右子树。因为B的右子树为空,所以B访问完毕。B访问完毕则A的左子树访问完毕,所以第3个访问的是A。再访问A的右子树C。因为C也是树,所以先访问C的左子树E。因为E也是树,所以先访问E的左子树,E的左子树为空,所以第4个访问的是E。再访问E的右子树,E的右子树为空,所以C的左子树访问完毕,接着访问C,所以第5个访问的是节点C。接着访问C的右子树F。因为F是树,所以先访问F的左子树G。因为G也是树,所以先访问G的左子树。G的左子树为空,所以第6个访问的是节点G。再访问G的右子树。G的右子树为空,所以节点G访问完毕。G访问完毕则F的左子树访问完毕,所以第7个访问的是节点F。F的右子树为空,所以F访问完毕,则C的右子树访问完毕,所以A的右子树访问完毕,整个树访问完毕!

中序遍历

3、后序遍历(最后访问根节点)后序遍历左子树

后续遍历右子树

再访问根节点

后续遍历

已知两种遍历序列求二叉树:只有已知一个树的先序和中序或者是后序和中序,才可以还原出二叉树的样子。知道先序和后序是不可以还原出二叉树。

例1、已知先序和中序还原出二叉树:

例1:已知先序:ABCDEFGH

中序:BDCEAFHG

求后序

解:先序中第一个出现的一定是根节点,所以在先序中第一个出现的A是根节点。中序中找出该根节点左边为左子树,右边为右子树。由于中序是先访问左子树再访问根节点再访问右子树。所以在中序中A的左边是A的左子树,所以BDCE是A的左子树;

从先序中找到BDCE的顺序是BCDE所以B是A左子树的根节点;

在中序中B的左边一定是B的左子树。由于B左边没有,所以B没有左子树,DCE是B的右子树;

在先序中DCE三个个节点C是第一个出现的,所以C是B右子树的根节点;

再从中序中D和E分别在C的左右,所以D是C的左子树,E是C的右子树,这样A的左子树确定那个。

再同样确定A的右子树 在中序中A的右边FHG在先序中F第一个出现,所以F是A的右子树的根节点;

再从中序中F左边没有,所以F没有左子树;HG是F的右子树;

再从先序中确定HG第一个出现的是G,所以G是F的右子树的根;

再从中序中G左边是H,右边没有,所以H是G的左子是,G没有右子树。

这样还原出树和后序如下图:

例2、已知后序和中序求先序:

已知中序:BDCEAFHG

后序:DECBHGFA

求先序。

解:后序中最后一个一定是根节点,再在中序中找出做右子树。

从后序中求出根节点:A;

从中序中求出A的左子树:BDCE,右子树:FHG;

后序中求出A的左子树BDCE的根结点:B;

中序中求出B的左子树:空,右子树:DCE;

后序中求出树DCE的根节点:C;

中序中求出C的左子树:D,右子树:E;

后序中求出树A的右子树FHG根节点:F;

中序中求出F的左子树:空,右子树:HG;

先序中求出树HG的根节点:G;

中序中求出节点G的左子树:H,右子树:空。

这样还原出二叉树和其先序如下图:

~~~end~~~

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6418.html

魔兽世界里面的宏到底是用什么语言编写的啊

求这个二叉树的前中后遍历

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部