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 existsreturn 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);}
然后我们将创建一个简单的测试来验证树是否真的包含插入的元素：
@Testpublic 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.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);}
现在让我们检查删除是否按预期工作：
@Testpublic 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开发
暂无评论数据