二叉排序樹

先看一個需求

給你一個數列(7,3, 10, 12,5,1,9)，要求能夠高效的完成對資料的查詢和添加。

方案我們一般首先會想到數組的方式

數組未排序，優點:直接在數組尾添加，速度快。缺點:查找速度慢.

數組排序，優點:可以使用二分查找，查找速度快，缺點:為了保證數組有序在添加新資料時，找到插入位置後，後面的資料需整體移動，速度慢。

鍊式存儲呢？

不管連結清單是否有序，查找速度都慢，添加資料速度比數組快，不需要資料整體

移動。

我們前面說到樹存儲可以有效解決，到底是為什麼呢?

二叉排序樹

介紹

二叉排序樹: BST: (Binary Sort(Search) Tree),對于二叉排序樹的任何一個非葉子節點，

要求左子節點的值比目前節點的值小，右子節點的值比目前節點的值大。

特别說明:如果有相同的值，可以将該節點放在左子節點或右子節點

二叉排序樹的建立和周遊

package 二叉排序樹;

public class BinarySortTree {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr= {7,3,10,12,5,1,9};
		BinarySortTreeDemo binarySortTree = new BinarySortTreeDemo();
		//循環添加節點到二叉樹
		for (int i = 0; i < arr.length; i++) {
			binarySortTree.addNode(new Node(arr[i]));
		}
//		System.out.println("中序周遊二叉樹");
		binarySortTree.infixOrder();
	}

}
//建立二叉排序樹
class BinarySortTreeDemo{
	private Node root;
	//添加節點的方法
	public void addNode(Node node){
		if(root == null){
			root = node;
		}else{
			root.addNode(node);
		}
	}
	//中序周遊
	public void infixOrder(){
		if(root != null){
			root.infixOrder();
		}else{
			System.out.println("空樹");
		}
	}
}
class Node{
	int value;
	Node left;
	Node right;
	public Node(int value) {
		super();
		this.value = value;
	}
	
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

	//添加節點的方法
	//遞歸的形式添加節點，需要滿足二叉排序樹
	public void addNode(Node node){
		if(node == null){
			return;
		}
		//判斷傳入的節點值，跟目前子樹根節點值的關系
		if(node.value < this.value){
			//如果目前節點的左子節點為空
			if(this.left == null){
				this.left = node;
			}else
			{
				this.left.addNode(node);//遞歸添加
			}
		}else{
			if(this.right == null){
				this.right = node;
			}else{
				this.right.addNode(node);
			}
		}
	}
	//中序周遊
	public void infixOrder(){
		if(this.left != null){
			this.left.infixOrder();
		}
		System.out.println(this);
		if(this.right != null){
			this.right.infixOrder();
		}
	}
}

二叉排序樹的删除

這裡面有很多情況：

1.删除葉子結點

2.删除隻有一顆子樹的節點

3.删除有兩顆子樹的節點

思路

情況一：删除葉子節點

1.需要先找到待删除的節點targetNode

2.找到待删除節點的父節點parent(考慮是否有父節點)

3.判斷targetNode是parent的左子節點還是右子節點

4.根據前面，對應删除

情況二：删除隻有一顆子樹的節點

1.需要先找到待删除的節點targetNode

2.找到待删除節點的父節點parent(考慮是否有父節點)

3.确定targetNode的子節點是左子節點還是右子節點

4.确定targetNode是parent的左子節點還是右子節點

5.如果targetNode有左子節點

1）targetNode是parent的左子節點

parent.left = targetNode = left;

2)targetNode是parent的右子節點

parent.left = targetNode .right;

6.如果targetNode有右子節點同理

情況三：删除有兩顆子樹的節點

1.需要先找到待删除的節點targetNode

2.找到待删除節點的父節點parent(考慮是否有父節點)

3.從targetNode的右子樹找到最小的節點

4.用臨時變量将最小節點的值儲存起來 temp

5.删除最小節點

6.targetNode.value = temp

删除節點代碼

package 二叉排序樹;

public class BinarySortTree {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr= {7,3,10,12,5,1,9,2};
		BinarySortTreeDemo binarySortTree = new BinarySortTreeDemo();
		//循環添加節點到二叉樹
		for (int i = 0; i < arr.length; i++) {
			binarySortTree.addNode(new Node(arr[i]));
		}
//		System.out.println("中序周遊二叉樹");
		binarySortTree.infixOrder();
		
		//測試删除葉子節點
//		binarySortTree.delNode(2);
//		System.out.println("删除2節點後");
//		binarySortTree.infixOrder();
		binarySortTree.delNode(10);
		binarySortTree.infixOrder();

	}

}
//建立二叉排序樹
class BinarySortTreeDemo{
	private Node root;
	//添加節點的方法
	public void addNode(Node node){
		if(root == null){
			root = node;
		}else{
			root.addNode(node);
		}
	}
	//中序周遊
	public void infixOrder(){
		if(root != null){
			root.infixOrder();
		}else{
			System.out.println("空樹");
		}
	}
	//查找要删除的節點
	public Node search(int value){
		if(root == null){
			return null;
		}else{
			return root.search(value);
		}
	}
	//查找待删除節點的父節點
	public Node searchParent(int value){
		if(root == null){
			return null;
		}else{
			return root.searchParent(value);
		}
	}
	//編寫方法
	/**
	 * 傳回最小節點值，并且删除以node為根節點的二叉排序樹的最小節點
	 * @param node	當做一顆二叉排序樹的根節點
	 * @return		傳回的以node為根節點的二叉排序樹的最小節點的值
	 */
	public int delRightTreeMin(Node node){
		Node target = node;
		//循環查找左子節點，就會找到最小值
		while(target.left != null){
			target = target.left;
		}
		//這是target就指向了最小節點
		//删除最小節點
		delNode(target.value);
		return target.value;
	}
	
	//删除葉子結點的方法
	public void delNode(int value){
		if(root == null){
			return;
		}else{
			//1.需要先去找到待删除節點
			Node targetNode = search(value);
			//如果沒有找到
			if(targetNode == null){
				return;
			}
			//如果目前這課二叉排序樹隻有一個節點
			if(root.left == null&& root.right == null){
				root = null;
				return;
			}
			//去查找targetNode的父節點
			Node parent = searchParent(value);
			//如果待删除的節點是葉子結點
			if(targetNode.left == null && targetNode.right == null){
				//如果targetNode是parent的左子節點
				if(parent.left != null && parent.left.value == targetNode.value){
					parent.left = null;
				}else if(parent.right != null && parent.right.value == targetNode.value){
					parent.right = null;
				}
			}else if(targetNode.left!=null && targetNode.right != null){
				int minValue = delRightTreeMin(targetNode.right);
				targetNode.value = minValue;
			}else{
				//删除隻有一個子樹的節點
				//如果删除的節點有左子節點
				if(targetNode.left != null){
					if(parent.left.value == targetNode.value){
						parent.left = targetNode.left;
					}else{
						parent.right = targetNode.left;
					}
				}else{
					//要删除的節點有右子節點
					if(parent.left.value == targetNode.value){
						parent.left = targetNode.right;
					}else{
						parent.right = targetNode.right;
					}
				}
			}
		}
	}
}
class Node{
	int value;
	Node left;
	Node right;
	public Node(int value) {
		super();
		this.value = value;
	}
	
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

	/**
	 * 查找待删除的節點
	 * @param value	待删除節點的值
	 * @return
	 */
	public Node search(int value){
		if(value == this.value){
			return this;
		}else if(value < this.value){//應該向左子樹遞歸查找
			if(this.left != null){
				return this.left.search(value);
			}else{
				return null;
			}
		}else{
			if(this.right == null){
				return null;
			}else{
				return this.right.search(value);
			}
		}
	}
	/**
	 * 查找待删除節點的父節點
	 * @param value		待删除節點的值
	 * @return     傳回待删除節點的父節點
	 */
	public Node searchParent(int value){
		if((this.left !=null && this.left.value == value) || (this.right != null && this.right.value == value)){
			//目前節點就是待删除節點的父節點
			return this;
		}else{
			//如果查找的值，小于目前節點的值，且目前節點的左子節點不為空
			if(value < this.value && this.left != null){
				return this.left.searchParent(value);
			}else if(value >= this.value && this.right != null){
				return this.right.searchParent(value);
			}else{
				return null;//沒有找到父節點
			}
		}
	}
	
	
	//添加節點的方法
	//遞歸的形式添加節點，需要滿足二叉排序樹
	public void addNode(Node node){
		if(node == null){
			return;
		}
		//判斷傳入的節點值，跟目前子樹根節點值的關系
		if(node.value < this.value){
			//如果目前節點的左子節點為空
			if(this.left == null){
				this.left = node;
			}else
			{
				this.left.addNode(node);//遞歸添加
			}
		}else{
			if(this.right == null){
				this.right = node;
			}else{
				this.right.addNode(node);
			}
		}
	}
	//中序周遊
	public void infixOrder(){
		if(this.left != null){
			this.left.infixOrder();
		}
		System.out.println(this);
		if(this.right != null){
			this.right.infixOrder();
		}
	}
}

注意事項

删除多個節點的時候一定要注意順序，有的順序可以正常删除，但是有的順序會報空指針錯誤，原因就是删除的順序有問題，導緻我們删除方法中的判斷出了問題，就是根節點這個地方，他沒有父節點，但是我們判斷了，是以在這出錯

資料結構--------二叉排序樹二叉排序樹

二叉排序樹

繼續閱讀

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method

hdu7108哈希