用Java實現二叉樹
1.簡介
在本文中，我們將介紹Java中二叉樹的實現。
為了本文的方便，我們將使用包含int值的排序二叉樹。
進一步閱讀：
如何打印二叉樹圖
了解如何打印二叉樹圖。
閱讀更多→
反轉Java中的二叉樹
快速實用的指南，介紹如何用Java反轉二叉樹。
閱讀更多→
Java深度優先搜索
Java的深度優先搜索算法指南，同時使用Tree和Graph數據結構。
閱讀更多→
2.二叉樹
二叉樹是一種遞歸數據結構，其中每個節點最多可以有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;
// ...
}3.常用操作
現在，讓我們看看可以對二叉樹執行的最常見的操作。
3.1。插入元素
我們要介紹的第一個操作是插入新節點。
首先，我們必須找到要添加新節點的位置，以使樹保持排序。我們將從根節點開始遵循以下規則：
- 如果新節點的值小於當前節點的值，我們轉到左子節點
- 如果新節點的值大於當前節點的值，則轉到正確的子節點
- 噹噹前節點為null時，我們到達了葉節點，我們可以在該位置插入新節點
首先，我們將創建一個遞歸方法來執行插入操作：
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方法：
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;
}3.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方法：
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.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;
}在這裡，我們將返回非null子節點，以便可以將其分配給父節點。
最後，我們必須處理節點有兩個孩子的情況。
首先，我們需要找到將替換已刪除節點的節點。我們將使用要刪除的節點的最小子節點的右子樹：
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));
}4.穿越樹
在本節中，我們將看到遍歷樹的不同方式，詳細介紹了深度優先搜索和寬度優先搜索。
我們將使用之前使用的同一棵樹，並顯示每種情況的遍歷順序。
4.1。深度優先搜索
深度優先搜索是一種遍歷類型，在探索下一個同級對象之前，它會在每個孩子中盡可能深入。
進行深度優先搜索的方法有多種：按順序，按順序和按順序進行。
按順序遍歷包括首先訪問左子樹，然後訪問根節點，最後是右子樹：
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
System.out.print(" " + node.value);
traverseInOrder(node.right);
}
}如果調用此方法，則控制台輸出將顯示有序遍歷：
3 4 5 6 7 8 9預遍歷首先訪問根節點，然後訪問左子樹，最後訪問右子樹：
public void traversePreOrder(Node node) {
if (node != null) {
System.out.print(" " + node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}讓我們檢查控制台輸出中的預訂遍歷：
6 4 3 5 8 7 9順序遍歷訪問左子樹，右子樹和末尾的根節點：
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
System.out.print(" " + node.value);
}
}以下是訂購後的節點：
3 5 4 7 9 8 64.2。廣度優先搜索
這是另一種遍歷類型，它遍歷一個級別的所有節點然後再進入下一個級別。
這種遍歷也稱為級別順序，它從根開始，從左到右訪問樹的所有級別。
對於實現，我們將使用隊列按順序保存每個級別的節點。我們將從列表中提取每個節點，打印其值，然後將其子級添加到隊列中：
public void traverseLevelOrder() {
if (root == null) {
return;
}
Queue<Node> nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
Node node = nodes.remove();
System.out.print(" " + node.value);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
}
}
}在這種情況下，節點的順序為：
6 4 8 3 5 7 95.結論
在本文中，我們已經看到瞭如何在Java中實現排序的二叉樹及其最常見的操作。
示例的完整源代碼可在GitHub上獲得。