以上就是二叉树前序遍历,中序遍历,后序遍历的所有内容。有问题欢迎指出。
以下面的例题为例进行讲解:已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列。
分析:先序遍历序列的第一个字符为根结点。对于中序遍历,根结点在中序遍历序列的中间,左边部分是根结点的左子树的中序遍历序列,右边部分是根结点的右子树的中序遍历序列。
先序:ABDCEF --> A BD CEF
中序:BDAECF --> BD A ECF
得出结论:A是树根,A有左子树和右子树,左子树有BD结点,右子树有CEF结点。
先序:BD --> B D
中序:BD --> B D
得出结论:B是左子树的根结点,B无左子树,有右子树(只有D结点)。
先序:CEF --> C E F
中序:ECF --> E C F
得出结论:C是右子树的根结点,C有左子树(只有E结点),有右子树(只有F结点)。
还原二叉树为:
A
B C
D EF
后序遍历序列:DBEFCA