前序遍历和中序遍历求后序遍历

红太狼 2022-07-27 16:42 150阅读 0赞

> 一个二叉树  
> 前序遍历：GDAFEMHZ  
> 中序遍历：ADEFGHMZ  
> 求其后续遍历。

**求解过程**

> 1.  这三种遍历不知道是什么意思的请自行搜索。
> 2.  通过前序遍历我们可知此树根节点为G（即前序遍历第一个字符）
> 3.  观测中序遍历可知此树左子树所有节点为：ADEF 右子树所有节点为：HMZ（以根节点划分）
> 4.  得到左子树的前序遍历（DAFE）中序遍历（ADEF） 顺序未变。
> 5.  得到右字数的前序遍历（MHZ）中序遍历（HMZ） 顺序未变。
> 6.  递归此过程，展开所有子树。

代码如下：  
定义二叉树的类

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());  
                }    
            }  
        }    
    }