算法系列之数据结构-二叉树

修己xj

发布于 2025-03-12 13:01:21

9600

代码可运行

文章被收录于专栏：修己xj修己xj

运行总次数：0

代码可运行

在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和修改数据。树（Tree）是一种非常重要的非线性数据结构，广泛应用于各种算法和应用中。本文将详细介绍树的基本概念、常见类型以及用Java实现树的遍历。

树的基本概念

树是一种非线性数据结构，它由一组节点组成，每个节点最多只能有一个父节点，但可以有多个子节点。树的结构类似于自然界中的树，具有层次分明的特点。以下是数的一些基本术语：

根节点（Root）：树的顶端节点，没有父节点。
子节点（Child）：一个节点的直接下级节点。
父节点（Parent）：一个节点的直接上级节点。
叶子节点（Leaf）：没有子节点的节点。
深度（Depth）：从根节点到某个节点的路径长度。
高度（Height）：从某个节点到叶子节点的最长路径长度。

树的常见类型

二叉树（Binary Tree）

二叉树是一种特殊的树，每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树具有以下性质：

第i层的最大节点数为。
高度为k的二叉树最多有个节点。

满二叉树（Full Binary Tree）

满二叉树是指高度为k的二叉树并且有个节点的二叉树。及每层的节点数都是满的。

完全二叉树（Complete Binary Tree）

完全二叉树也是一种特殊的二叉树，除了最后一层，其他层都满，且最后一层节点从左到右排列。可见，满二叉树必为完全二叉树，但完全二叉树不一定是满二叉树。完全二叉树常用于实现堆结构。

平衡二叉树（Balanced Binary Tree）

平衡二叉树是一种特殊的二叉树，其中每个节点的左右子树高度差不超过1。AVL树和红黑树是平衡二叉树的两种常见实现。

二叉查找树（Binary Search Tree BST）

二叉查找树满足以下性质：对于任意节点，其左子树上所有节点的值小于该节点的值，右子树上所有节点的值大于该节点的值。二叉搜索树常用于实现查找、插入和删除操作。

二叉查找树是一种非常重要的数据结构，许多高技树结构都是二叉查找树的变种，如AVL树和红黑树。

红黑树（Red-Black Tree）

红黑树是一种特殊的二叉查找树。红黑树的每个节点上都有存储表示节点的颜色。这些规则使红黑树保证了一种平衡，插入、删除、查找最坏的时间复杂度都是O(logn)。

红黑树的统计性能要好于平衡二叉树，Java中，HashMap、HashSet、TreeSet 等都有红黑树的应用。

B树

B树是一种平衡的多路搜索树，每个节点可以包含多个子节点，通常用于磁盘存储系统。

特点：

节点结构：每个节点最多有 m 个子节点，m−1 个键（M为树的阶数）。
平衡性：所有叶子节点位于同一层。
键值：节点中的键按升序排列，且每个键的左子树键值小于它，右子树键值大于它。
操作：插入和删除通过分裂和合并节点保持平衡。

B树常用于数据库索引和文件系统，因为它能够高效地支持范围查询和顺序扫描。

B+树

B+树是B树的变种，数据仅存储在叶子节点，内部节点仅用于索引。

特点：

节点结构：内部节点有 m 个子节点和 m−1 个键，叶子节点包含所有键和数据。
顺序访问：叶子节点通过指针连接，支持高效的范围查询。
平衡性：所有叶子节点在同一层。
操作：插入和删除通过分裂和合并节点保持平衡。

B+树广泛应用于数据库索引和文件系统，尤其是在需要频繁进行范围查询和顺序扫描的场景中。例如，MySQL的InnoDB存储引擎就使用B+树作为索引结构。

B*树

B*树是B树的另一种变种，通过增加节点利用率减少分裂频率。

特点：

节点结构：每个节点至少有个子节点，比B树更紧凑。
分裂策略：在插入时，B*树会尝试将键重新分配到兄弟节点，延迟分裂。
平衡性：所有叶子节点在同一层。
操作：插入和删除通过键重新分配和节点分裂保持平衡。

常用于需要高节点利用率的数据库和文件系统。

R树

R树是一种用于空间数据索引的树结构，专门设计用于高效处理多维数据（如地理坐标、矩形区域等）。它广泛应用于地理信息系统（GIS）、数据库和计算机图形学等领域。

Java实现二叉树及遍历

前序遍历

首选访问根节点，然后前序遍历其左子树，最后遍历其右子树，遍历左右子树时仍使用前序遍历。

中序遍历

首选遍历根节点的左子树，然后访问根节点，最后中序遍历其右子树，遍历左右子树时仍使用中序遍历。

后序遍历

首选后序遍历其左子树，然后后序遍历其右子树，最后访问根节点。遍历左右子树时仍使用后序遍历。

层次遍历

层次遍历使用队列来实现，按层次从上到下、从左到右遍历节点。也是广度优先遍历。

我们使用java 递归实现二叉树的前序遍历、中序遍历、后序遍历、层次遍历。

/**
 * 二叉树节点实体类
 */
@Data
publicclass BinaryTreeNode<T> {
    private T val;
    private BinaryTreeNode<T> left;
    private BinaryTreeNode<T> right;

    public BinaryTreeNode(T val) {
        this.val = val;
    }


}



/**
 * 二叉树遍历
 */
publicclass BinaryTreeExample<T> {
    /**
     * 前序遍历
     * 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。
     */
    public static void preOrder(BinaryTreeNode<Integer> node, List<Integer> result){
        // 递归结束条件:节点为空则结束递归
        if(node == null){
            return;
        }
        //先访问根节点
        result.add(node.getVal());
        //遍历左子树
        preOrder(node.getLeft(), result);
        //遍历右子树
        preOrder(node.getRight(), result);
    }

    /**
     * 中序遍历
     * 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
     */
    public static void inOrder(BinaryTreeNode<Integer> node, List<Integer> result){
        // 递归结束条件:节点为空则结束递归
        if(node == null){
            return;
        }
        //遍历左子树
        inOrder(node.getLeft(), result);
        //访问根节点
        result.add(node.getVal());
        //遍历右子树
        inOrder(node.getRight(), result);
    }

    /**
     * 后续遍历
     * 后序遍历的顺序是：左子树 -> 右子树 -> 根节点。
     */
    public static void postOrder(BinaryTreeNode<Integer> node, List<Integer> result){
        // 递归结束条件:节点为空则结束递归
        if(node == null){
            return;
        }
        //遍历左子树
        postOrder(node.getLeft(), result);
        //遍历右子树
        postOrder(node.getRight(), result);
        //访问根节点
        result.add(node.getVal());
    }

    /**
     * 层序遍历
     */
    public static void levelOrder(BinaryTreeNode<Integer> start, List<Integer> result){
        if(start == null){
            return;
        }
        //创建一个队列
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            BinaryTreeNode<Integer> node = queue.poll();
            result.add(node.getVal());

            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            }
            if (node.getRight() != null) {
                queue.offer(node.getRight());
            }
        }
    }

    public static void main(String[] args) {
        BinaryTreeNode<Integer> node1 =  new BinaryTreeNode<>(1);
        BinaryTreeNode<Integer> node2 = new BinaryTreeNode<>(3);
        BinaryTreeNode<Integer> node3 = new BinaryTreeNode<>(2);
        BinaryTreeNode<Integer> node4 = new BinaryTreeNode<>(5);
        BinaryTreeNode<Integer> node5 = new BinaryTreeNode<>(4);
        BinaryTreeNode<Integer> node6 = new BinaryTreeNode<>(2);
        BinaryTreeNode<Integer> node7 = new BinaryTreeNode<>(6);
        BinaryTreeNode<Integer> node8 = new BinaryTreeNode<>(8);
        BinaryTreeNode<Integer> node9 = new BinaryTreeNode<>(7);
        BinaryTreeNode<Integer> node10 = new BinaryTreeNode<>(9);
        BinaryTreeNode<Integer> node11 = new BinaryTreeNode<>(6);
        BinaryTreeNode<Integer> node12 = new BinaryTreeNode<>(5);
        node1.setLeft(node2);
        node1.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        node3.setRight(node7);
        node4.setLeft(node8);
        node4.setRight(node9);
        node5.setLeft(node10);
        node5.setRight(node11);
        node6.setLeft(node12);

        List<Integer> result1 = new ArrayList<>();
        List<Integer> result2 = new ArrayList<>();
        List<Integer> result3 = new ArrayList<>();
        List<Integer> result4 = new ArrayList<>();
        //前序遍历
        preOrder(node1, result1);
        System.out.println("前序遍历:"+result1.toString());
        //中序遍历
        inOrder(node1, result2);
        System.out.println("中序遍历:"+result2.toString());
        //后序遍历
        postOrder(node1, result3);
        System.out.println("后序遍历:"+result3.toString());
        //层序遍历
        levelOrder(node1, result4);
        System.out.println("层序遍历:"+result4.toString());


    }
}

运行结果如下：

前序遍历:[1, 3, 5, 8, 7, 4, 9, 6, 2, 2, 5, 6]
中序遍历:[8, 5, 7, 3, 9, 4, 6, 1, 5, 2, 2, 6]
后序遍历:[8, 7, 5, 9, 6, 4, 3, 5, 2, 6, 2, 1]
层序遍历:[1, 3, 2, 5, 4, 2, 6, 8, 7, 9, 6, 5]