詳解Java二叉排序樹。本站提示廣大學習愛好者：（詳解Java二叉排序樹）文章只能為提供參考，不一定能成為您想要的結果。以下是詳解Java二叉排序樹正文
1、二叉排序樹界說
1.二叉排序樹的界說
二叉排序樹(Binary Sort Tree)又稱二叉查找(搜刮)樹(Binary Search Tree)。其界說為：二叉排序樹或許是空樹，或許是知足以下性質的二叉樹：
①若它的左子樹非空，則左子樹上一切結點的值均小於根結點的值；
②若它的右子樹非空，則右子樹上一切結點的值均年夜於根結點的值；
③左、右子樹自己又各是一棵二叉排序樹。
上述性質簡稱二叉排序樹性質(BST性質)，故二叉排序樹現實上是知足BST性質的二叉樹。
2.二叉排序樹的性質
按中序遍歷二叉排序樹，所獲得的中序遍歷序列是一個遞增有序序列。
3.二叉排序樹的拔出
在二叉排序樹中拔出新結點，要包管拔出後的二叉樹仍相符二叉排序樹的界說。
拔出進程：
若二叉排序樹為空，則待拔出結點*S作為根結點拔出到空樹中；
當非空時，將待插結點症結字S->key和樹根症結字t->key停止比擬，若s->key = t->key,則不必拔出，若s->key< t->key,則拔出到根的左子樹中，若s->key> t->key,則拔出到根的右子樹中。而子樹中的拔出進程和在樹中的拔出進程雷同，如斯停止下去，直到把結點*s作為一個新的樹葉拔出到二叉排序樹中，或許直到發明樹已有雷同症結字的結點為止。
4.二叉排序樹的查找
假定二叉排序樹的根結點指針為 root ，給定的症結字值為 K ，則查找算法可描寫為：
① 置初值： q ＝ root ；
② 假如 K ＝ q －＞ key ，則查找勝利，算法停止；
③ 不然，假如 K ＜ q －＞ key ，並且 q 的左子樹非空，則將 q 的左子樹根送 q ，轉步調②；不然，查找掉敗，停止算法；
④ 不然，假如 K ＞ q －＞ key ，並且 q 的右子樹非空，則將 q 的右子樹根送 q ，轉步調②；不然，查找掉敗，算法停止。
5.二叉排序樹的刪除
假定被刪結點是*p，其雙親是*f，不掉普通性，設*p是*f的左孩子，上面分三種情形評論辯論：
⑴ 若結點*p是葉子結點，則只需修正其雙親結點*f的指針便可。
⑵ 若結點*p只要左子樹PL或許只要右子樹PR，則只需使PL或PR 成為其雙親結點的左子樹便可。
⑶ 若結點*p的左、右子樹均非空，先找到*p的中序前趨(或後繼)結點*s（留意*s是*p的左子樹中的最右下的結點，它的右鏈域為空），然後有兩種做法：① 令*p的左子樹直接鏈到*p的雙親結點*f的左鏈上,而*p的右子樹鏈到*p的中序前趨結點*s的右鏈上。② 以*p的中序前趨結點*s取代*p（即把*s的數據復制到*p中），將*s的左子樹鏈到*s的雙親結點*q的左（或右）鏈上。
6、二叉樹的遍歷
二叉樹的遍歷有三種方法，以下：
（1）前序遍歷（DLR），起首拜訪根結點，然後遍歷左子樹，最初遍歷右子樹。簡記根-左-右。
（2）中序遍歷（LDR），起首遍歷左子樹，然後拜訪根結點，最初遍歷右子樹。簡記左-根-右。
（3）後序遍歷（LRD），起首遍歷左子樹，然後遍歷右子樹，最初拜訪根結點。簡記左-右-根。
2、代碼編寫
1、樹節點類的界說0
package com.lin;
/**
* 功效概要：
*/
public class TreeNode {
public Integer data;
/*該節點的父節點*/
public TreeNode parent;
/*該節點的左子節點*/
public TreeNode left;
/*該節點的右子節點*/
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;
/**
* 往樹中加節點
* @param data
* @return Boolean 拔出勝利前往true
*/
public Boolean addTreeNode(Integer data) {
if (null == root) {
root = new TreeNode(data);
System.out.println("數據勝利拔出到均衡二叉樹中");
return true;
}
TreeNode treeNode = new TreeNode(data);// 行將被拔出的數據
TreeNode currentNode = root;
TreeNode parentNode;
while (true) {
parentNode = currentNode;// 保留父節點
// 拔出的數據比父節點小
if (currentNode.data > data) {
currentNode = currentNode.left;
// 以後父節點的左子節點為空
if (null == currentNode) {
parentNode.left = treeNode;
treeNode.parent = parentNode;
System.out.println("數據勝利拔出到二叉查找樹中");
size++;
return true;
}
// 拔出的數據比父節點年夜
} else if (currentNode.data < data) {
currentNode = currentNode.right;
// 以後父節點的右子節點為空
if (null == currentNode) {
parentNode.right = treeNode;
treeNode.parent = parentNode;
System.out.println("數據勝利拔出到二叉查找樹中");
size++;
return true;
}
} else {
System.out.println("輸出數據與節點的數據雷同");
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;
}
}
這裡臨時只放了一個增長和查找的辦法
3、前、中、後遍歷
package com.lin;
import java.util.Stack;
/**
* 功效概要：
*/
public class TreeOrder {
/**
* 遞歸完成前序遍歷
* @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);
}
}
}
/**
* 輪回完成前序遍歷
* @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 + " ");
// 右子節點不為null,先把右子節點放出來
if (null != tempNode.right) {
stack.push(tempNode.right);
}
// 放完右子節點放左子節點，下次先取
if (null != tempNode.left) {
stack.push(tempNode.left);
}
}
}
}
/**
* 遞歸完成中序遍歷
* @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);
}
}
}
/**
* 輪回完成中序遍歷
* @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;
}
}
}
/**
* 遞歸完成後序遍歷
* @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 + " ");
}
}
/**
* 輪回完成後序遍歷
* @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("=============================="+"采取輪回的前序遍歷開端"+"==============================");
TreeOrder.preOrderMethodTwo(tree.root);
System.out.println();
System.out.println("=============================="+"采取遞歸的後序遍歷開端"+"==============================");
TreeOrder.postOrderMethodOne(tree.root);
System.out.println();
System.out.println("=============================="+"采取輪回的後序遍歷開端"+"==============================");
TreeOrder.postOrderMethodTwo(tree.root);
System.out.println();
System.out.println("=============================="+"采取遞歸的中序遍歷開端"+"==============================");
TreeOrder.medOrderMethodOne(tree.root);
System.out.println();
System.out.println("=============================="+"采取輪回的中序遍歷開端"+"==============================");
TreeOrder.medOrderMethodTwo(tree.root);
}
}
輸入成果：
異樣，停止查找進程以下：
TreeNode node = tree.findTreeNode(100); System.out.println(node);
成果是准確的
以上就是關於Java二叉排序樹的具體引見，願望對年夜家的進修java法式設計有所贊助。
