徹底弄懂二叉排序樹
前言
在之前學習數(shù)據(jù)結(jié)構(gòu)的時候，就學過二叉排序樹，不過，由于但是只是紙上談兵，雖然知道二叉排序樹的插入，刪除等的操作過程，不過由于沒有具體實現(xiàn)過，所以當想要實現(xiàn)的時候，就出現(xiàn)了“道理都懂，卻無法做到”的尷尬局面，趁著最近有空，抽了個時間認真學習二叉排序樹，并且手動編寫了實現(xiàn)的代碼，真正理解了二叉排序樹的操作過程
二叉排序樹簡介
二叉排序樹，二叉樹的一個變種，主要的特點在于，該樹的值在分布的時候具有非常明顯的特征，左子樹的值小于根節(jié)點的值，而根節(jié)點的值小于右子樹的值，這在進行搜索，查找的時候是非常有利的，因為它的平均操作時間接近O(h)，h為樹的高度，而且，二叉排序樹本身是具有動態(tài)性的，可以動態(tài)地進行節(jié)點的刪除，插入等的操作，接下來我們就通過具體的例子來學習二叉排序樹
深入學習二叉排序樹
首先先構(gòu)造一個二叉排序樹，然后我們來通過代碼演示如何生成該樹
從圖中可以看到，生成的樹相對是比較平衡的
樹的生成過程
class Tree{
private Node root;
public Node getRoot() {
return root;
}
// 構(gòu)造樹，構(gòu)造的過程相當于將data中的數(shù)據(jù)插入
public void construct(int[] data){
for (int i = 0; i < data.length; i++){
insert(data[i]);
}
}
/**
* 插入節(jié)點
* @param value 節(jié)點的值
*/
public void insert(int value){
Node pre = null;
Node current = root;
// 插入的過程：
// 每次都從根節(jié)點開始查找
// 如果值比根節(jié)點小，則插入的節(jié)點應(yīng)該在根節(jié)點的左側(cè)
// 否則，應(yīng)該在根節(jié)點的右側(cè)
while (current != null){
pre = current;
// 如果根節(jié)點的值比value大，
// 則新節(jié)點應(yīng)該插入在根節(jié)點的左側(cè)
if (current.value > value){
current = current.left;
//否則，應(yīng)該插入在右側(cè)
}else {
current = current.right;
}
}
current = new Node(value, pre, null, null);
// 如果pre是null，說明此時是空樹
if (pre == null){
root = current;
}else {
// 如果current的值比pre大，則current是pre的右節(jié)點
if (current.value > pre.value){
pre.right = current;
// 否則，current是pre的左節(jié)點
}else {
pre.left = current;
}
}
}
/**
* 中序遍歷樹，可以用于校驗樹是否成功創(chuàng)建
* @param current 當前節(jié)點
*/
public void show(Node current){
if (current != null){
show(current.left);
System.out.print(current.value + " ");
show(current.right);
}
}
/**
* 樹的節(jié)點
*/
private class Node{
int value;
Node parent;
Node left;
Node right;
public Node(int value, Node parent, Node left, Node right) {
this.value = value;
this.parent = parent;
this.left = left;
this.right = right;
}
}
}
經(jīng)過上面的步驟，我們就成功的創(chuàng)建了一個二叉排序樹了，可以通過簡單的測試來判斷樹的建立是否正確，其中一個比較簡單的方法就是通過中序遍歷該樹，由于二叉排序樹的特點，中序遍歷的結(jié)果應(yīng)當是一系列從小到大排序好的值
獲取樹中的最小值以及最大值
由于二叉排序樹的特點，其最小值必定在最左子樹，最大值必然在最右子樹，當然，如果是空樹那就沒有了，如果是只有跟節(jié)點的樹，那么最小值以及最大值都是根節(jié)點本身
// 獲取樹中的最小值
public Integer getMin(){
Node current = root;
if (current == null){
return null;
}
// 尋找最左子樹
while (current.left != null){
current = current.left;
}
return current.value;
}
// 獲取樹中的最大值
public Integer getMax(){
Node current = root;
if (current == null){
return null;
}
// 尋找最右子樹
while (current.right != null){
current = current.right;
}
return current.value;
}
查找包含某一值的節(jié)點
// 查找包含某一值的節(jié)點
public Node search(int value){
Node current = root;
while (current != null){
// 如果該值比當前節(jié)點的值小，則
// 找當前節(jié)點的左子樹
if (current.value > value){
current = current.left;
// 如果該值比當前節(jié)點的值大，則
// 找當前節(jié)點的右子樹
}else if (current.value < value){
current = current.right;
}else {
return current;
}
}
// 找不到則返回null
return null;
}
查找某一個節(jié)點的前驅(qū)和后繼
根據(jù)二叉排序樹的特點，某一個節(jié)點的前驅(qū)只可能是
- 如果該節(jié)點有左子樹，則該節(jié)點的前驅(qū)為其左子樹的最右子樹
- 如果沒有左子樹，則該節(jié)點的前驅(qū)為，沿著該節(jié)點的路徑往上走，第一個該節(jié)點不是其祖先的左節(jié)點則為其前驅(qū)(此處畫個圖比較好理解)
根據(jù)二叉排序樹的特點，如果target.parent.left == target，則target.parent的值比target的值大，所以應(yīng)該一直往上尋找，如果紅色箭頭所示，當找到第一個target.parent.right == target，如果黑色方框所示，這意味著target.parent的值是剛剛所經(jīng)過的路徑的最小值，而target就是倒數(shù)第二小的值，(還記得，target.parent的右子樹的最左子樹嗎?)
后繼節(jié)點的查找類似，只不過方向應(yīng)該相反，這里就不重復敘述了
// 前驅(qū)
public Node getPre(Node target){
if (target == null){
return null;
}
// 如果左子樹非空，則前驅(qū)為左子樹的最右子樹
if (target.left != null){
target = target.left;
// 尋找最右子樹
while (target.right != null){
target = target.right;
}
return target;
}else {
// 否則，查找該節(jié)點是某個節(jié)點的右子樹的最左子樹的節(jié)點
// 也就是沿著父親路徑往上走，第一個該節(jié)點不是其父親節(jié)點的左節(jié)點的節(jié)點
Node parent = target.parent;
while (parent != null && target == parent.left){
target = parent;
parent = parent.parent;
}
return parent;
}
}
// 后繼
public Node getSuc(Node target){
if (target == null){
return null;
}
// 查找右子樹的最左子樹
if (target.right != null){
target = target.right;
while (target.left != null){
target = target.left;
}
return target;
}else {
// 沿著父親路徑向上走，第一個該節(jié)點不是父親節(jié)點的右子樹的節(jié)點
Node parent = target.parent;
while (parent != null && target == parent.right){
target = parent;
parent = parent.parent;
}
return parent;
}
}
刪除節(jié)點
刪除節(jié)點是二叉排序樹最復雜的一個地方，主要是由于刪除的時候，存在多種情況
- 被刪除的節(jié)點沒有左右子樹
- 被刪除的節(jié)點只有左子樹
- 被刪除的節(jié)點只有右子樹
- 被刪除的節(jié)點有左右子樹
前三種情況比較好處理，直接令其父親指向其孩子即可，最后一種比較復雜，直接看代碼結(jié)合注釋比較好理解
// 刪除節(jié)點
public void remove(Node target){
if (target == null){
return;
}
// 只有右子樹
if (target.left == null){
// 如果target是其父親的左子樹
if (target.parent.left == target){
// 將target的右孩子連接到父親的左孩子，
// 也就是target的右孩子替代父親
target.parent.left = target.right;
}else {
// 如果target是右孩子，則連接到parent的右孩子
target.parent.right = target.right;
}
// 如果右孩子非空，右孩子的parent指向target.parent
if (target.right != null){
target.right.parent = target.parent;
}
// 如果target的右子樹為空，而且此時左子樹不為空
// 操作基本同上
}else if (target.right == null){
if (target.parent.left == target){
target.parent.left = target.left;
}else {
target.parent.right = target.left;
}
target.left.parent = target.parent;
// 如果左右子樹都非空，則用右子樹的最左子樹進行替代
}else {
// 如果target的右子樹沒有左子樹，直接拿右子樹進行替代
if (target.right.left == null){
if (target.parent.left == target){
target.parent.left = target.right;
}else {
target.parent.right = target.right;
}
// 指向target的parent
target.right.parent = target.parent;
// 接管target的左子樹
target.right.left = target.left;
}else {
// 尋找target的右子樹的最左子樹
Node current = target;
target = target.right;
while (target.left != null){
target = target.left;
}
// 直接替換其值即可
current.value = target.value;
// 此時target為右子樹的最左子樹，但是target可能有右子樹
// 所以刪除只有，target.parent.left需要接管target的右子樹
target.parent.left = target.right;
}
}
}
總結(jié)
本小節(jié)主要學習了二叉排序樹的基本原理，并且通過代碼的方式，學習了二叉排序樹的創(chuàng)建，插入，查找最大值，查找最小值，查找指定值的節(jié)點，查找指定節(jié)點的前驅(qū)，后繼，刪除節(jié)點等，其中刪除節(jié)點可以說最復雜，也是最難理解的一個，在學習的過程中最好結(jié)合具體的圖片，然后手動演示整個過程
