一、二叉排序樹定義
1.二叉排序樹的定義<br /> 二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：
①若它的左子樹非空，則左子樹上所有結點的值均小於根結點的值；
②若它的右子樹非空，則右子樹上所有結點的值均大於根結點的值；
③左、右子樹本身又各是一棵二叉排序樹。
上述性質簡稱二叉排序樹性質(BST性質)，故二叉排序樹實際上是滿足BST性質的二叉樹。
2.二叉排序樹的性質<br />按中序遍歷二叉排序樹，所得到的中序遍歷序列是一個遞增有序序列。
3.二叉排序樹的插入<br />在二叉排序樹中插入新結點，要保證插入後的二叉樹仍符合二叉排序樹的定義。
插入過程：
若二叉排序樹為空，則待插入結點*S作為根結點插入到空樹中；
當非空時，將待插結點關鍵字S->key和樹根關鍵字t->key進行比較，若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，如此進行下去，直到把結點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發現樹已有相同關鍵字的結點為止。
4.二叉排序樹的查找<br />假定二叉排序樹的根結點指針為root ，給定的關鍵字值為K ，則查找算法可描述為：
① 置初值： q ＝ root ；
② 如果K ＝ q －＞ key ，則查找成功，算法結束；
③ 否則，如果K ＜ q －＞ key ，而且q 的左子樹非空，則將q 的左子樹根送q ，轉步驟②；否則，查找失敗，結束算法；
④ 否則，如果K ＞ q －＞ key ，而且q 的右子樹非空，則將q 的右子樹根送q ，轉步驟②；否則，查找失敗，算法結束。
5.二叉排序樹的刪除<br />假設被刪結點是*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、二叉樹的遍歷<br />二叉樹的遍歷有三種方式，如下：
（1）前序遍歷（DLR），首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。簡記根-左-右。
（2）中序遍歷（LDR），首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。簡記左-根-右。
（3）後序遍歷（LRD），首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。簡記左-右-根。
二、代碼編寫
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程序設計有所幫助。