IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> Java二叉树 -> 正文阅读

[数据结构与算法]Java二叉树

1.二叉树

????????二叉树是一种递归数据结构,其中每个节点最多可以有 2 个子节点。

????????二叉树的一种常见类型是二叉搜索树,其中每个节点的值都大于或等于左子树中的节点值,并且小于或等于右子树中的节点值树。

这是这种二叉树的直观表示:

?对于实现,我们将使用一个辅助Node类来存储int值,并保留对每个孩子的引用:

class Node {
    int value;
    Node left;
    Node right;
    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

然后我们将添加树的起始节点,通常称为根:

public class BinaryTree {
    Node root;
    // ...
}

2.常用操作

????????现在让我们看看我们可以在二叉树上执行的最常见的操作。

(1)插入元素

????????我们要介绍的第一个操作是插入新节点。

????????首先,我们必须找到要添加新节点的位置,以保持树的排序。我们将从根节点开始遵循这些规则:

????????如果新节点的值小于当前节点的值,我们去左子树

????????如果新节点的值大于当前节点的值,我们去右子树

????????当当前节点为空时,我们到达了一个叶节点,我们可以在该位置插入新节点

????????然后我们将创建一个递归方法来进行插入:

private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }
    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // value already exists
        return current;
    }
    return current;
}

????????接下来我们将创建从根节点开始递归的公共方法:

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

????????让我们看看如何使用此方法从我们的示例中创建树:

private BinaryTree createBinaryTree() {
    BinaryTree bt = new BinaryTree();
    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);
    return bt;
}

(2)寻找元素

????????现在让我们添加一个方法来检查树是否包含特定值。

????????和以前一样,我们将首先创建一个遍历树的递归方法:

private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    } 
    if (value == current.value) {
        return true;
    } 
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

????????在这里,我们通过将其与当前节点中的值进行比较来搜索该值;然后,我们将根据结果继续左或右孩子。

????????接下来,我们将创建从root开始的公共方法:

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

????????然后我们将创建一个简单的测试来验证树是否真的包含插入的元素:

@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
    BinaryTree bt = createBinaryTree();
    assertTrue(bt.containsNode(6));
    assertTrue(bt.containsNode(4)); 
    assertFalse(bt.containsNode(1));
}

????????添加的所有节点都应包含在树中。

(3)删除元素

????????另一种常见的操作是从树中删除一个节点。

????????首先,我们必须以与之前类似的方式找到要删除的节点:

private Node deleteRecursive(Node current, int value) {
    if (current == null) {
        return null;
    }
    if (value == current.value) {
        // Node to delete found
        // ... code to delete the node will go here
    } 
    if (value < current.value) {
        current.left = deleteRecursive(current.left, value);
        return current;
    }
    current.right = deleteRecursive(current.right, value);
    return current;
}

????????一旦我们找到要删除的节点,主要有 3 种不同的情况:

  • 一个节点没有孩子——这是最简单的情况;我们只需要在它的父节点中用null替换这个节点

  • 一个节点只有一个孩子——在父节点中,我们用它唯一的孩子替换这个节点。

  • 一个节点有两个孩子——这是最复杂的情??况,因为它需要树重组

????????让我们看看当节点是叶节点时如何实现第一种情况:

if (current.left == null && current.right == null) {
    return null;
}

????????现在让我们继续讨论节点有一个孩子的情况:

if (current.right == null) {
    return current.left;
}
if (current.left == null) {
    return current.right;
}

????????在这里,我们返回非空子节点,以便将其分配给父节点。

????????最后,我们必须处理节点有两个孩子的情况。

????????首先,我们需要找到将替换已删除节点的节点。我们将使用即将被删除节点的右子树的最小节点:

private int findSmallestValue(Node root) {
    return root.left == null ? root.value : findSmallestValue(root.left);
}

????????然后我们将最小值分配给要删除的节点,然后,我们将从右子树中删除它:

int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;

????????最后,我们将创建从根开始删除的公共方法:

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

????????现在让我们检查删除是否按预期工作:

@Test
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
    BinaryTree bt = createBinaryTree();
    assertTrue(bt.containsNode(9));
    bt.delete(9);
    assertFalse(bt.containsNode(9));
}

Java学习视频

Java基础:

Java300集,Java必备优质视频_手把手图解学习Java,让学习成为一种享受

Java项目:

【Java游戏项目】1小时教你用Java语言做经典扫雷游戏_手把手教你开发游戏

【Java毕业设计】OA办公系统项目实战_OA员工管理系统项目_java开发

?

  数据结构与算法 最新文章
《算法系列》之 数组
Python描述 LeetCode 剑指 Offer II 091. 粉
【八大排序①】插入排序(直接插入排序、希
【恋上数据结构与算法】理论 三: 链表:Li
LeetCode 剑指 Offer II 091.粉刷房子 - 原
2022-06-27 数据结构与算法-递归、冒泡、插
AcWing 848. 有向图的拓扑序列(拓扑排序模
排序算法-C++
C语言求最大公约数
2021.12.09 - SX09-08.跳跃游戏 II
上一篇文章      下一篇文章      查看所有文章
加:2022-05-21 19:13:41  更:2022-05-21 19:16:09 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年6日历 -2022/6/30 16:13:46-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码