遍历和中序遍历求后序遍历"/>
前序遍历和中序遍历求后序遍历
一个二叉树
前序遍历:GDAFEMHZ
中序遍历:ADEFGHMZ
求其后续遍历。
求解过程
- 这三种遍历不知道是什么意思的请自行搜索。
- 通过前序遍历我们可知此树根节点为G(即前序遍历第一个字符)
- 观测中序遍历可知此树左子树所有节点为:ADEF 右子树所有节点为:HMZ(以根节点划分)
- 得到左子树的前序遍历(DAFE)中序遍历(ADEF) 顺序未变。
- 得到右字数的前序遍历(MHZ)中序遍历(HMZ) 顺序未变。
- 递归此过程,展开所有子树。
代码如下:
定义二叉树的类
view plain
public class Tree { String root = "";//根节点 Tree left; //左子树 Tree right; //右子树 String pre = "";//前序遍历字符串 String in = "";//中序遍历字符串 String back = "";//后序遍历字符串 Tree(String s){ this.root = s; } Tree(){}
}
实现代码:
view plain
public class testTree { public static String post = ""; /** * @param args */ public static void main(String[] args) { String pre = "GDAFEMHZ"; String in = "ADEFGHMZ"; Tree t = new Tree(); t.root = in; t.pre = pre; build(t); System.out.println(post); } /** * 采取后序遍历递归展开所有节点 * @param tree */ public static void build(Tree tree){ if(tree == null){ return; } open(tree); if(tree.left != null){ open(tree.left); build(tree.left); } if(tree.right != null){ open(tree.right); build(tree.right); } post = post + tree.root; } /** * 将节点不是单字符的节点展开 * @param tree */ public static void open(Tree tree){ if(tree.root.length()>1){ String s2 = tree.root; String s1 = tree.pre; tree.root =s1.substring(0, 1); String [] node = s2.split(tree.root); if(node.length>=2){ tree.left = new Tree(node[0]); tree.left.pre = s1.substring(1, node[0].length()+1); tree.right = new Tree(node[1]); tree.right.pre = s1.substring(s1.length()-node[1].length(), s1.length()); } } }
}
更多推荐
前序遍历和中序遍历求后序遍历
发布评论