二分搜索树的遍历

深度优先遍历

  • 前序遍历:先访问当前节点,再依次递归访问左右子树;

  • 中序遍历:先递归访问左子数,再访问自身,再递归访问右子树;

  • 后序遍历:先递归访问左右子树,再访问自身节点;

广度优先遍历

  • 层序遍历

前序遍历

public void preOrder() {
    preOrder(root);
}
private void preOrder(Node node) {
    if (node == null) {
        return;
    }
    System.out.print(node.value);
    preOrder(node.left);
    preOrder(node.right);
}

中序遍历

public void inOrder() {
    inOrder(root);
}
private void inOrder(Node node) {
    if (node == null) {
        return;
    }
    inOrder(node.left);
    System.out.print(node.value);
    inOrder(node.right);
}

后序遍历

// 后序遍历
public void postOrder() {
    postOrder(root);
}
private void postOrder(Node node) {
    if (node == null) {
        return;
    }
    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.value);
}

层序遍历

// 层序遍历
public void levelOrder() {
    LinkedList<Node> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        Node node = q.remove();
        System.out.print(node.value);
        if (node.left != null) {
            q.add(node.left);
        }
        if (node.right != null) {
            q.add(node.right);
        }
    }
}

results matching ""

    No results matching ""