Java数据结构学习之二叉树

什么是二叉树

二叉树是一种树形数据结构，他的每个节点最多有两个子节点，分别称为左子节点和右子节点。如果一个节点没有子节点，则成为叶子节点。二叉树具有以下性质：

• 每个节点最多有两个子节点
• 左子树和右子树是二叉树
• 二叉树可以为空

二叉树的遍历

为了遍历一棵树，我们可以采用两种算法：

深度优先遍历

深度优先遍历的思路是：从根节点出发，一直走到该方向没有节点为止，然后回溯到上一个节点，再取另一个子节点，重复执行直到遍历完整棵树。

二叉树有三种深度优先遍历方法：

前序遍历

前序遍历的访问顺序是：先访问该节点的值，然后遍历它的左子树，最后遍历右子树。

示例：

   1
 /   \
2     3

前序遍历的结果为：1 2 3

中序遍历

中序遍历的访问顺序是：先遍历左子树，然后访问该节点的值，最后遍历右子树。

示例：

   1
 /   \
2     3

中序遍历的结果为：2 1 3

后序遍历

后序遍历的访问顺序是：先遍历左子树，然后遍历右子树，最后访问该节点的值。

示例：

   1
 /   \
2     3

后序遍历的结果为： 2 3 1

广度优先遍历

广度优先遍历的思路是：从根节点开始，先遍历根节点，然后遍历它的所有子节点，再遍历子节点的子节点，一层一层地遍历下去。

广度优先遍历可以使用队列来实现。

示例：

   1
 /   \
2     3

广度优先遍历的结果为：1 2 3

二叉树的实现

在Java中，我们可以使用类来实现二叉树。

public class TreeNode {
    public int val;
    public TreeNode left, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

我们定义一个TreeNode类，它有三个属性：

• val：节点的值
• left：左子节点
• right：右子节点

二叉搜索树

二叉搜索树是二叉树的一种特殊形式，在二叉搜索树中，每个节点的值都比它左子树中的所有节点的值大，比右子树中的所有节点的值小。

二叉搜索树有以下特点：

• 左子树中所有节点的值都比根节点的值小
• 右子树中所有节点的值都比根节点的值大
• 左右子树分别也是二叉搜索树

二叉搜索树的遍历和普通二叉树一样，只需要根据节点值的大小关系和遍历顺序来区分即可。

二叉搜索树的实现

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int val) {
        root = insert(root, val);
    }

    private TreeNode insert(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
        } else if (val < root.val) {
            root.left = insert(root.left, val);
        } else if (val > root.val) {
            root.right = insert(root.right, val);
        }
        return root;
    }

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

    private void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }
}

我们定义一个BinarySearchTree类，它有一个属性root，表示二叉搜索树的根节点。它有两个方法：

• insert：插入一个节点
• inorderTraversal：中序遍历二叉搜索树

示例说明

示例一

假设我们要将下面这些数字插入到二叉搜索树中，并进行中序遍历：

5 2 7 1 3

我们定义一个BinarySearchTree实例，依次插入这些数字，然后进行中序遍历：

BinarySearchTree tree = new BinarySearchTree();
tree.insert(5);
tree.insert(2);
tree.insert(7);
tree.insert(1);
tree.insert(3);
tree.inorderTraversal();

输出结果为：

1 2 3 5 7

示例二

假设我们要对下面这棵二叉树进行前序遍历：

   1
 /   \
2     3

我们定义一个TreeNode实例，然后进行前序遍历：

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
preorderTraversal(root);

输出结果为：

1 2 3