如何由二叉樹的先序和中序序列畫出二叉樹？二叉樹可以由兩次遍歷的順序唯一地確定。例如，給定一個二叉樹，前序序列是abdecfg，中序序列是dbeafcg。二叉樹的根可以由前序序列確定為a，因為前序遍歷順

如何由二叉樹的先序和中序序列畫出二叉樹？

二叉樹可以由兩次遍歷的順序唯一地確定。例如，給定一個二叉樹，前序序列是abdecfg，中序序列是dbeafcg。二叉樹的根可以由前序序列確定為a，因為前序遍歷順序是從根到左子樹再到右子樹。然后從中階序列可以知道DBE在a的左子樹中，F(xiàn)CG在樹的右子樹中，B必須是a的左子樹的根，因為B在前階序列中跟隨a。在中尺度序列中，a的左子樹是DBE。中間序列的遍歷順序為：左子樹、父子樹和右子樹。我們可以看到，D是B的左子樹，E是B的右子樹，我們也可以分析樹根a的右子樹，前序序列中的ABDE已經(jīng)遍歷了根和左子樹，因此，剩余的CFG就是右子樹的前序遍歷序列。可以看出，C是右子樹的根，f是C的左子樹，G是C的右子樹，因此，二叉樹的遍歷序列應(yīng)該是ABCDEFG。