二分搜索树深度优先遍历学习笔记

什么是二分搜索树？

二分搜索树（Binary Search Tree，简称BST）是一种数据结构，它具有以下特点：

• 每个节点最多只有两个子节点；
• 二分搜索树的左子树都小于根节点，右子树都大于根节点；
• 每个节点都可以看做一颗新的二分搜索树。

例如，下图就是一颗二分搜索树：

Copy Code
        5
       / \
      3   6
     / \   \
    2   4   8
           / \
          7   9

深度优先遍历

深度优先遍历（Depth-First-Search，简称DFS）是一种遍历二叉树的方法。常用的有以下三种遍历方式：

1. 前序遍历：先访问根节点，递归遍历左右子树；
2. 中序遍历：先递归遍历左子树，访问根节点，再递归遍历右子树；
3. 后序遍历：先递归遍历左右子树，访问根节点。

下面给出一个前序遍历的示例代码：

javaCopy Code
public void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + " ");
    preOrder(root.left);
    preOrder(root.right);
}

假设我们要遍历上述二分搜索树，其前序遍历结果为：5 3 2 4 6 8 7 9。

代码实例

下面给出一个使用Java实现的二分搜索树数据结构。代码中包含了前、中、后序遍历的实现。

javaCopy Code
public class BST<E extends Comparable<E>> {

    private Node root;

    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }

        return node;
    }

    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }

        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) < 0) {
            return contains(node.left, e);
        } else {
            return contains(node.right, e);
        }
    }

    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.e + " ");
        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.e + " ");
        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.e + " ");
    }
}

使用示例：

javaCopy Code
public static void main(String[] args) {
    BST<Integer> bst = new BST<>();

    bst.add(5);
    bst.add(3);
    bst.add(6);
    bst.add(2);
    bst.add(4);
    bst.add(8);
    bst.add(7);
    bst.add(9);

    bst.preOrder(); // 5 3 2 4 6 8 7 9
    System.out.println();

    bst.inOrder(); // 2 3 4 5 6 7 8 9
    System.out.println();

    bst.postOrder(); // 2 4 3 7 9 8 6 5
}

以上就是关于二分搜索树深度优先遍历的学习笔记。