姓名: 李小娜

[嵌牛導(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ì)

按中序遍歷二叉排序樹，所得到的中序遍歷序列是一個遞增有序序列。

3.二叉排序樹的插入

在二叉排序樹中插入新結(jié)點(diǎn)，要保證插入后的二叉樹仍符合二叉排序樹的定義。

插入過程：

若二叉排序樹為空，則待插入結(jié)點(diǎn)*S作為根結(jié)點(diǎn)插入到空樹中；

當(dāng)非空時，將待插結(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作為一個新的樹葉插入到二叉排序樹中，或者直到發(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

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;

}

}

這里暫時只放了一個增加和查找的方法

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)行查找過程如下：