詳解Java二叉排序樹
一、二叉排序樹定義
1.二叉排序樹的定義
二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹：
①若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；
②若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；
③左、右子樹本身又各是一棵二叉排序樹。
上述性質(zhì)簡稱二叉排序樹性質(zhì)(BST性質(zhì))，故二叉排序樹實(shí)際上是滿足BST性質(zhì)的二叉樹。
2.二叉排序樹的性質(zhì)
按中序遍歷二叉排序樹，所得到的中序遍歷序列是一個(gè)遞增有序序列。
3.二叉排序樹的插入
在二叉排序樹中插入新結(jié)點(diǎn)，要保證插入后的二叉樹仍符合二叉排序樹的定義。
插入過程：
若二叉排序樹為空，則待插入結(jié)點(diǎn)*S作為根結(jié)點(diǎn)插入到空樹中；
當(dāng)非空時(shí)，將待插結(jié)點(diǎn)關(guān)鍵字S->key和樹根關(guān)鍵字t->key進(jìn)行比較，若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，如此進(jìn)行下去，直到把結(jié)點(diǎn)*s作為一個(gè)新的樹葉插入到二叉排序樹中，或者直到發(fā)現(xiàn)樹已有相同關(guān)鍵字的結(jié)點(diǎn)為止。
4.二叉排序樹的查找
假定二叉排序樹的根結(jié)點(diǎn)指針為 root ，給定的關(guān)鍵字值為 K ，則查找算法可描述為：
?、?置初值： q ＝ root ；
② 如果 K ＝ q －＞ key ，則查找成功，算法結(jié)束；
③ 否則，如果 K ＜ q －＞ key ，而且 q 的左子樹非空，則將 q 的左子樹根送 q ，轉(zhuǎn)步驟②；否則，查找失敗，結(jié)束算法；
?、?否則，如果 K ＞ q －＞ key ，而且 q 的右子樹非空，則將 q 的右子樹根送 q ，轉(zhuǎn)步驟②；否則，查找失敗，算法結(jié)束。
5.二叉排序樹的刪除
假設(shè)被刪結(jié)點(diǎn)是*p，其雙親是*f，不失一般性，設(shè)*p是*f的左孩子，下面分三種情況討論：
⑴ 若結(jié)點(diǎn)*p是葉子結(jié)點(diǎn)，則只需修改其雙親結(jié)點(diǎn)*f的指針即可。
⑵ 若結(jié)點(diǎn)*p只有左子樹PL或者只有右子樹PR，則只要使PL或PR 成為其雙親結(jié)點(diǎn)的左子樹即可。
⑶ 若結(jié)點(diǎn)*p的左、右子樹均非空，先找到*p的中序前趨(或后繼)結(jié)點(diǎn)*s（注意*s是*p的左子樹中的最右下的結(jié)點(diǎn)，它的右鏈域?yàn)榭眨?，然后有兩種做法：① 令*p的左子樹直接鏈到*p的雙親結(jié)點(diǎn)*f的左鏈上,而*p的右子樹鏈到*p的中序前趨結(jié)點(diǎn)*s的右鏈上。② 以*p的中序前趨結(jié)點(diǎn)*s代替*p（即把*s的數(shù)據(jù)復(fù)制到*p中），將*s的左子樹鏈到*s的雙親結(jié)點(diǎn)*q的左（或右）鏈上。
6、二叉樹的遍歷
二叉樹的遍歷有三種方式，如下：
（1）前序遍歷（DLR），首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。簡記根-左-右。
（2）中序遍歷（LDR），首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。簡記左-根-右。
（3）后序遍歷（LRD），首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。簡記左-右-根。
二、代碼編寫
1、樹節(jié)點(diǎn)類的定義0
package com.lin;
/**
* 功能概要：
*/
public class TreeNode {
public Integer data;
/*該節(jié)點(diǎn)的父節(jié)點(diǎn)*/
public TreeNode parent;
/*該節(jié)點(diǎn)的左子節(jié)點(diǎn)*/
public TreeNode left;
/*該節(jié)點(diǎn)的右子節(jié)點(diǎn)*/
public TreeNode right;
public TreeNode(Integer data) {
this.data = data;
}
@Override
public String toString() {
return "TreeNode [data=" + data + "]";
}
}
2、二叉排序樹的定義
package com.lin;
/**
* 功能概要：排序/平衡二叉樹
*/
public class SearchTree {
public TreeNode root;
public long size;
/**
* 往樹中加節(jié)點(diǎn)
* @param data
* @return Boolean 插入成功返回true
*/
public Boolean addTreeNode(Integer data) {
if (null == root) {
root = new TreeNode(data);
System.out.println("數(shù)據(jù)成功插入到平衡二叉樹中");
return true;
}
TreeNode treeNode = new TreeNode(data);// 即將被插入的數(shù)據(jù)
TreeNode currentNode = root;
TreeNode parentNode;
while (true) {
parentNode = currentNode;// 保存父節(jié)點(diǎn)
// 插入的數(shù)據(jù)比父節(jié)點(diǎn)小
if (currentNode.data > data) {
currentNode = currentNode.left;
// 當(dāng)前父節(jié)點(diǎn)的左子節(jié)點(diǎn)為空
if (null == currentNode) {
parentNode.left = treeNode;
treeNode.parent = parentNode;
System.out.println("數(shù)據(jù)成功插入到二叉查找樹中");
size++;
return true;
}
// 插入的數(shù)據(jù)比父節(jié)點(diǎn)大
} else if (currentNode.data < data) {
currentNode = currentNode.right;
// 當(dāng)前父節(jié)點(diǎn)的右子節(jié)點(diǎn)為空
if (null == currentNode) {
parentNode.right = treeNode;
treeNode.parent = parentNode;
System.out.println("數(shù)據(jù)成功插入到二叉查找樹中");
size++;
return true;
}
} else {
System.out.println("輸入數(shù)據(jù)與節(jié)點(diǎn)的數(shù)據(jù)相同");
return false;
}
}
}
/**
* @param data
* @return TreeNode
*/
public TreeNode findTreeNode(Integer data){
if(null == root){
return null;
}
TreeNode current = root;
while(current != null){
if(current.data > data){
current = current.left;
}else if(current.data < data){
current = current.right;
}else {
return current;
}
}
return null;
}
}
這里暫時(shí)只放了一個(gè)增加和查找的方法
3、前、中、后遍歷
package com.lin;
import java.util.Stack;
/**
* 功能概要：
*/
public class TreeOrder {
/**
* 遞歸實(shí)現(xiàn)前序遍歷
* @author linbingwen
* @since 2015年8月29日
* @param treeNode
*/
public static void preOrderMethodOne(TreeNode treeNode) {
if (null != treeNode) {
System.out.print(treeNode.data + " ");
if (null != treeNode.left) {
preOrderMethodOne(treeNode.left);
}
if (null != treeNode.right) {
preOrderMethodOne(treeNode.right);
}
}
}
/**
* 循環(huán)實(shí)現(xiàn)前序遍歷
* @param treeNode
*/
public static void preOrderMethodTwo(TreeNode treeNode) {
if (null != treeNode) {
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(treeNode);
while (!stack.isEmpty()) {
TreeNode tempNode = stack.pop();
System.out.print(tempNode.data + " ");
// 右子節(jié)點(diǎn)不為null,先把右子節(jié)點(diǎn)放進(jìn)去
if (null != tempNode.right) {
stack.push(tempNode.right);
}
// 放完右子節(jié)點(diǎn)放左子節(jié)點(diǎn)，下次先取
if (null != tempNode.left) {
stack.push(tempNode.left);
}
}
}
}
/**
* 遞歸實(shí)現(xiàn)中序遍歷
* @param treeNode
*/
public static void medOrderMethodOne(TreeNode treeNode){
if (null != treeNode) {
if (null != treeNode.left) {
medOrderMethodOne(treeNode.left);
}
System.out.print(treeNode.data + " ");
if (null != treeNode.right) {
medOrderMethodOne(treeNode.right);
}
}
}
/**
* 循環(huán)實(shí)現(xiàn)中序遍歷
* @param treeNode
*/
public static void medOrderMethodTwo(TreeNode treeNode){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = treeNode;
while (current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.left;
}
if (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.data+" ");
current = current.right;
}
}
}
/**
* 遞歸實(shí)現(xiàn)后序遍歷
* @param treeNode
*/
public static void postOrderMethodOne(TreeNode treeNode){
if (null != treeNode) {
if (null != treeNode.left) {
postOrderMethodOne(treeNode.left);
}
if (null != treeNode.right) {
postOrderMethodOne(treeNode.right);
}
System.out.print(treeNode.data + " ");
}
}
/**
* 循環(huán)實(shí)現(xiàn)后序遍歷
* @param treeNode
*/
public static void postOrderMethodTwo(TreeNode treeNode){
if (null != treeNode) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = treeNode;
TreeNode rightNode = null;
while(current != null || !stack.isEmpty()) {
while(current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
while (current != null && (current.right == null ||current.right == rightNode)) {
System.out.print(current.data + " ");
rightNode = current;
if (stack.isEmpty()){
System.out.println();
return;
}
current = stack.pop();
}
stack.push(current);
current = current.right;
}
}
}
}
4、使用方法
package com.lin;
/**
* 功能概要：
*/
public class SearchTreeTest {
/**
* @param args
*/
public static void main(String[] args) {
SearchTree tree = new SearchTree();
tree.addTreeNode(50);
tree.addTreeNode(80);
tree.addTreeNode(20);
tree.addTreeNode(60);
tree.addTreeNode(10);
tree.addTreeNode(30);
tree.addTreeNode(70);
tree.addTreeNode(90);
tree.addTreeNode(100);
tree.addTreeNode(40);
System.out.println("=============================="+"采用遞歸的前序遍歷開始"+"==============================");
TreeOrder.preOrderMethodOne(tree.root);
System.out.println();
System.out.println("=============================="+"采用循環(huán)的前序遍歷開始"+"==============================");
TreeOrder.preOrderMethodTwo(tree.root);
System.out.println();
System.out.println("=============================="+"采用遞歸的后序遍歷開始"+"==============================");
TreeOrder.postOrderMethodOne(tree.root);
System.out.println();
System.out.println("=============================="+"采用循環(huán)的后序遍歷開始"+"==============================");
TreeOrder.postOrderMethodTwo(tree.root);
System.out.println();
System.out.println("=============================="+"采用遞歸的中序遍歷開始"+"==============================");
TreeOrder.medOrderMethodOne(tree.root);
System.out.println();
System.out.println("=============================="+"采用循環(huán)的中序遍歷開始"+"==============================");
TreeOrder.medOrderMethodTwo(tree.root);
}
}
輸出結(jié)果：
同樣，進(jìn)行查找過程如下：
TreeNode node = tree.findTreeNode(100); System.out.println(node);
結(jié)果是正確的
以上就是關(guān)于Java二叉排序樹的詳細(xì)介紹，希望對(duì)大家的學(xué)習(xí)java程序設(shè)計(jì)有所幫助。
- Java二叉搜索樹遍歷操作詳解【前序、中序、后序、層次、廣度優(yōu)先遍歷】
- Java二叉搜索樹基礎(chǔ)原理與實(shí)現(xiàn)方法詳解
- java實(shí)現(xiàn) 二叉搜索樹功能
- Java創(chuàng)建二叉搜索樹,實(shí)現(xiàn)搜索,插入,刪除的操作實(shí)例
- Java 實(shí)現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷
- java使用歸并刪除法刪除二叉樹中節(jié)點(diǎn)的方法
- 圖解二叉樹的三種遍歷方式及java實(shí)現(xiàn)代碼
- Java中二叉樹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)示例
- java實(shí)現(xiàn)二叉樹的創(chuàng)建及5種遍歷方法(總結(jié))
- Java實(shí)現(xiàn)二叉樹的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法示例
- Java實(shí)現(xiàn)求二叉樹的深度和寬度
- Java刪除二叉搜索樹最大元素和最小元素的方法詳解
相關(guān)文章
SpringBoot中Filter?bean如何添加到Servlet容器
這篇文章主要介紹了SpringBoot中Filter bean是怎么被添加到Servlet容器中的,本文分步驟結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了Java獲取文件夾下所有文件名稱的方法,涉及java針對(duì)文件與目錄相關(guān)操作技巧,需要的朋友可以參考下2017-06-06
這篇文章主要介紹了深入淺出講解Java集合之Map接口，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
IDEA 2020.2 部署JSF項(xiàng)目的詳細(xì)過程
本文通過圖文并茂的形式教大家如何在IDEA中創(chuàng)建一個(gè)JSF項(xiàng)目及遇到問題的解決方法，感興趣的朋友跟隨小編一起看看吧2021-09-09
Sentinel是阿里巴巴開源的一款微服務(wù)流量控制組件,主要以流量為切入點(diǎn),從流量路由、流量控制、流量整形、熔斷降級(jí)、系統(tǒng)自適應(yīng)過載保護(hù)、熱點(diǎn)流量防護(hù)等多個(gè)維度來幫助開發(fā)者保障微服務(wù)的穩(wěn)定性,本文介紹Sentinel 斷路器在Spring Cloud使用,感興趣的朋友一起看看吧2025-02-02
深入淺析Java中Static Class及靜態(tài)內(nèi)部類和非靜態(tài)內(nèi)部類的不同
上次有朋友問我，java中的類可以是static嗎？我給他肯定的回答是可以的，在java中我們可以有靜態(tài)實(shí)例變量、靜態(tài)方法、靜態(tài)塊。當(dāng)然類也可以是靜態(tài)的，下面小編整理了些關(guān)于java中的static class相關(guān)資料分享在腳本之家平臺(tái)供大家參考2015-11-11
SpringCloud服務(wù)的發(fā)現(xiàn)與調(diào)用詳解
在Java微服務(wù)越來越火的今天。幾乎什么公司都在搞微服務(wù)。而使用的比較多的就是Spring?Cloud技術(shù)棧。今天就來研究一下Spring?Cloud中服務(wù)發(fā)現(xiàn)與調(diào)用的基本原理2022-07-07
基于@PostConstruct注解的使用,解決向靜態(tài)變量注入值
這篇文章主要介紹了基于@PostConstruct注解的使用，解決向靜態(tài)變量注入值問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了Java中的日期類的相關(guān)資料，幫助大家更好的利用Java處理時(shí)間，感興趣的朋友可以了解下2020-10-10
Java中哈希表(Hashtable)是如何實(shí)現(xiàn)的呢？Hashtable中有一個(gè)內(nèi)部類Entry，用來保存單元數(shù)據(jù)，我們用來構(gòu)建哈希表的每一個(gè)數(shù)據(jù)是Entry的一個(gè)實(shí)例。假設(shè)我們保存下面一組數(shù)據(jù)，第一列作為key, 第二列作為value。2015-06-06