用Java實現二叉樹

1.簡介

在本文中,我們將介紹Java中二叉樹的實現。

為了本文的方便,我們將使用包含int值的排序二叉樹

進一步閱讀:

如何打印二叉樹圖

了解如何打印二叉樹圖。

閱讀更多→

反轉Java中的二叉樹

快速實用的指南,介紹如何用Java反轉二叉樹。

閱讀更多→

Java深度優先搜索

Java的深度優先搜索算法指南,同時使用Tree和Graph數據結構。

閱讀更多→

2.二叉樹

二叉樹是一種遞歸數據結構,其中每個節點最多可以有2個子節點。

二進制搜索樹的一種常見類型是二進制搜索樹,其中每個節點的值都大於或等於左子樹中的節點值,並且小於或等於右子樹中的節點值。樹。

這是這種類型的二叉樹的快速直觀表示:

用Java實現二叉樹

對於實現,我們將使用輔助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 6

4.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 9

5.結論

在本文中,我們已經看到瞭如何在Java中實現排序的二叉樹及其最常見的操作。

示例的完整源代碼可在GitHub上獲得