姓名: 李小娜
[嵌牛導(dǎo)讀] ：這篇文章主要介紹了Java二叉排序樹排监，包括二叉排序樹的定義狰右、二叉排序樹的性質(zhì)、二叉排序樹的插入和查找等舆床，感興趣的小伙伴們可以參考一下
[嵌牛鼻子]：二叉排序樹定義 ? 二叉排序樹的性質(zhì) ????代碼編寫 ??二叉排序樹的插入 ? ?二叉排序樹的查找 ??二叉排序樹的刪除 ? ?二叉樹的遍歷 ?
[嵌牛提問]：二叉排序樹的性質(zhì)是什么棋蚌？
[嵌牛正文] : ?一、二叉排序樹定義
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)榭眨┕美叮缓笥袃煞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
2咽瓷、二叉排序樹的定義
packagecom.lin;
/**
* 功能概要：排序/平衡二叉樹
*/
publicclassSearchTree {
publicTreeNode root;
publiclongsize;
/**
* 往樹中加節(jié)點(diǎn)
* @param data
* @return Boolean 插入成功返回true
*/
publicBoolean addTreeNode(Integer data) {
if(null== root) {
root =newTreeNode(data);
System.out.println("數(shù)據(jù)成功插入到平衡二叉樹中");
returntrue;
}
TreeNode treeNode =newTreeNode(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++;
returntrue;
}
// 插入的數(shù)據(jù)比父節(jié)點(diǎn)大
}elseif(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++;
returntrue;
}
}else{
System.out.println("輸入數(shù)據(jù)與節(jié)點(diǎn)的數(shù)據(jù)相同");
returnfalse;
}
}
}
/**
* @param data
* @return TreeNode
*/
publicTreeNode findTreeNode(Integer data){
if(null== root){
returnnull;
}
TreeNode current = root;
while(current !=null){
if(current.data > data){
current = current.left;
}elseif(current.data < data){
current = current.right;
}else{
returncurrent;
}
}
returnnull;
}
}
這里暫時(shí)只放了一個(gè)增加和查找的方法
3、前舰讹、中茅姜、后遍歷
packagecom.lin;
importjava.util.Stack;
/**
* 功能概要：
*/
publicclassTreeOrder {
/**
* 遞歸實(shí)現(xiàn)前序遍歷
* @author linbingwen
* @since 2015年8月29日
* @param treeNode
*/
publicstaticvoidpreOrderMethodOne(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
*/
publicstaticvoidpreOrderMethodTwo(TreeNode treeNode) {
if(null!= treeNode) {
Stack stack =newStack();
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
*/
publicstaticvoidmedOrderMethodOne(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
*/
publicstaticvoidmedOrderMethodTwo(TreeNode treeNode){
Stack stack =newStack();
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
*/
publicstaticvoidpostOrderMethodOne(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
*/
publicstaticvoidpostOrderMethodTwo(TreeNode treeNode){
if(null!= treeNode) {
Stack stack =newStack();
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月匣、使用方法
packagecom.lin;
/**
* 功能概要：
*/
publicclassSearchTreeTest {
/**
* @param args
*/
publicstaticvoidmain(String[] args) {
SearchTree tree =newSearchTree();
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)行查找過程如下：
