欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

如何根据二叉树前序和中序求后序

程序员文章站 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
相关标签: Tree