当前位置： 首页 > article >正文

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

article 2025/3/4 19:17:07

_20250303234623.jpg

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

树的基本概念

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

  • 根节点（Root）：树的顶端节点，没有父节点。

  • 子节点（Child）：一个节点的直接下级节点。

  • 父节点（Parent）：一个节点的直接上级节点。

  • 叶子节点（Leaf）：没有子节点的节点。

  • 深度（Depth）：从根节点到某个节点的路径长度。

  • 高度（Height）：从某个节点到叶子节点的最长路径长度。

_20250303212232.jpg

树的常见类型

  1. 二叉树（Binary Tree）

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

  • 第i层的最大节点数为 2 i − 1 2^{i-1} 2i−1。

  • 高度为k的二叉树最多有 2 k − 1 2^k - 1 2k−1个节点。

  1. 满二叉树（Full Binary Tree）

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

  1. 完全二叉树（Complete Binary Tree）

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

  1. 平衡二叉树（Balanced Binary Tree）

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

  1. 二叉查找树（Binary Search Tree BST）

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

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

  1. 红黑树（Red-Black Tree）

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

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

  1. B树

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

特点：

  • 节点结构：每个节点最多有 m 个子节点，m−1 个键（M为树的阶数）。

  • 平衡性：所有叶子节点位于同一层。

  • 键值：节点中的键按升序排列，且每个键的左子树键值小于它，右子树键值大于它。

  • 操作：插入和删除通过分裂和合并节点保持平衡。

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

  1. B+树

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

特点：

  • 节点结构：内部节点有 m 个子节点和 m−1 个键，叶子节点包含所有键和数据。

  • 顺序访问：叶子节点通过指针连接，支持高效的范围查询。

  • 平衡性：所有叶子节点在同一层。

  • 操作：插入和删除通过分裂和合并节点保持平衡。

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

  1. B*树

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

特点：

  • 节点结构：每个节点至少有 个子节点，比B树更紧凑。

  • 分裂策略：在插入时，B*树会尝试将键重新分配到兄弟节点，延迟分裂。

  • 平衡性：所有叶子节点在同一层。

  • 操作：插入和删除通过键重新分配和节点分裂保持平衡。

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

  1. R树

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

Java实现二叉树及遍历

  • 前序遍历

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

  • 中序遍历

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

  • 后序遍历

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

  • 层次遍历

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

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

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

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


}



/**
 * 二叉树遍历
 */
public class 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]

总结

二叉树是一种非常重要的数据结构，广泛应用于各种算法和应用中。通过本文的介绍，您应该对树的基本概念、常见类型以及在Java中的实现有了更深入的理解。掌握树结构不仅有助于提高编程能力，还能帮助您更好地理解和设计复杂的算法。


http://www.kler.cn/a/570521.html

相关文章：

  • 通俗易懂版 Maven 科普,maven是什么?
  • GMAC网络延时性能优化
  • QT 记事本程序开发
  • RHCE9.0版本笔记3：创建、查看和编辑文本文件
  • Spark核心之03写mysql、写HBase、RDD宽窄依赖、DAG、缓存、Checkpoint
  • GSMA SAS 安全生产审计检查清单
  • ARM MTE
  • C++：类和对象(下篇)
  • 内网穿透的应用-企业级远程办公方案：NAS部署网页版Linux，HTTPS加密访问全配置
  • 【word】电子签名设置、保存和调用
  • 蓝桥杯 之 图形规律
  • 算法进阶——二分
  • 美团面试题解析：new Integer(“127“)和Integer.valueOf(“128“) 的底层差异与缓存机制
  • Java【多线程】（2）线程属性与线程安全
  • 前端-css
  • 物联网中水位计顶级功能有哪些
  • Muduo + OpenSSL 网络交互完整流程
  • 如何在MacOS 10.15上安装Docker Desktop
  • 数据结构（三）链表
  • 使用 CodeMirror 6 和 React 构建一个支持只读模式的 JSON 编辑器