【数据结构】树的遍历

                                                     树的遍历

以前序遍历为例

（1）先遍历树根

（2）然后前序遍历左子树

（3）最后前序遍历右子树

 

对于这样的一个二叉树

前序遍历结果：ABDEGCF

遍历流程：

【1】首先遍历树根，输出A

【2】对A的左子树进行前序遍历，怎么前序遍历？对于B这个左子树而言，首先遍历根节点，输出B

【3】然后遍历子树B的左子树，得到D这个子树，对D进行前序遍历，首先遍历树根节点，输出D

【4】然后遍历D的左子树，不存在。那就遍历D的右子树，不存在。此时B的左子树D遍历完成

【5】遍历B的右子树E，则前序遍历E，首先遍历树根结点，输出E

【6】遍历E的左子树，得到子树G，对于子树G，前序遍历G，得到树根节点G，输出G，此时G遍历完成

【7】此时A的左子树遍历完成，现在开始遍历A的右子树C，前序遍历C，得到树根结点，输出C

【8】遍历C的左子树，不存在，则遍历其右子树，得到子树F，前序遍历F，得到树根结点F，输出F

 

同理，中序遍历结果：DBGEACF

           后序遍历结果：DGEBFCA

 

树的遍历  代码演示

节点类

public class TreeNode {
    private final char value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public char getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

人肉构造一棵树，也就是图中的那棵树

public class TreeCreator {
    public TreeNode createTree() {
        TreeNode root = new TreeNode('A');
        root.setLeft(new TreeNode('B'));
        root.setRight(new TreeNode('C'));
        root.getLeft().setLeft(new TreeNode('D'));
        root.getLeft().setRight(new TreeNode('E'));
        root.getLeft().getRight().setLeft(new TreeNode('G'));
        root.getRight().setRight(new TreeNode('F'));
        return root;
    }
}

前序遍历、中序遍历、后序遍历代码

public class Main {
    //前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getValue());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.getLeft());
        System.out.print(root.getValue());
        inOrder(root.getRight());

    }

    //后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue());
    }


    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        Main main = new Main();
        System.out.print("前序遍历:");
        main.preOrder(creator.createTree());
        System.out.println();
        System.out.print("中序遍历:");
        main.inOrder(creator.createTree());
        System.out.println();
        System.out.print("后序遍历:");
        main.postOrder(creator.createTree());
    }
}

最后的输出为

总结：树的遍历其实就是一种递归的过程，三个遍历的主要区别在于输出树根结点的时机