树的遍历及根据遍历顺序反推树的形状

遍历及根据遍历顺序反推树的形状"/>

树的遍历及根据遍历顺序反推树的形状

三种遍历顺序

以上是网上随便找的一个树
前序遍历：FCADBEHGM（根左右）
中序遍历：ACBDFHEMG（左根右）
后序遍历：ABDCHMGEF（左右根）

中序遍历步骤

中序遍历的规则是【左根右】，我们从root节点A看起；

此时F是根节点，遍历F的左子树；

F的左子树存在，找到C，此时C看做根节点，遍历C的左子树；

C的左子树存在，找到A，此时A看做根节点，遍历A的左子树；

A的左子树不存在，返回A，根据【左根右】的遍历规则，记录A，遍历A的右子树；（此时记录顺序为：A）

A的右子树不存在，返回C，根据【左根右】的遍历规则，记录C，遍历C的右子树；（此时记录顺序为：AC）

C的右子树存在，找到D，此时D看做根节点，遍历D的左子树

D的左子树存在，找到B，B为叶子节点，左右子树不存在，记录B，返回D, 根据【左根右】的遍历规则，记录D，遍历D的右子树；（此时记录顺序为：ACBD）

D的右子树不存在，至此，F的左子树遍历完毕，根据【左根右】的遍历规则，记录F，遍历F的右子树；（此时记录顺序为：ACBDF）

F的右子树存在，找到E，此时E看做根节点，遍历E的左子树；

E的右子树存在，找到H，此时H看做根节点，遍历H的左子树；

H为根节点，左右子树不存在，记录H，返回E, 根据【左根右】的遍历规则，记录E，遍历E的右子树；（此时记录顺序为：ACBDFHE）

E的右子树存在，找到G，此时G看做根节点，遍历G的左子树；

G的左子树存在，找到M，M为叶子节点，左右子树不存在，记录M，返回G, 根据【左根右】的遍历规则，记录G,遍历G的右子树，不存在, 结束遍历（此时记录顺序为：ACBDFHEMG）

前序遍历和后序遍历步骤分别按照【根左右】【左右根】规则同样可得。

通过后序遍历和中序遍历反推树的形状

中序遍历：ACBDFHEMG（左根右）
后序遍历：ABDCHMGEF（左右根）

首先，通过后续遍历最后一个值拿到根节点F

根据中序遍历知道F的左子树有ACBD, 右子树有HEMG

在后序遍历中找到ACBD，通过排列顺序ABDC取最后一个值C即为F的左子树的根节点。

根据中序遍历知道C的左子树有A, 右子树有BD。

在后序遍历中找到BD，通过排列顺序去最后一个值D即为C的右子树的根节点。

根据中序遍历知道D的左子树有B, 无右子树

至此，得出F的左子树， 看右子树。

在后序遍历中找到HEMG，通过排列顺序HMGE取最后一个值E即为F的右子树的根节点。

根据中序遍历知道E的左子树有H, 右子树有MG。

在后序遍历中找到MG，通过排列顺序去最后一个值G即为E的右子树的根节点。

根据中序遍历知道G的左子树有M, 无右子树

至此，得出F的右子树， 推算完成

通过先序遍历和中序遍历反推时，改为通过前序遍历顺序的第一个值确定根节点即可得出