成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

Java如何利用二叉搜索樹實現(xiàn)查找、插入、刪除、遍歷

這篇文章將為大家詳細講解有關Java 如何利用二叉搜索樹實現(xiàn)查找、插入、刪除、遍歷，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關知識有一定的了解。

創(chuàng)新互聯(lián)是一家專業(yè)提供莘縣企業(yè)網(wǎng)站建設,專注與做網(wǎng)站、成都網(wǎng)站制作、HTML5建站、小程序制作等業(yè)務。10年已為莘縣眾多企業(yè)、政府機構(gòu)等服務。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設計公司優(yōu)惠進行中。

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

學習紅黑樹，我覺得有必要從二叉搜索樹開始學起，本篇隨筆就主要介紹Java實現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷等內(nèi)容。

二叉搜索樹需滿足以下四個條件：

若任意節(jié)點的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；

若任意節(jié)點的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；

任意節(jié)點的左、右子樹也分別為二叉查找樹；

沒有鍵值相等的節(jié)點。

二叉搜索樹舉例：

Java 如何利用二叉搜索樹實現(xiàn)查找、插入、刪除、遍歷

圖一

接下來將基于圖一介紹二叉搜索樹相關操作。

首先，應先有一個節(jié)點對象相關的類，命名為 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 值，用于確定節(jié)點在樹中相應位置，value 值代表要存儲的內(nèi)容，還含有指向左右孩子節(jié)點的兩個引用。

接下來看下搜索樹相應的類：

class Tree {
 Node root;//保存樹的根
 public Node find(int key) {//查找指定節(jié)點
 }
 public void insert(int key, int value) {//插入節(jié)點
 }
 public boolean delete(int key) {//刪除指定節(jié)點
 }
 private Node getDirectPostNode(Node delNode) {//得到待刪除節(jié)點的直接后繼節(jié)點
 }
 public void preOrder(Node rootNode) {//先序遍歷樹
 }
 public void inOrder(Node rootNode) {//中序遍歷樹
 }
 public void postOrder(Node rootNode) {//后序遍歷樹
 }
}

類中表示樹的框架，包含查找、插入、遍歷、刪除相應方法，其中刪除節(jié)點操作最為復雜，接下來一一介紹。

一、查找某個節(jié)點

由于二叉搜索樹定義上的特殊性，只需根據(jù)輸入的 key 值從根開始進行比較，若小于根的 key 值，則與根的左子樹比較，大于根的key值與根的右子樹比較，以此類推，找到則返回相應節(jié)點，否則返回 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;
}

二、插入節(jié)點

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

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);
 }
 }

四、刪除指定節(jié)點。

在二叉搜索樹中刪除節(jié)點操作較復雜，可分為以下三種情況。

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

public boolean delete(int key) {
 Node currentNode = root;//用來保存待刪除節(jié)點
 Node parentNode = root;//用來保存待刪除節(jié)點的父親節(jié)點
 boolean isLeftChild = true;//用來確定待刪除節(jié)點是父親節(jié)點的左孩子還是右孩子
 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) {//要刪除的節(jié)點為葉子節(jié)點
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } 
 ......
 }

2、待刪除節(jié)點只有一個孩子節(jié)點

例如刪除圖一中的 key 值為 11 的節(jié)點，只需將 key 值為 13 的節(jié)點的左孩子指向 key 值為 12的節(jié)點即可達到刪除 key 值為 11 的節(jié)點的目的。

由以上分析可得代碼如下（接上述 delete 方法省略號后）：

else if (currentNode.rightChild == null) {//要刪除的節(jié)點只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要刪除的節(jié)點只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } 
 ......

3、待刪除節(jié)點既有左孩子，又有右孩子。

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

所以刪除 圖一中 key 值為 10 的節(jié)點分為以下幾步：

a、找到 key 值為 10 的節(jié)點的直接中序后繼節(jié)點（即其右子樹中值最小的節(jié)點 11），并刪除此直接中序后繼節(jié)點。

private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節(jié)點的直接后繼節(jié)點
 Node parentNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點的父親節(jié)點
 Node direcrPostNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節(jié)點
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后繼節(jié)點
}

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

else { //要刪除的節(jié)點既有左孩子又有右孩子
 //思路：用待刪除節(jié)點右子樹中的key值最小節(jié)點的值來替代要刪除的節(jié)點的值,然后刪除右子樹中key值最小的節(jié)點
 //右子樹key最小的節(jié)點一定不含左子樹,所以刪除這個key最小的節(jié)點一定是屬于葉子節(jié)點或者只有右子樹的節(jié)點
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
}

至此刪除指定節(jié)點的操作結(jié)束。

最后給出完整代碼及簡單測試代碼及測試結(jié)果：

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) {
 //要刪除的節(jié)點為葉子節(jié)點
 if (currentNode == root)
 root = null;
 else if (isLeftChild)
 parentNode.leftChild = null;
 else
 parentNode.rightChild = null;
 } else if (currentNode.rightChild == null) {//要刪除的節(jié)點只有左孩子
 if (currentNode == root)
 root = currentNode.leftChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.leftChild;
 else
 parentNode.rightChild = currentNode.leftChild;
 } else if (currentNode.leftChild == null) {//要刪除的節(jié)點只有右孩子
 if (currentNode == root)
 root = currentNode.rightChild;
 else if (isLeftChild)
 parentNode.leftChild = currentNode.rightChild;
 else
 parentNode.rightChild = currentNode.rightChild;
 } else { //要刪除的節(jié)點既有左孩子又有右孩子
 //思路：用待刪除節(jié)點右子樹中的key值最小節(jié)點的值來替代要刪除的節(jié)點的值,然后刪除右子樹中key值最小的節(jié)點
 //右子樹key最小的節(jié)點一定不含左子樹,所以刪除這個key最小的節(jié)點一定是屬于葉子節(jié)點或者只有右子樹的節(jié)點
 Node directPostNode = getDirectPostNode(currentNode);
 currentNode.key = directPostNode.key;
 currentNode.value = directPostNode.value;
 }
 return true;
 }
 private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節(jié)點的直接后繼節(jié)點
 Node parentNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點的父親節(jié)點
 Node direcrPostNode = delNode;//用來保存待刪除節(jié)點的直接后繼節(jié)點
 Node currentNode = delNode.rightChild;
 while (currentNode != null) {
 parentNode = direcrPostNode;
 direcrPostNode = currentNode;
 currentNode = currentNode.leftChild;
 }
 if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節(jié)點
 parentNode.leftChild = direcrPostNode.rightChild;
 direcrPostNode.rightChild = null;
 }
 return direcrPostNode;//返回此直接后繼節(jié)點
 }
 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);//插入操作,構(gòu)造圖一所示的二叉樹
 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("刪除前遍歷結(jié)果");
 tree.inOrder(tree.root);//中序遍歷操作
 System.out.println("刪除節(jié)點10之后遍歷結(jié)果");
 tree.delete(10);//刪除操作
 tree.inOrder(tree.root);
 }
}

測試結(jié)果：

Java 如何利用二叉搜索樹實現(xiàn)查找、插入、刪除、遍歷

關于Java 如何利用二叉搜索樹實現(xiàn)查找、插入、刪除、遍歷就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。

當前標題：Java如何利用二叉搜索樹實現(xiàn)查找、插入、刪除、遍歷
文章起源：http://jinyejixie.com/article26/iihijg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供做網(wǎng)站、網(wǎng)站設計、微信小程序、網(wǎng)站導航、建站公司、

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

商城網(wǎng)站建設
永年县| 兴安县| 肇州县| 广宁县| 富川| 通渭县| 皋兰县| 彝良县| 苗栗县| 麻江县| 雅江县| 靖江市| 申扎县| 莱阳市| 玛曲县| 龙里县| 壶关县| 兖州市| 锦州市| 广丰县| 长阳| 洛宁县| 晴隆县| 澳门| 平远县| 邯郸市| 元氏县| 南涧| 阿荣旗| 唐海县| 永年县| 卓尼县| 富顺县| 余庆县| 河池市| 西平县| 盘山县| 清苑县| 察雅县| 大石桥市| 保定市|