二叉树遍历

问题：根据先序遍历和中序遍历，求解后序遍历

思路：

• 第一步，将先序和中序字符串进行划分。
  先序：1--247--3568，中序：472--1--5386，由此可见，数字247属于左边的树结点，数字3568属于右边的树结点，1属于根结点
• 第二步，根据第一步的规律，进行递归赋值。顶点作为根结点。分别设置其左右结点，如果没有则为Null。
• PS:substring方法传入的第一个参数不能大于字符串长度或者为负数。并且当参数相同时，返回的字符串长度为0。

二叉树.png

代码实现：

public class N06 {

    public static void main(String[] args) {
        String preOrder = "12473568";
        String inOrder = "47215386";
        BinaryTree binaryTree = new BinaryTree(preOrder, inOrder);
        TreeNode root = binaryTree.root;
        
        System.out.println("pre order: ");
        binaryTree.preTreeTraverse(root);
        System.out.println();
        
        System.out.println("in order: ");
        binaryTree.inTreeTraverse(root);
        System.out.println();
        
        System.out.println("post order: ");
        binaryTree.postTreeTreverse(root);
        System.out.println();
    }

}

class BinaryTree {
    TreeNode root;

    public BinaryTree(String preOrder, String inOrder) {
        if (preOrder.length() == 0)
            return;
        char key = preOrder.charAt(0);
        int index = inOrder.indexOf(key);
        root = new TreeNode(key);

        this.root.setLeftNode(new BinaryTree(preOrder.substring(1, index + 1), inOrder.substring(0, index)).root);
        this.root.setRightNode(new BinaryTree(preOrder.substring(index + 1),inOrder.substring(index+1)).root);

    }

    public void preTreeTraverse(TreeNode root) {
        //先序遍历
        if (root != null) {
            System.out.print(root.data+"  ");
            preTreeTraverse(root.leftNode);
            preTreeTraverse(root.rightNode);

        }
    }

    public void inTreeTraverse(TreeNode root) {
        //中序遍历
        if (root != null) {
            inTreeTraverse(root.leftNode);
            System.out.print(root.data+"  ");
            inTreeTraverse(root.rightNode);
        }
    }

    public void postTreeTreverse(TreeNode root) {
        //后序遍历
        if (root != null) {
            postTreeTreverse(root.leftNode);
            postTreeTreverse(root.rightNode);
            System.out.print(root.getData()+"  ");
        }
        
    }
}

class TreeNode {
    char data;
    TreeNode leftNode;
    TreeNode rightNode;

    public TreeNode(char data) {
        this.data = data;
    }

    public char getData() {
        return data;
    }

    public void setData(char data) {
        this.data = data;
    }

    public TreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
}

参考

根据先序遍历与中序遍历构建二叉树