树的遍历及根据遍历顺序反推树的形状
三种遍历顺序
以上是网上随便找的一个树
前序遍历: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的右子树, 推算完成
通过先序遍历和中序遍历反推时,改为通过前序遍历顺序的第一个值确定根节点即可得出