Java——二叉树

🕗 发布于 2024-04-17 10:24 数据结构 算法 java

二叉树

二叉树在Java中是一种重要的数据结构，用于高效地组织和处理具有层级关系的数据。

二叉树的每个节点最多有两个子节点，这两个子节点分别称为左子节点和右子节点。这种结构非常适合于使用递归的方式进行定义和操作。在计算机科学中，二叉树可以用于多种算法和应用，如排序、搜索以及作为其他复杂数据结构如堆、红黑树等的基础。

下面是关于二叉树的一些重要概念：

基本定义：二叉树是节点的集合，可以是空集或由一个根节点和两棵互不相交的左右子树组成。
特殊类型：有满二叉树和完全二叉树等特殊形式，它们在特定条件下拥有最优的存储和操作效率。
性质：二叉树的第i层最多有2^(i-1)个节点，深度为k的二叉树至多有2^k - 1个节点。
操作：二叉树可以有多种操作，包括不同方式的遍历（前序、中序、后序），查找特定值的节点，以及计算二叉树的高度等。
应用：二叉树常应用于文件系统、排序算法和内存管理等领域。
实现：在Java中，可以通过创建一个包含左右子节点引用的TreeNode类来表示二叉树的节点。然后可以通过创建TreeNode对象并设置它们的链接来构建整个二叉树结构。

以下是一个简单的Java二叉树节点类的示例：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

在这个类中，val变量用于存储节点的值，left和right变量分别指向左子节点和右子节点。

要创建一个二叉树，我们可以手动创建节点并将它们链接起来，或者使用递归方法自动创建。以下是一个简单的递归创建二叉树的示例：

public TreeNode createBinaryTree(int[] values, int index) {
    if (index >= values.length || values[index] == -1) {
        return null;
    }
    TreeNode node = new TreeNode(values[index]);
    node.left = createBinaryTree(values, 2 * index + 1);
    node.right = createBinaryTree(values, 2 * index + 2);
    return node;
}

在这个函数中，我们首先检查索引是否超出数组的范围或者当前值是否为-1（表示空节点），如果是则返回null。然后我们创建一个新的节点，并递归地为其左子节点和右子节点赋值。

二叉树有许多重要的操作，如遍历、查找和插入等。以下是一个简单的前序遍历二叉树的示例：

public void preorderTraversal(TreeNode node) {
    if (node == null) {
        return;
    }
    System.out.print(node.val + " ");
    preorderTraversal(node.left);
    preorderTraversal(node.right);
}

在这个函数中，我们首先打印当前节点的值，然后递归地遍历左子树和右子树。这就是前序遍历的基本思想。

二叉排序树

Java中的二叉排序树是一种特殊的二叉树，它具有明确的排序性质。以下是关于二叉排序树的一些关键点：

定义和性质：二叉排序树（BST）是具有以下特性的二叉树，对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。这种性质保证了二叉排序树在查找、插入和删除等操作上具有较高的效率。
创建和遍历：可以通过插入操作逐个添加节点来创建二叉排序树。遍历方式包括前序遍历、中序遍历和后序遍历，其中中序遍历可以得到树中所有元素的升序排列。
实现细节：在Java中实现二叉排序树时，通常定义一个包含元素值以及指向左右子节点引用的Node类。通过维护二叉排序树的性质，可以确保树在执行各种操作时保持正确的结构。
实际应用：由于二叉排序树具有快速检索的特点，它们常被用于数据库索引、有序集合等数据结构中，以提供高效的数据检索和管理功能。
注意事项：在处理二叉排序树时需要注意，如果插入的数据违反了二叉排序树的定义，那么树的结构将不会被正确维护。因此，插入和删除操作必须谨慎执行，以确保树的排序性质不被破坏。

以下是一个简单的Java二叉排序树实现示例：

public class BinarySortTree {
    private Node root;

    private static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

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

    private Node insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        }

        return node;
    }

    public boolean contains(int value) {
        return contains(root, value);
    }

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

        if (value < node.value) {
            return contains(node.left, value);
        } else if (value > node.value) {
            return contains(node.right, value);
        } else {
            return true;
        }
    }

    public void remove(int value) {
        root = remove(root, value);
    }

    private Node remove(Node node, int value) {
        if (node == null) {
            return null;
        }

        if (value < node.value) {
            node.left = remove(node.left, value);
        } else if (value > node.value) {
            node.right = remove(node.right, value);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            node.value = minValue(node.right);
            node.right = remove(node.right, node.value);
        }

        return node;
    }

    private int minValue(Node node) {
        int minValue = node.value;
        while (node.left != null) {
            minValue = node.left.value;
            node = node.left;
        }
        return minValue;
    }
}

在这个示例中，我们定义了一个BinarySortTree类，它包含一个根节点root和一个内部类Node。Node类表示二叉排序树的节点，包含一个整数值、一个左子节点和一个右子节点。BinarySortTree类提供了插入、查找和删除等基本操作的方法。

平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉搜索树，它的每个节点的左子树和右子树的高度差不超过1。这种数据结构可以保证在插入、删除和查找操作时具有较高的效率，时间复杂度为O(log n)。

在Java中，可以使用AVL树（一种自平衡二叉搜索树）来实现平衡二叉树。AVL树是一种高度平衡的二叉搜索树，它在每次插入或删除节点后，都会通过旋转操作来保持树的平衡。

AVL树的基本操作包括：

插入（Insert）：向AVL树中插入一个新的键值。
删除（Delete）：从AVL树中删除一个键值。
查找（Search）：在AVL树中查找一个指定的键值。
旋转（Rotate）：通过旋转操作来保持树的平衡。

AVL树的主要优点是在保持平衡的同时，还能保持二叉搜索树的性质，因此在查找、插入和删除操作时具有较高的效率。但是，由于需要维护平衡，AVL树的实现相对复杂。

如何保持平衡

AVL树通过在每个节点上维护一个平衡因子来保持平衡。平衡因子是该节点的左子树的高度与右子树的高度之差。平衡因子可以是 -1、0 或 1，这确保了每个节点的左右子树的高度差不会超过 1，从而维持了树的平衡状态。

当执行插入或删除操作时，AVL树会检查每个受影响节点的平衡因子。如果任何节点的平衡因子变为非法值（即不是 -1、0 或 1），则会进行一系列旋转来恢复平衡。这些旋转操作包括：

单旋转：当一个节点的平衡因子变为非法值时，如果不平衡在节点的某一侧，那么只需要一次旋转就可以恢复平衡。这又分为：

右旋：如果节点的左子树高度大于右子树，需要进行右旋。
左旋：如果节点的右子树高度大于左子树，需要进行左旋。

双旋转：如果不平衡在节点的两侧，可能需要两次旋转来恢复平衡。这又分为：

左右旋：首先对节点的左孩子进行左旋，然后对节点进行右旋。
右左旋：首先对节点的右孩子进行右旋，然后对节点进行左旋。

通过这些旋转操作，AVL树可以在每次插入或删除后保持平衡，确保了操作的时间复杂度保持在 O(log n)。

总结来说，AVL树通过以下方式保持平衡：

维护每个节点的平衡因子。
在插入和删除操作后检查并更新平衡因子。
如果检测到不平衡，使用旋转操作来重新平衡。

代码示例

class Node {
    int key, height;
    Node left, right;

    Node(int d) {
        key = d;
        height = 1;
    }
}

class AVLTree {
    Node root;

    int height(Node N) {
        if (N == null)
            return 0;
        return N.height;
    }

    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        return x;
    }

    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        return y;
    }

    int getBalance(Node N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    Node insert(Node node, int key) {
        if (node == null)
            return (new Node(key));

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else
            return node;

        node.height = 1 + max(height(node.left), height(node.right));

        int balance = getBalance(node);

        if (balance > 1 && key < node.left.key)
            return rightRotate(node);

        if (balance < -1 && key > node.right.key)
            return leftRotate(node);

        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }
}

红黑树

Java中的红黑树是一种自平衡的二叉查找树，它通过颜色和结构规则来保持树的平衡。

红黑树是一种特殊的二叉查找树，它的每个节点都有一个颜色属性，要么是红色，要么是黑色。红黑树需要满足以下条件：

节点颜色：每个节点要么是红色，要么是黑色。
根节点是黑色：树的根节点必须是黑色。
叶子节点是黑色：所有叶子节点（NIL节点，空节点）都是黑色。
红色节点的规则：如果一个节点是红色，那么它的两个子节点都必须是黑色。
路径上的黑色节点数量：从任一节点到其后代叶子的所有路径上包含相同数目的黑节点。

当进行插入或删除操作时，可能会破坏上述规则，此时需要通过旋转和重新着色来修复，以确保树继续保持平衡。旋转分为左旋和右旋，用于改变树的结构；重新着色则是改变某些节点的颜色，以符合红黑树的规则。

public class RedBlackTree {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        int key;
        Node left, right, parent;
        boolean color;

        Node(int key) {
            this.key = key;
            this.color = RED;
        }
    }

    private Node root;

    public void insert(int key) {
        Node newNode = new Node(key);
        if (root == null) {
            root = newNode;
            root.color = BLACK;
        } else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (key < current.key) {
                    current = current.left;
                    if (current == null) {
                        parent.left = newNode;
                        newNode.parent = parent;
                        break;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = newNode;
                        newNode.parent = parent;
                        break;
                    }
                }
            }
            fixInsert(newNode);
        }
    }

    private void fixInsert(Node node) {
        while (node != root && node.parent.color == RED) {
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                if (uncle != null && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.right) {
                        node = node.parent;
                        rotateLeft(node);
                    }
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    rotateRight(node.parent.parent);
                }
            } else {
                Node uncle = node.parent.parent.left;
                if (uncle != null && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        rotateRight(node);
                    }
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    rotateLeft(node.parent.parent);
                }
            }
        }
        root.color = BLACK;
    }

    private void rotateLeft(Node node) {
        Node temp = node.right;
        node.right = temp.left;
        if (temp.left != null) {
            temp.left.parent = node;
        }
        temp.parent = node.parent;
        if (node.parent == null) {
            root = temp;
        } else if (node == node.parent.left) {
            node.parent.left = temp;
        } else {
            node.parent.right = temp;
        }
        temp.left = node;
        node.parent = temp;
    }

    private void rotateRight(Node node) {
        Node temp = node.left;
        node.left = temp.right;
        if (temp.right != null) {
            temp.right.parent = node;
        }
        temp.parent = node.parent;
        if (node.parent == null) {
            root = temp;
        } else if (node == node.parent.right) {
            node.parent.right = temp;
        } else {
            node.parent.left = temp;
        }
        temp.right = node;
        node.parent = temp;
    }
}

原文地址：https://blog.csdn.net/weixin_74521994/article/details/137838726

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Rx.Net 第三章 linq介绍
下一篇：【力扣】45. 跳跃游戏 II

Neko一个在Docker环境下的虚拟浏览器
Neko是一个在 Docker 中运行并使用 WebRTC 技术的自托管虚拟浏览器。Neko 是一个强大的工具，可让您在虚拟环境中运行功能齐全的浏览器，使您能够从任何地方安全、私密地访问互联网。使用
阅读更多2024-09-21
《华为交换机堆叠配置》
2. 提高可靠性：如果其中一台交换机出现故障，堆叠系统中的其他交换机可以继续工作，不会导致整个网络中断，从而提高了网络的可靠性。在进行华为交换机堆叠时，需要注意交换机的型号是否支持堆叠、堆叠线缆的连接
阅读更多2024-09-21
OpenLayers 开源的Web GIS引擎 - 地图初始化
坐标系转换： EPSG:3857 和 EPSG:4326 坐标系相互转换。
阅读更多2024-09-21
【PSINS工具箱】仅速度为观测量的SINS/GNSS组合导航，MATLAB源代码，无需下载，可直接复制
本程序需要在安装工具箱后使用，工具箱是开源的，链接：http://www.psins.org.cn/kydm。
阅读更多2024-09-21
从零开始学习Linux（13）---多线程
pthread_create是 POSIX 线程（pthread）库中的一个函数，用于在 POSIX 兼容的操作系统中创建新的线程。地址空间是计算机内存管理中的一个基本概念，它指的是一个程序在运行时可
阅读更多2024-09-21
Pytest-allure如何在测试完成后自动生成完整报告？
Pytest-allure如何在测试完成后自动生成完整报告？
阅读更多2024-09-21
【秋招笔试-支持在线评测】0919华为秋招(已改编)-三语言题解
在一个网络监控系统中，K小姐负责定期检查网络的健康状态。每当重要节日来临，K小姐需要对网络中的各个设备进行数据采集，并根据预设的判断条件来判断网络是否健康。判断条件以布尔表达式的形式给出，包含不同的字
阅读更多2024-09-21
简单多状态dp第一弹 leetcode -面试题17.16.按摩师 -213.打家劫舍II
简单多状态dp第一弹 leetcode -面试题17.16.按摩师 -213.打家劫舍II
阅读更多2024-09-21
漏洞——CVE简介
漏洞——CVE简介。根据CVE编号查询漏洞，查询特定软件的CVE。
阅读更多2024-09-21
生活小助手系统小程序的设计
管理员账户功能包括：系统首页，个人中心，客户管理，社区公告管理，反馈信息管理，生活缴费处管理，物品分类管理，二手物品管理，系统管理。主要技术：Java,Spring,mybatis,mysql,jqu
阅读更多2024-09-21

Java——二叉树

二叉树

二叉排序树

平衡二叉树

如何保持平衡

代码示例

红黑树

相关文章