二分搜索树遍历方式

二分搜索树的遍历方式

前言

二分搜索树是我们在编程中最常遇到的树结构，我们下面来聊聊二分搜索树的前序遍历、中序遍历和后序遍历。

树结构

int[] nums = {28, 16, 13, 22, 30, 42, 29};

          28
        /     \
       /       \
      /         \
     16          30
    /   \       /   \
   /     \     /     \
  /       \   /       \
13        22 29        42

树节点遍历

对于树节点，遍历的过程中都会经过三次。
28->16->13->13->13->16->22->22->22->16->28->30->29->29->29->30->42->42->42->30->28
前序遍历即各个节点的第一次遍历：
28->16->13->22->30->29->42
中序遍历即各个节点的第二次遍历：
13->16->22->28->29->30->42
后序遍历即各个节点的第三次遍历：
13->22->16->29->42->30->28

前序遍历

前序遍历，即为第一次经过该节点的时候对该节点进行标记。

/**
* 前序遍历
*/
public void preOrder() {
    preOrder(root);
}

/**
* 前序遍历
*
* @param node
*/
private void preOrder(Node node) {
    if (node == null) {
        return;
    }
    System.out.print(node.e + "\t");
    preOrder(node.left);
    preOrder(node.right);
}

输出结果：

28 16 13 22 30 29 42

中序遍历

中序遍历，即为第二次经过该节点的时候对该节点进行标记。

/**
 * 中序遍历，顺序
 */
public void inOrder() {
    inOrder(root);
}

/**
 * 中序遍历，顺序
 */
private void inOrder(Node node) {
    if (node == null) {
        return;
    }

    inOrder(node.left);
    System.out.print(node.e + "\t");
    inOrder(node.right);
}

输出结果：

13 16 22 28 29 30 42

后序遍历

后序遍历，即为第三次经过该节点的时候对该节点进行标记。

/**
 * 后序遍历
 */
public void postOrder() {
    postOrder(root);
}

/**
 * 后序遍历
 */
private void postOrder(Node node) {
    if (node == null) {
        return;
    }

    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.e + "\t");
}

输出结果：

13 22 16 29 42 30 28