一、二叉排序樹(shù)定義
1.二叉排序樹(shù)的定義
二叉排序樹(shù)(Binary Sort Tree)又稱(chēng)二叉查找(搜索)樹(shù)(Binary Search Tree)。其定義為：二叉排序樹(shù)或者是空樹(shù)，或者是滿(mǎn)足如下性質(zhì)的二叉樹(shù)：
①若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；
②若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；
③左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。
上述性質(zhì)簡(jiǎn)稱(chēng)二叉排序樹(shù)性質(zhì)(BST性質(zhì))，故二叉排序樹(shù)實(shí)際上是滿(mǎn)足BST性質(zhì)的二叉樹(shù)。
2.二叉排序樹(shù)的性質(zhì)
按中序遍歷二叉排序樹(shù)，所得到的中序遍歷序列是一個(gè)遞增有序序列。
3.二叉排序樹(shù)的插入
在二叉排序樹(shù)中插入新結(jié)點(diǎn)，要保證插入后的二叉樹(shù)仍符合二叉排序樹(shù)的定義。
插入過(guò)程：
若二叉排序樹(shù)為空，則待插入結(jié)點(diǎn)*S作為根結(jié)點(diǎn)插入到空樹(shù)中；
當(dāng)非空時(shí)，將待插結(jié)點(diǎn)關(guān)鍵字S->key和樹(shù)根關(guān)鍵字t->key進(jìn)行比較，若s->key = t->key,則無(wú)須插入，若s->key< t->key,則插入到根的左子樹(shù)中，若s->key> t->key,則插入到根的右子樹(shù)中。而子樹(shù)中的插入過(guò)程和在樹(shù)中的插入過(guò)程相同，如此進(jìn)行下去，直到把結(jié)點(diǎn)*s作為一個(gè)新的樹(shù)葉插入到二叉排序樹(shù)中，或者直到發(fā)現(xiàn)樹(shù)已有相同關(guān)鍵字的結(jié)點(diǎn)為止。
4.二叉排序樹(shù)的查找
假定二叉排序樹(shù)的根結(jié)點(diǎn)指針為 root ，給定的關(guān)鍵字值為 K ，則查找算法可描述為：
① 置初值： q ＝ root ；
② 如果 K ＝ q －＞ key ，則查找成功，算法結(jié)束；
③ 否則，如果 K ＜ q －＞ key ，而且 q 的左子樹(shù)非空，則將 q 的左子樹(shù)根送 q ，轉(zhuǎn)步驟②；否則，查找失敗，結(jié)束算法；
④ 否則，如果 K ＞ q －＞ key ，而且 q 的右子樹(shù)非空，則將 q 的右子樹(shù)根送 q ，轉(zhuǎn)步驟②；否則，查找失敗，算法結(jié)束。
5.二叉排序樹(shù)的刪除
假設(shè)被刪結(jié)點(diǎn)是*p，其雙親是*f，不失一般性，設(shè)*p是*f的左孩子，下面分三種情況討論：
⑴ 若結(jié)點(diǎn)*p是葉子結(jié)點(diǎn)，則只需修改其雙親結(jié)點(diǎn)*f的指針即可。
⑵ 若結(jié)點(diǎn)*p只有左子樹(shù)PL或者只有右子樹(shù)PR，則只要使PL或PR 成為其雙親結(jié)點(diǎn)的左子樹(shù)即可。
⑶ 若結(jié)點(diǎn)*p的左、右子樹(shù)均非空，先找到*p的中序前趨(或后繼)結(jié)點(diǎn)*s（注意*s是*p的左子樹(shù)中的最右下的結(jié)點(diǎn)，它的右鏈域?yàn)榭眨缓笥袃煞N做法：① 令*p的左子樹(shù)直接鏈到*p的雙親結(jié)點(diǎn)*f的左鏈上,而*p的右子樹(shù)鏈到*p的中序前趨結(jié)點(diǎn)*s的右鏈上。② 以*p的中序前趨結(jié)點(diǎn)*s代替*p（即把*s的數(shù)據(jù)復(fù)制到*p中），將*s的左子樹(shù)鏈到*s的雙親結(jié)點(diǎn)*q的左（或右）鏈上。
6、二叉樹(shù)的遍歷
二叉樹(shù)的遍歷有三種方式，如下：
（1）前序遍歷（DLR），首先訪(fǎng)問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。簡(jiǎn)記根-左-右。
（2）中序遍歷（LDR），首先遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。簡(jiǎn)記左-根-右。
（3）后序遍歷（LRD），首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪(fǎng)問(wèn)根結(jié)點(diǎn)。簡(jiǎn)記左-右-根。
二、代碼編寫(xiě)
1、樹(shù)節(jié)點(diǎn)類(lèi)的定義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、二叉排序樹(shù)的定義
package com.lin; /** * 功能概要：排序/平衡二叉樹(shù) */ public class SearchTree { public TreeNode root; public long size; /** * 往樹(shù)中加節(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ù)成功插入到平衡二叉樹(shù)中"); 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ù)成功插入到二叉查找樹(shù)中"); 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ù)成功插入到二叉查找樹(shù)中"); 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("=============================="+"采用遞歸的前序遍歷開(kāi)始"+"=============================="); TreeOrder.preOrderMethodOne(tree.root); System.out.println(); System.out.println("=============================="+"采用循環(huán)的前序遍歷開(kāi)始"+"=============================="); TreeOrder.preOrderMethodTwo(tree.root); System.out.println(); System.out.println("=============================="+"采用遞歸的后序遍歷開(kāi)始"+"=============================="); TreeOrder.postOrderMethodOne(tree.root); System.out.println(); System.out.println("=============================="+"采用循環(huán)的后序遍歷開(kāi)始"+"=============================="); TreeOrder.postOrderMethodTwo(tree.root); System.out.println(); System.out.println("=============================="+"采用遞歸的中序遍歷開(kāi)始"+"=============================="); TreeOrder.medOrderMethodOne(tree.root); System.out.println(); System.out.println("=============================="+"采用循環(huán)的中序遍歷開(kāi)始"+"=============================="); TreeOrder.medOrderMethodTwo(tree.root); } } 輸出結(jié)果：
同樣，進(jìn)行查找過(guò)程如下：
TreeNode node = tree.findTreeNode(100); System.out.println(node);
結(jié)果是正確的
以上就是關(guān)于Java二叉排序樹(shù)的詳細(xì)介紹，希望對(duì)大家的學(xué)習(xí)java程序設(shè)計(jì)有所幫助。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
