如何根据二叉树前序和中序求后序
程序员文章站
2022-04-27 08:59:49
...
根据如下前序和中序字串求出后序
前序:
ABDCEF
中序:
DBAECF
分析:
首先要弄清楚二叉树遍历规则:
前序遍历方式为:根节点->左子树->右子树
中序遍历方式为:左子树->根节点->右子树
后序遍历方式为:左子树->右子树->根节点
根据这些原则,我们可以知道前序遍历字串的第一个字符即为整个树的根节点,本题即为A, 知道A后,去中序字串中查找其左子树(B)和右子树(DCE)。再根据根节点在中序中左右子树的长度,把前序遍历根节点的后半部分一分为二,即为左子树的前序和右子树的前序,分别根据左子树的前序和中序与右子树 的前序和中序递归求得左右子树。 参考代码如下(JAVA)
package interview.algorithm;
public class TreeIterator {
public Tree buildTree(String preIterator, String midIterator){
if (preIterator.length() != midIterator.length()){
return null;
}
if (preIterator.length() == 1){
return new Tree(preIterator);
}
String root = preIterator.substring(0, 1);
Tree tree = new Tree(root);
int rootIdx = midIterator.indexOf(root);
String newPreIterator;
String newMidIterator;
if (rootIdx != 0){//Left tree exists
newPreIterator = preIterator.substring(1, rootIdx + 1);
newMidIterator = midIterator.substring(0, rootIdx);
tree.left = this.buildTree(newPreIterator, newMidIterator);
}
if (rootIdx != midIterator.length()-1){//right tree exists
newPreIterator = preIterator.substring(rootIdx + 1);
newMidIterator = midIterator.substring(rootIdx + 1);
tree.right = this.buildTree(newPreIterator, newMidIterator);
}
return tree;
}
public String printPostorder(Tree tree){
StringBuffer buf = new StringBuffer();
if (tree.left != null){
buf.append(printPostorder(tree.left));
}
if (tree.right != null){
buf.append(printPostorder(tree.right));
}
buf.append(tree.data);
return buf.toString();
}
public static void main(String[] args){
String pre = "ABDCEF";
String mid = "DBAECF";
TreeIterator obj = new TreeIterator();
System.out.println(obj.printPostorder(obj.buildTree(pre, mid)));
//Output >>>> DBEFCA
}
}
class Tree{
String data;
Tree left;
Tree right;
public Tree(String data){
this.data = data;
}
}
还原后的树为:
求得后序为
DBEFCA
上一篇: 个人站长做好全站SEO检测的方法是什么?
推荐阅读
-
Python利用前序和中序遍历结果重建二叉树的方法
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
c/c++ 用前序和中序,或者中序和后序,创建二叉树
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
已知后序遍历和中序遍历求层序遍历(树的遍历)
-
剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解