二叉排序樹

二叉排序樹介紹

二叉排序樹的創建(節點的添加)

從二叉排序樹的定義知，它的前提是二叉樹，并且采用了遞回的方式進行定義，它的節點間滿足一個偏序關系，左子樹根節點的值一定比父節點小，右子樹根節點的值一定比父節點大，

構建這樣一顆樹的目的是為了提高排序的速度，如果對二叉樹排序樹進行中序遍歷，可以發現，得到的序列是一個遞增序列，

二叉排序樹的節點添加指的是：將給定的值生成結點后，添加到樹上的某個位置，并且保持這棵樹還是二叉排序樹，

演算法原理

對于要添加的節點node，從根節點出發，總共四種情況依次判斷：
1）若為空樹，則創建一個值為node的結點并且回傳；
2）node的值等于樹根結點的值，無須執行添加，直接回傳根結點；
3）node的值小于樹根結點的值，那么添加位置一定在左子樹，遞回執行添加左子樹的程序，并且回傳添加結果作為新的左子樹；
4）node的值大于樹根結點的值，那么添加位置一定在右子樹，遞回執行添加右子樹的程序，并且回傳添加結果作為新的右子樹；

    /**
	 * 添加節點的方法
	 */
	public void add(Node node) {
		if (root == null) {
			root = node;// 如果root為空則直接讓root指向node
		} else {
			root.add(node);
		}
	}
    /**
	 * 添加節點的方法 遞回的形式添加節點，注意需要滿足二叉樹排序樹的要求
	 * 
	 * @param node
	 */
	public void add(Node node) {
		if (node == null) {
			return;
		}
		// 判斷傳入的節點的值，和當前子樹的根節點的值關系
		if (node.value < this.value) {
			// 如果當前節點左子節點位null
			if (this.left == null) {
				this.left = node;
			} else {
				// 遞回的向左子樹添加
				this.left.add(node);
			}
		} else {// 添加的節點的值大于當前節點的值
			if (this.right == null) {
				this.right = node;
			} else {
				// 遞回的向右子樹添加
				this.right.add(node);
			}
		}
	}

二叉排序樹的遍歷

二叉排序樹的中序遍歷是最常用的，一顆二叉排序樹的中序遍歷是一個遞增序列，
遞增序列是存在單調性的，所以可以利用這個特性，在有效的時間內找出這棵樹的第 k個結點，

二叉排序樹的查找

對于要查找的樹node,從根節點出發，總共四種情況依次判斷：
1）若為空樹，直接回傳null；
2）node的值等于樹根結點的值，則直接回傳；
3）node的值小于樹根結點的值，說明node對應的結點不在根結點，也不在右子樹上，則遞回回傳左子樹的查找結果；
4）node的值大于樹根結點的值，說明node對應的結點不在根結點，也不在左子樹上，則遞回回傳右子樹的查找結果；

    // 查找節點
	public Node search(int value) {
		if (root == null) {
			return null;
		} else {
			return root.search(value);
		}
	}
    /**
	 * 查找節點
	 */
	public Node search(int value) {
		if (value == this.value) {// 找到就是該節點
			return this;
		} else if (value < this.value) {// 如果查找的值小于當前節點，向左子樹遞回查找
			// 如果左子節點為空
			if (this.left == null) {
				return null;
			}
			return this.left.search(value);
		} else {// 如果查找的值不小于當前節點，向右子樹遞回查找
			if (this.right == null) {
				return null;
			}
			return this.right.search(value);
		}
	}

二叉樹的節點洗掉

情況一：洗掉葉子節點

1）需要先去找到要洗掉的節點 targetNode

2）找到targetNode的父節點parent

3）確定targetNode是parent的左子節點還是右子節點

4）根據前面的情況來對應洗掉：左子節點 parent.left = null ; 右子節點 parent.right = null

情況二：洗掉只有一顆子樹的節點

1）需要先去找到要洗掉的節點 targetNode

2）找到targetNode的父節點parent

3）確定targetNode的子節點是左子節點還是右子節點

4）targetNode是parent的左子節點還是右子節點

5）如果targetNode有左子節點

5.1 如果targetNode是parent的左子節點 ：parent.left = targetNode.left;

5.2 如果targetNode是parent的右子節點 ：parent.right = targetNode.left;

6）如果targetNode有右子節點

6.1 如果targetNode是parent的左子節點 ：parent.left = targetNode.right;

6.2 如果targetNode是parent的右子節點 ：parent.right = targetNode.right;

情況三：洗掉兩顆子樹的節點

1）需要先去找到要洗掉的節點 targetNode

2）從targetNode的右子樹找到最小的節點

3）用一個臨時變數，將最小節點的值保存

4）洗掉該最小節點

5）targetNode.value = temp

如圖所示，下圖展示的是，從這棵樹洗掉根結點 5 的程序，首先，由于它有左右子樹結點，從右子樹中找到最小的結點 6，保存節點6的值，洗掉 6 ，

注：還有一種洗掉思路為左子樹找到最大的，

在介紹二叉排序樹的結點洗掉演算法前，我們首先需要知道以下三個方法：

1）查找要洗掉的節點

    // 查找要洗掉的節點
	public Node search(int value) {
		if (root == null) {
			return null;
		} else {
			return root.search(value);
		}
	}
    /**
	 * 查找要洗掉的節點
	 */
	public Node search(int value) {
		if (value == this.value) {// 找到就是該節點
			return this;
		} else if (value < this.value) {// 如果查找的值小于當前節點，向左子樹遞回查找
			// 如果左子節點為空
			if (this.left == null) {
				return null;
			}
			return this.left.search(value);
		} else {// 如果查找的值不小于當前節點，向右子樹遞回查找
			if (this.right == null) {
				return null;
			}
			return this.right.search(value);
		}
	}

2）查找父節點

    // 查找父節點
	public Node searchParent(int value) {
		if (root == null) {
			return null;
		} else {
			return root.searchParent(value);
		} 	
	}
    /**
	 * 查找要洗掉節點的父節點
	 * 
	 * @param value 要找到的節點的值
	 * @return 回傳的是要洗掉的節點的父節點，如果沒有就回傳null
	 */
	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;// 沒有找到父節點
			}
		}
	}

3）回傳最小節點

	/**
	 * 1.回傳以node為根節點的二叉排序樹的最小節點的值 2.洗掉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.找到要洗掉節點 targetNode
			Node targetNode = search(value);
			// 2.如果沒有找到要洗掉的節點
			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) {
				if (parent.left != null && parent.left.value == value) {// 是右子節點
					parent.left = null;
				} else if (parent.right != null && parent.right.value == value) {// 是左子節點
					parent.right = null;
				}
			} else if (targetNode.left != null && targetNode.right != null) {// 洗掉有兩顆子樹的節點
				int minVal = delRightTreeMin(targetNode.right);
				targetNode.value = minVal;
			} else {// 洗掉只有一顆子樹的節點
					// 如果targetNode有左子節點
				if (targetNode.left != null) {
					if (parent != null) {
						// 如果targetNode是parent的左子節點
						if (parent.left.value == value) {
							parent.left = targetNode.left;
						} else {
							// targetNode是parent的右子節點
							parent.right = targetNode.left;
						}
					} else {
						root = targetNode.left;
					}
				} else {// 如果targetNode有右子節點
					if (parent != null) {
						// 如果targetNode是parent的左子節點
						if (parent.left.value == value) {
							parent.left = targetNode.right;
						} else {// 如果targetNode是parent的右子節點
							parent.right = targetNode.right;
						}
					} else {
						root = targetNode.right;
					}
				}
			}
		}
	}

二叉排序樹的總結

縱觀二叉排序樹的查找、插入和洗掉，完全取決于二叉排序樹的形狀，如果是完全二叉樹或者接近完全二叉樹，則這三個程序都是 O(log_2_n),如果是斜樹，則三個程序近似操作線性表，為O(n).