请分别写出下面二叉树的先序遍历,中序遍历和后序遍历的结果.pdfVIP

请分别写出下面二叉树的先序遍历,中序遍历和后序遍历的结果--第1页

请分别写出下面二叉树的先序遍

历,中序遍历和后序遍历的结果.

二叉树的遍历主要有三种：

（1）先(根)序遍历（根左右）

（2）中(根)序遍历（左根右）

（3）后(根)序遍历（左右根）

举个例子：

先(根)序遍历（根左右）：ABDHEICFJKG

中(根)序遍历（左根右）:DHBEIAJFKCG

后(根)序遍历（左右根）:HDIEBJKFGCA

以后(根)序遍历为例，每次都是先遍历树的左子树，

然后再遍历树的右子树，最后再遍历根节点，以此类推，直至

遍历完整个树。

此外，还有一个命题：给定了二叉树的任何一种遍历序

列，都无法唯一确定相应的二叉树。但是如果知道了二叉树的

中序遍历序列和任意的另一种遍历序列，就可以唯一地确定二

叉树。

请分别写出下面二叉树的先序遍历,中序遍历和后序遍历的结

果.1

(1)中序遍历：debac

后序遍历：dabec

请分别写出下面二叉树的先序遍历,中序遍历和后序遍历的结果--第1页

请分别写出下面二叉树的先序遍历,中序遍历和后序遍历的结果--第2页

后序遍历序列的最后一个结点是根结点，所以可知c为根结

点。

中序遍历序列的根结点在中间，其左边是左子树，右边是右子

树。所以从中序遍历序列中可看出，根结点c只有左子树，没

有右子树。

(2)中序遍历：deba

后序遍历：dabe

后序遍历序列的最后一个结点是根结点，所以可知e为c的左

子树的根结点。

中序遍历序列的根结点在中间，其左边是左子树，右边是右子

树。所以从中序遍历序列中可看出，根结点e的左子结点是

d，右子树是ba。

(3)中序遍历：ba

后序遍历：ab

由后序遍历序列可知b为e的右子树的根结点。由中序遍历序

列中可看出，a为根结点b的右子结点。

树的结构如下：

classNode:

def__init__(self,dat,left=None,right=None):

self.data=dat

self.left=left

self.right=right

defrebuild(rear,center):

ifnotrear:

请分别写出下面二叉树的先序遍历,中序遍历和后序遍历的结果--第2页

请分别写出下面二叉树的先序遍历,中序遍历和后序遍历的结果--第3页

return

cur=Node(rear[-1])

index=center.index(rear[-1])

cur.left=rebuild(rear[:index],center[:index])

cur.right=rebuild(rear[index:-1],center[index+

1:])#rear[index:-1]是到倒数第二个数

returncur

defpre_order(t):

ift==None:

return

print(t.data)

pre_order(t.left)

pre_order(t.right)

rear=[d,a,b,e,c]

center=[d,e,b,a,c]