Java 實作二元搜尋樹的尋找、插入、刪除、遍歷的圖文詳情

本文主要介紹了Java實作二元搜尋樹的尋找、插入、刪除、遍歷等內容。具有很好的參考價值，下面跟著小編一起來看下吧

由於最近想要閱讀下JDK1.8 中HashMap的具體實現，但是由於HashMap的實現中用到了紅黑樹，所以我覺得有必要先複習下紅黑樹的相關知識，所以寫下這篇隨筆備忘，有不對的地方請指出～

學習紅黑樹，我覺得有必要從二元搜尋樹開始學起，本篇隨筆就主要介紹Java實作二元搜尋樹的尋找、插入、刪除、遍歷等內容。

二元搜尋樹需滿足以下四個條件：

若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

若任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

任意節點的左、右子樹也分別為二元查找樹；

沒有鍵值相等的節點。

二元搜尋樹範例：

#圖一

圖一

接下來將基於圖一介紹二元搜尋樹相關操作。

首先，應先有一個節點物件相關的類，命名為 Node。

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}

Node 類別中包含key 值，用於確定節點在樹中對應位置，value 值代表要儲存的內容，也包含指向左右孩子節點的兩個引用。

接下來看下搜尋樹對應的類別：

class Tree {
 Node root;//保存树的根
 public Node find(int key) {//查找指定节点
 }
 public void insert(int key, int value) {//插入节点
 }
 public boolean delete(int key) {//删除指定节点
 }
 private Node getDirectPostNode(Node delNode) {//得到待删除节点的直接后继节点
 }
 public void preOrder(Node rootNode) {//先序遍历树
 }
 public void inOrder(Node rootNode) {//中序遍历树
 }
 public void postOrder(Node rootNode) {//后序遍历树
 }
}

#類別中表示樹的框架，包含尋找、插入、遍歷、刪除對應方法，其中刪除節點操作最為複雜，接下來一一介紹。

一、尋找某個節點

由於二元搜尋樹定義上的特殊性，只需根據輸入的key 值從根開始進行比較，若小於根的key 值，則與根的左子樹比較，大於根的key值與根的右子樹比較，以此類推，找到則返回相應節點，否則返回null。

public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
}

二、插入節點

與查找操作相似，由於二元搜尋樹的特殊性，待插入的節點也需要從根節點開始進行比較，小於根節點則與根節點左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應為空的位置，在比較的過程中要注意保存父節點的資訊及待插入的位置是父節點的左子樹還是右子樹，才能插入到正確的位置。

public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
}

三、遍歷二元搜尋樹

遍歷操作與遍歷普通二元樹運算完全相同，不贅述。

public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }

#四、刪除指定節點。

在二元搜尋樹中刪除節點操作較為複雜，可分為以下三種情況。

1、待刪除的節點為葉子節點，可直接刪除。

public boolean delete(int key) {
 Node currentNode = root;//用来保存待删除节点
 Node parentNode = root;//用来保存待删除节点的父亲节点
 boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } 
 ......
 }

#2、待刪除節點只有一個孩子節點

例如刪除圖一中的key 值為11 的節點，只需將key 值為13 的節點的左孩子指向key 值為12的節點即可達到刪除key 值為11 的節點的目的。 由上述分析可得程式碼如下（接上述delete 方法省略號後）：

#

else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } 
 ......

##3、待刪除節點既有左孩子，又有右孩子。

例如刪除圖一中key 值為10 的節點，這時就需要用key 值為10 的節點的中序後繼節點（節點11）來取代key 值為10的節點，並刪除key 值為10 的節點的中序後繼節點，由中序遍歷相關規則可知， key 值為10 的節點的直接中序後繼節點一定是其右子樹中key 值最小的節點，所以此中序後繼節點一定不含子節點或只含有一個右孩子，刪除此中序後繼節點就屬於上述1,2 所述情況。圖一中 key 值為 10 的節點的直接中序後繼節點 為 11，節點 11 含有一個右孩子 12。

所以刪除圖一中key 值為10 的節點分成以下幾步：

a、找到key 值為10 的節點的直接中序後繼節點（即其右子樹中值最小的節點11），並刪除此直接中序後繼節點。

private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
}

#b、將此後繼節點的key、value 值賦給待刪除節點的key， value值。 (接情況二中省略號代碼之後)

else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

#至此刪除指定節點的操作結束。 ######最後給出完整程式碼及簡單測試程式碼及測試結果：#########

class Node {
 int key;
 int value;
 Node leftChild;
 Node rightChild;
 public Node(int key, int value) {
 this.key = key;
 this.value = value;
 }
 public void displayNode() {
 }
}
class Tree {
 Node root;
 public Node find(int key) {
 Node currentNode = root;
 while (currentNode != null && currentNode.key != key) {
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 } else {
 currentNode = currentNode.rightChild;
 }
 }
 return currentNode;
 }
 public void insert(int key, int value) {
 if (root == null) {
 root = new Node(key, value);
 return;
 }
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 Node newNode = new Node(key, value);
 if (isLeftChild) {
 parentNode.leftChild = newNode;
 } else {
 parentNode.rightChild = newNode;
 }
 }
 public boolean delete(int key) {
 Node currentNode = root;
 Node parentNode = root;
 boolean isLeftChild = true;
 while (currentNode != null && currentNode.key != key) {
 parentNode = currentNode;
 if (key < currentNode.key) {
 currentNode = currentNode.leftChild;
 isLeftChild = true;
 } else {
 currentNode = currentNode.rightChild;
 isLeftChild = false;
 }
 }
 if (currentNode == null) {
 return false;
 }
 if (currentNode.leftChild == null && currentNode.rightChild == null) {
 //要删除的节点为叶子节点
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } else { //要删除的节点既有左孩子又有右孩子
 //思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
 //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
 }
 return true;
 }
 private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
 Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
 Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后继节点
 }
 public void preOrder(Node rootNode) {
 if (rootNode != null) {
 System.out.println(rootNode.key + " " + rootNode.value);
 preOrder(rootNode.leftChild);
 preOrder(rootNode.rightChild);
 }
 }
 public void inOrder(Node rootNode) {
 if (rootNode != null) {
 inOrder(rootNode.leftChild);
 System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
 inOrder(rootNode.rightChild);
 }
 }
 public void postOrder(Node rootNode) {
 if (rootNode != null) {
 postOrder(rootNode.leftChild);
 postOrder(rootNode.rightChild);
 System.out.println(rootNode.key + " " + rootNode.value);
 }
 }
}
public class BinarySearchTreeApp {
 public static void main(String[] args) {
 Tree tree = new Tree();
 tree.insert(6, 6);//插入操作,构造图一所示的二叉树
 tree.insert(3, 3);
 tree.insert(14, 14);
 tree.insert(16, 16);
 tree.insert(10, 10);
 tree.insert(9, 9);
 tree.insert(13, 13);
 tree.insert(11, 11);
 tree.insert(12, 12);
 System.out.println("删除前遍历结果");
 tree.inOrder(tree.root);//中序遍历操作
 System.out.println("删除节点10之后遍历结果");
 tree.delete(10);//删除操作
 tree.inOrder(tree.root);
 }
}

######

測試結果：

 以上就是Java 實作二元搜尋樹的尋找、插入、刪除、遍歷的圖文詳情的內容，更多相關內容請關注PHP中文網（www.php.cn）！

#