二叉查找樹的定義：
二叉查找樹或者是一顆空樹，或者是一顆具有以下特性的非空二叉樹：
1. 若左子樹非空，則左子樹上所有節點關鍵字值均小於根節點的關鍵字；
2. 若右子樹非空，則右子樹上所有節點關鍵字值均大於根節點的關鍵字；
3. 左、右子樹本身也分別是一顆二叉查找樹。
二叉查找樹的實現，功能有：
1. 用一個數組去構建二叉查找樹
2. 二叉查找樹的中序遍歷和層次遍歷
3. 插入節點
4. 查找節點
5. 查找二叉樹中的最大值和最小值
6. 得到節點的直接父節點
7. 得到節點的直接前驅和直接後繼節點
8. 刪除節點
樹節點TreeNode的定義見：Java實現鏈式存儲的二叉樹 http://www.linuxidc.com/Linux/2015-07/119873.htm
import java.lang.Integer;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
* 二叉排序樹（二叉查找樹）的實現
*/
public class BinarySearchTree {
private TreeNode<Integer> root; //根節點
public BinarySearchTree(){
root = null;
}
//用一個數組去構建二叉查找樹
public TreeNode<Integer> buildBST(Integer[] array){
if(array.length == 0){
return null;
}else{
root = null; //初始化樹為空樹
for(int i=0; i<array.length; i++){ //依次將每個元素插入
root = insertNode(root,array[i]);
}
return root;
}
}
//在二叉查找樹中插入一個數據域為data的結點，新插入的結點一定是某個葉子節點
public TreeNode<Integer> insertNode(TreeNode<Integer> node, Integer data){
if(node == null){ //原樹為空，新插入的記錄為根節點
node = new TreeNode<Integer>(data,null,null);
}else{
if(node.getData() == data){ //樹中存在相同關鍵字的結點,什麼也不做
}else{
if(node.getData() > data){ //根節點>插入數據，插入到左子樹中
node.setLchild(insertNode(node.getLchild(),data));
}else{ //根節點<插入數據，插入到右子樹中
node.setRchild(insertNode(node.getRchild(),data));
}
}
}
return node;
}
//二叉查找樹的中序遍歷，可以得到一個遞增的有序數列
public void inOrder(TreeNode<Integer> node){
if(node != null){
inOrder(node.getLchild());
System.out.print(node.getData()+" ");
inOrder(node.getRchild());
}
}
//二叉查找樹的層次遍歷
public void levelOrder(TreeNode<Integer> root){
Queue<TreeNode<Integer>> nodeQueue = new LinkedList<TreeNode<Integer>>();
TreeNode<Integer> node = null;
nodeQueue.add(root); //將根節點入隊
while(!nodeQueue.isEmpty()){ //隊列不空循環
node = nodeQueue.peek();
System.out.print(node.getData()+" ");
nodeQueue.poll(); //隊頭元素出隊
if(node.getLchild() != null){ //左子樹不空，則左子樹入隊列
nodeQueue.add(node.getLchild());
}
if(node.getRchild() != null){ //右子樹不空，則右子樹入隊列
nodeQueue.add(node.getRchild());
}
}
}
//查找數據域為data的結點，若不存在，返回null
public TreeNode<Integer> searchNode(TreeNode<Integer> node, Integer data){
while(node != null && node.getData() != data){
if(node.getData() > data){
node = node.getLchild(); //根節點>數據，向左走
}else{
node = node.getRchild(); //根節點<數據，向右走
}
}
return node;
}
//查找最大值：不斷地尋找右子節點
public TreeNode<Integer> getMaxData(TreeNode<Integer> node){
if(node.getRchild() == null){
return node;
}else{
return getMaxData(node.getRchild());
}
}
//查找最小值：不斷地尋找左子節點
public TreeNode<Integer> getMinData(TreeNode<Integer> node){
if(node.getLchild() == null){
return node;
}else{
return getMinData(node.getLchild());
}
}
//得到數據域為data的結點的直接父節點parentNode
public TreeNode<Integer> getParentNode(TreeNode<Integer> root, Integer data){
TreeNode<Integer> parentNode = root;
if(parentNode.getData() == data){ //根節點的父節點返回為null
return null;
}
while(parentNode != null){
//查找當前節點的父節點的左右子節點，若是相等，則返回該父節點
if((parentNode.getLchild() != null && parentNode.getLchild().getData() == data) ||
(parentNode.getRchild() != null && parentNode.getRchild().getData() == data)){
return parentNode;
}else{
if(parentNode.getData() > data){ //向左查找父節點
parentNode = parentNode.getLchild();
}else{
parentNode = parentNode.getRchild(); //向右查找父節點
}
}
}
return null;
}
/**
* 得到結點node的直接前趨
* a.該節點左子樹不為空：其前驅節點為其左子樹的最大元素
* b.該節點左子樹為空: 其前驅節點為其祖先節點(遞歸)，且該祖先節點的右孩子也為其祖先節點
* (就是一直往其parent找，出現左拐後的那個祖先節點)
*/
public TreeNode<Integer> getPrecessor(TreeNode<Integer> root,TreeNode<Integer> node){
if(node == null){
return null;
}
//a.該節點左子樹不為空：其前驅節點為其左子樹的最大元素
if(node.getLchild() != null){
return getMaxData(node.getLchild());
}else{ //b.該節點左子樹為空: 其前驅節點為其祖先節點(遞歸)
TreeNode<Integer> parentNode = getParentNode(root, node.getData());
while(parentNode != null && node == parentNode.getLchild()){
node = parentNode;
parentNode = getParentNode(root, parentNode.getData());
}
return parentNode;
}
}
/**
* 得到結點node的直接後繼(後繼節點就是比要刪除的節點的關鍵值要大的節點集合中的最小值)
* a.該節點右子樹不為空，其後繼節點為其右子樹的最小元素
* b.該節點右子樹為空，則其後繼節點為其祖先節點(遞歸)，且此祖先節點的左孩子也是該節點的祖先節點，
* 就是說一直往上找其祖先節點，直到出現右拐後的那個祖先節點��
*/
public TreeNode<Integer> getSuccessor(TreeNode<Integer> root,TreeNode<Integer> node){
if(node == null){
return null;
}
//a.該節點右子樹不為空，其後繼節點為其右子樹的最小元素
if(node.getRchild() != null){
return getMinData(node.getRchild());
}else{ //b.該節點右子樹為空，則其後繼節點為其最高祖先節點(遞歸)
TreeNode<Integer> parentNode = getParentNode(root, node.getData());
while(parentNode != null && node == parentNode.getRchild()){
node = parentNode;
parentNode = getParentNode(root, parentNode.getData());
}
return parentNode;
}
}
/**
* 刪除數據域為data的結點
* 按三種情況處理：
* a.如果被刪除結點z是葉子節點，則直接刪除，不會破壞二叉查找樹的性質
* b.如果節點z只有一顆左子樹或右子樹，則讓z的子樹成為z父節點的子樹，代替z的位置
* c.若結點z有左、右兩顆子樹，則令z的直接後繼（或直接前驅）替代z，
* 然後從二叉查找樹中刪去這個直接後繼（或直接前驅）,這樣就轉換為第一或第二種情況
* @param node 二叉查找樹的根節點
* @param data 需要刪除的結點的數據域
* @return
*/
public boolean deleteNode(TreeNode<Integer> node, Integer data){
if(node == null){ //樹為空
throw new RuntimeException("樹為空！");
}
TreeNode<Integer> delNode= searchNode(node, data); //搜索需要刪除的結點
TreeNode<Integer> parent = null;
if(delNode == null){ //如果樹中不存在要刪除的關鍵字
throw new RuntimeException("樹中不存在要刪除的關鍵字！");
}else{
parent = getParentNode(node,data); //得到刪除節點的直接父節點
//a.如果被刪除結點z是葉子節點，則直接刪除，不會破壞二叉查找樹的性質
if(delNode.getLchild()==null && delNode.getRchild()==null){
if(delNode==parent.getLchild()){ //被刪除節點為其父節點的左孩子
parent.setLchild(null);
}else{ //被刪除節點為其父節點的右孩子
parent.setRchild(null);
}
return true;
}
//b1.如果節點z只有一顆左子樹，則讓z的子樹成為z父節點的子樹，代替z的位置
if(delNode.getLchild()!=null && delNode.getRchild()==null){
if(delNode==parent.getLchild()){ //被刪除節點為其父節點的左孩子
parent.setLchild(delNode.getLchild());
}else{ //被刪除節點為其父節點的右孩子
parent.setRchild(delNode.getLchild());
}
delNode.setLchild(null); //設置被刪除結點的左孩子為null
return true;
}
//b2.如果節點z只有一顆右子樹，則讓z的子樹成為z父節點的子樹，代替z的位置
if(delNode.getLchild()==null && delNode.getRchild()!=null){
if(delNode==parent.getLchild()){ //被刪除節點為其父節點的左孩子
parent.setLchild(delNode.getRchild());
}else{ //被刪除節點為其父節點的右孩子
parent.setRchild(delNode.getRchild());
}
delNode.setRchild(null); //設置被刪除結點的右孩子為null
return true;
}
//c.若結點z有左、右兩顆子樹，則刪除該結點的後繼結點，並用該後繼結點取代該結點
if(delNode.getLchild()!=null && delNode.getRchild()!=null){
TreeNode<Integer> successorNode = getSuccessor(node,delNode); //得到被刪除結點的後繼節點
deleteNode(node,successorNode.getData()); //刪除該結點的後繼結點
delNode.setData(successorNode.getData()); //用該後繼結點取代該結點
return true;
}
}
return false;
}
public static void main(String args[]){
Scanner input = new Scanner(System.in);
Integer[] array = {8,3,10,1,6,14,4,7,13};
BinarySearchTree bst = new BinarySearchTree();
TreeNode<Integer> root = bst.buildBST(array);
System.out.print("層次遍歷：");
bst.levelOrder(root);
System.out.print("\n"+"中序遍歷：");
bst.inOrder(root);
System.out.println();
System.out.print("得到最大值：");
System.out.println(bst.getMaxData(root).getData());
System.out.print("得到最小值：");
System.out.println(bst.getMinData(root).getData());
System.out.print("向二叉查找樹中插入一個節點，請輸入需插入節點的數據域：");
int data = input.nextInt();
System.out.print("插入節點"+ data +"後，中序遍歷的結果：");
root = bst.insertNode(root, data);
bst.inOrder(root);
System.out.println("\n"+"在二叉查找樹中查找元素,"+"請輸入需要查找的結點值：");
data = input.nextInt();
if(bst.searchNode(root, data) == null){
System.out.println("false");
}else{
System.out.println("true");
}
System.out.println("查找節點的直接父節點,"+"請輸入需要查找的結點值：");
data = input.nextInt();
System.out.print("節點"+ data +"的父節點是：");
if(bst.getParentNode(root, data) == null){
System.out.println("null");
}else{
System.out.println(bst.getParentNode(root, data).getData());
}
System.out.println("刪除結點,"+"請輸入需要刪除的結點值：");
data = input.nextInt();
if(bst.deleteNode(root, data)){
System.out.print("刪除結點後的層次遍歷：");
bst.levelOrder(root);
System.out.print("\n"+"刪除結點後的中序遍歷：");
bst.inOrder(root);
}
}
}
程序運行結果：
層次遍歷：8 3 10 1 6 14 4 7 13
中序遍歷：1 3 4 6 7 8 10 13 14
得到最大值：14
得到最小值：1
向二叉查找樹中插入一個節點，請輸入需插入節點的數據域：15
插入節點15後，中序遍歷的結果：1 3 4 6 7 8 10 13 14 15
在二叉查找樹中查找元素,請輸入需要查找的結點值：
true
查找節點的直接父節點,請輸入需要查找的結點值：
節點10的父節點是：8
刪除結點,請輸入需要刪除的結點值：
刪除結點後的層次遍歷：8 3 10 1 6 14 7 13 15
刪除結點後的中序遍歷：1 3 6 7 8 10 13 14 15
某些方法的非遞歸實現：
1. 插入節點insertNode():
//在二叉查找樹中插入一個數據域為data的結點，新插入的結點一定是某個葉子節點
public TreeNode<Integer> insertNode(TreeNode<Integer> node, Integer data){
TreeNode<Integer> newNode = new TreeNode<Integer>(data,null,null);
TreeNode<Integer> tmpNode = node; //遍歷節點
TreeNode<Integer> pnode = null; //記錄當前節點的父節點
if(node == null){ //原樹為空，新插入的記錄為根節點
node = newNode;
return node;
}
while(tmpNode != null){
pnode = tmpNode;
if(tmpNode.getData() == data){ //樹中存在相同關鍵字的結點,什麼也不做
return node;
}else{
if(tmpNode.getData() > data){ //根節點>插入數據，插入到左子樹中
tmpNode = tmpNode.getLchild();
}else{ //根節點<插入數據，插入到右子樹中
tmpNode = tmpNode.getRchild();
}
}
}
if(pnode.getData() > data){
pnode.setLchild(newNode);
}else{
pnode.setRchild(newNode);
}
return node;
}
2. 二叉查找樹的中序遍歷：
//二叉查找樹的中序遍歷LNR，可以得到一個遞增的有序數列
public void inOrder(TreeNode<Integer> node){
Stack<TreeNode<Integer>> nodeStack = new Stack<TreeNode<Integer>>();
TreeNode<Integer> tempNode = node; //遍歷指針
while(tempNode != null || !nodeStack.isEmpty()){
if(tempNode != null){
nodeStack.push(tempNode);
tempNode = tempNode.getLchild();
}else{
tempNode = nodeStack.pop();
System.out.print(tempNode.getData() + " ");
tempNode = tempNode.getRchild();
}
}
}
3. 得到二叉查找樹的最大值和最小值：
//查找最大值：不斷地尋找右子節點
public TreeNode<Integer> getMaxData(TreeNode<Integer> node){
TreeNode<Integer> tempNode = node;
while(tempNode.getRchild()!=null){
tempNode = tempNode.getRchild();
}
return tempNode;
}
//查找最小值：不斷地尋找左子節點
public TreeNode<Integer> getMinData(TreeNode<Integer> node){
TreeNode<Integer> tempNode = node;
while(tempNode.getLchild() != null){
tempNode = tempNode.getLchild();
}
return tempNode;
}
