树的遍历

概念

深度优先遍历有前序遍历、中序遍历、后序遍历三种方式。

• 前序遍历：根结点 ---> 左子树 ---> 右子树
• 中序遍历：左子树---> 根结点 ---> 右子树
• 后序遍历：左子树 ---> 右子树 ---> 根结点

广度优先遍历其实就是层次遍历。

摘自维基百科：

Pre-order, NLR

1. Access the data part of the current node (in the figure: position red).
2. Traverse the left subtree by recursively calling the pre-order function.
3. Traverse the right subtree by recursively calling the pre-order function.

The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.

In-order, LNR

1. Traverse the left subtree by recursively calling the in-order function.
2. Access the data part of the current node (in the figure: position green).
3. Traverse the right subtree by recursively calling the in-order function.

In a binary search tree ordered such that in each node the key is greater than all keys in its left subtree and less than all keys in its right subtree, in-order traversal retrieves the keys in ascending sorted order.^[6]

Reverse in-order, RNL

1. Traverse the right subtree by recursively calling the reverse in-order function.
2. Access the data part of the current node.
3. Traverse the left subtree by recursively calling the reverse in-order function.

In a binary search tree, reverse in-order traversal retrieves the keys in descending sorted order.

Post-order, LRN

1. Traverse the left subtree by recursively calling the post-order function.
2. Traverse the right subtree by recursively calling the post-order function.
3. Access the data part of the current node (in the figure: position blue).

代码

import java.util.Arrays;

public class TreeTraversals {


    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5};

        BinaryTree tree = new BinaryTree();
        tree.root = new Node(a[0]);
        tree.root.left = new Node(a[1]);
        tree.root.right = new Node(a[2]);
        tree.root.left.left = new Node(a[3]);
        tree.root.left.right = new Node(a[4]);

        System.out.println("原数组：" + Arrays.toString(a));

        System.out.println("\n前序遍历：");
        tree.printPreorder(tree.root);

        System.out.println("\n中序遍历：");
        tree.printInorder(tree.root);

        System.out.println("\n后序遍历：");
        tree.printPostorder(tree.root);

        System.out.println("\n层次遍历：");
        tree.printLevelOrder();
    }

}


class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BinaryTree {

    Node root;

    BinaryTree() {
        root = null;
    }

    void printPostorder(Node node) {
        if (node == null) {
            return;
        }

        printPostorder(node.left);

        printPostorder(node.right);

        System.out.print(node.key + " ");
    }


    void printInorder(Node node) {
        if (node == null) {
            return;
        }

        printInorder(node.left);

        System.out.print(node.key + " ");

        printInorder(node.right);
    }


    void printPreorder(Node node) {
        if (node == null) {
            return;
        }

        System.out.print(node.key + " ");

        printPreorder(node.left);

        printPreorder(node.right);
    }

    void printLevelOrder() {
        int h = height(root);
        int i;
        for (i = 1; i <= h; i++) {
            printGivenLevel(root, i);
        }

    }

    int height(Node root) {
        if (root == null) {
            return 0;
        } else {
            int lheight = height(root.left);
            int rheight = height(root.right);

            if (lheight > rheight) {
                return (lheight + 1);
            } else {
                return (rheight + 1);
            }
        }
    }

    void printGivenLevel(Node root, int level) {
        if (root == null) {
            return;
        }

        if (level == 1) {
            System.out.print(root.key + " ");
        } else if (level > 1) {
            printGivenLevel(root.left, level - 1);
            printGivenLevel(root.right, level - 1);
        }
    }


}