引入

基本性質：

二叉排序樹（又叫二叉搜索、查找樹) 是一種特殊的二叉樹，定義如下：

若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
左、右子樹也分別為二叉排序樹，
不允許有鍵值相同結點，【如果真的出現了，那么放在左子樹，右子樹是無所謂的】

二分查找與二叉排序樹

? 二分查找也稱為折半查找，要求原線性表有序，它是一種效率很高的查找方法，如果在需要進行頻繁修改的表中采用二分查找，其效率也是非常低下的，因為順序表的修改操作效率低，如果只考慮頻繁的修改，我們可以采用鏈表，然而，鏈表的查找效率又非常低，綜合這兩種資料結構的優勢，二叉查找樹(Binary Sort/Search Tree)登場了，

給定一串數\(（65,32,87,46,71,98,39）\)，使用插入構造法，步驟如下：

# 二叉排序樹的基本操作

結構體定義

typedef struct BTNode
{
	char data;
	struct BTNode* Left;
	struct BTNode* Right;
}*BTree;

typedef BTNode BSTNode, *BSTree;

查找節點

如果是普通二叉樹的查找操作，因為無法確定二叉樹的具體特性，因此只能對其左右子樹都進行遍歷，但二叉排序樹的特性，則會有一條確定的路線，

//找不到回傳NULL，找到回傳該節點，
//非遞回
BSTNode* BSTreeFind(BSTree t, int x) {
	if (!t)return NULL;
	if (t->data =https://www.cnblogs.com/czc1999/p/= x) return t;
	if (x < t->data) return BSTreeFind(t->Left, x);
	if (x > t->data) return BSTreeFind(t->Right, x);
}
//非遞回
BSTNode* BSTFind(BSTree T,int x) {
	BSTree p = T;
	while (p) {
		if (x == p->data)
			return p;
		p = x > p->data ? p->Right : p->Left;
	}
	return NULL;
}

插入節點

對于一顆二叉排序樹來說，如果查找某個元素成功，說明該結點存在；如果查找失敗，則查找失敗的地方一定就是該結點應該插入的地方，

BSTree InsertBStree(BSTree BST, int x) {
	if (BST == NULL) {
		BST = new BSTNode;
		BST->data = https://www.cnblogs.com/czc1999/p/x;
		return BST;
	}
	if (x < BST->data)
		BST->Left = InsertBStree(BST->Left, x);
	else
		BST->Right = InsertBStree(BST->Right, x);
	return BST;
}

二叉排序樹的建立

建立一顆二叉排序樹，就是先后插入\(n\)個結點的程序，與一般二叉樹的建立是完全一樣的，

BSTree BuildBSTree(int* a, int length) {
	BSTree BST = NULL;
	for (int i = 0; i < length; i++)
		BST = InsertBStree(BST, a[i]);
	return BST;
}

二叉排序樹的洗掉

? 二叉查找樹的洗掉操作一般有兩種常見做法，復雜度都是\(O(h)\)或\(O(log(n))\)，其中 \(h\) 為樹的高度，\(n\) 為結點個數，

? 如下圖的二叉排序樹，如果要洗掉結點 \(5\)，則有兩種辦法，一種辦法是以樹中比 \(5\) 小的最大結點（結點 \(4\) ）覆寫結點 \(5\) ，另一種是用樹中比 \(5\) 大的最小結點（結點 \(6\) ）覆寫結點 \(5\)，

? 在二叉排序樹中把比該結點權值小的最大結點稱為該結點的前驅，把比該結點權值大的最小結點稱為該結點的后繼，結點的前驅是左子樹的最右結點，結點的后繼是右子樹的最左結點，用下面兩個函式用來尋找以`root`為根的樹中最大、最小權值的結點，后面會使用到，

//獲得以root為根結點的樹中的最大值結點
int GetMax(BSTree root) {
	while (root->Right != NULL)
		root = root->Right;
	return root->data;
}

//獲得以root為根結點的樹中的最小值
int GetMin(BSTree root) {
	while (root->Left != NULL) {
		root = root->Left;
	}
	return root->data;
}

假設決定使用結點\(N\)的前驅 \(P\) 來替換 \(N\) ，于是就把問題轉換為，先用 \(P\) 的值去覆寫 \(N\) 的權值，再洗掉結點\(P\)，于是洗掉操作的實作如下：（寫法1好理解，寫法2更簡潔）

寫法1：

使用 BSTree root，如果 root 為要洗掉的結點， \(P\) 為父節點，洗掉情況有以下3種：

　　1. root 結點是葉子，將 \(P\) 節點的 left 或 right 指標域置為NULL，

　　2. root 結點只有左子樹，將 root 節點的 left 重新到結點 \(P\) 上，和洗掉單鏈表節點類似，（只有右子樹時情況相似，第一種情況，寫的時候可以和第二種合并起來）

　　3. root 結點既有左子樹，也有右子樹，尋找結點的前驅 pre（或者后繼），用 pre 的值去覆寫 root 的權值，再洗掉結點 pre?，而這個 pre 的洗掉一定屬于情況 1 或者 2 ，

? 這個寫法更適合JAVA，代碼里的那些 delete 還可以省去，但是必須要注意的是：函式的回傳值不是多余的，洗掉只有一個（或沒有）子樹的根節點的時候，必須用到這個回傳值，

實作方法1：

//洗掉結點左子樹的最大值結點
BSTree DelMax(BSTree root) {
    if (root->Right == NULL) {
        BSTNode *t= root->Left;
        delete root;
        return t;
    }
    root->Right = DelMax(root->Right);
    return root;
}

BSTree BSTDel(BSTree root,int x) {
    if (root == NULL) 
        return NULL;
    if (root->data =https://www.cnblogs.com/czc1999/p/= x) {
        //情況1和2，被洗掉的結點只有左子樹或右子樹，或沒有子樹
        if (! root->Right || !root->Left) {
            BSTNode *t = !root->Right ? root->Left : root->Right;
            delete root;
            return t;
        }
        //洗掉既有左子樹，也有右子樹的結點
        else{
            root->data = GetMax(root->Left);
        	root->Left = DelMax(root->Left);
        }
    }
    else if (x > root->data) 
        root->Right = BSTDel(root->Right, x);
    else  
        root->Left = BSTDel(root->Left, x);
    return root;
}

實作方法2：

//洗掉子樹中的最大值
void DelMax(BSTree &root,int &value) {
	if (!root)return;
	if (root->Right == NULL) {
		BSTNode *t= root;
		value = https://www.cnblogs.com/czc1999/p/root->data;
		root = root->Left;
		delete t;
	}
	else
		DelMax(root->Right, value);
}

void BSTDel(BSTree &root,int x) {
	if (root == NULL) 
		return;
	BSTree p = root;
	if (p->data == x) {
		if (! p->Right || !p->Left) {
			root = !p->Right ? p->Left : p->Right;
			delete p;
		}
		else
			//因為使用的方法是值替換，并沒有把原來的root覆寫掉，所以delete p不能像和下面方法2一樣寫在整個大if里
			DelMax(root->Left, root->data);
	}
	else if (x > p->data) BSTDel(p->Right, x);
	else  BSTDel(p->Left, x);
}

寫法2：

使用 BSTree *root，和上面的BSTree &root是等價的，如果 root 為要洗掉的結點，洗掉情況也是以下3種：

　　1. 當前 root 結點是葉子，將 root 置空，
　　2. root 結點只有左子樹，將 root 置為 root->Right（只有右子樹時情況相似，第一種情況，寫的時候可以和第二種合并起來）
　　3. 被洗掉的結點既有左子樹，也有右子樹，尋找結點的前驅 pre（或者后繼），用 root 的指標域覆寫 pre 的指標域，再把結點 root 洗掉，（形象化來說就是洗掉 root，把 pre 移動到 root 的位置）

void BSTDel(BSTree *root, int x){
    if (!*root) return; 
    BSTree p = *root;
    if (p->data =https://www.cnblogs.com/czc1999/p/= x) {
        if (!p->Right || !p->Left)
        	*root = !p->Right ? p->Left : p->Right;
        else{
                BSTNode *parent = p->Left, *q = p->Left;
                if (!q->Right) q->Right = p->Right;
                else {
                    while (q->Right) {
                        parent = q;
                        q = q->Right;
                    }
                    parent->Right = q->Left;
                    q->Left = p->Left;
                    q->Right = p->Right;
                }
                *root = q;
        }
        delete p;
    }
    else if (x > p->data) //向右找
        BSTDel(&(p->Right), x);
    else if (x < p->data) //向左找
        BSTDel(&(p->Left), x);
}

二叉排序樹的性質

二叉排序樹最基本的性質：二叉排序樹的中序序列是有序的，

如果合理調整二叉排序樹的形態，使得樹上的每個結點都盡量有兩個子結點，這樣整個二叉樹的高度就會大約在\(log(n)\) 左右，其中 \(n\) 為結點個數，實作這個要求的一種樹就是下一篇平衡二叉樹（AVL Tree），

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135929.html

標籤：其他

上一篇：瀏覽器無法連接HDFS檔案系統

下一篇：【LeetCode】7. 整數反轉

資料結構篇——二叉排序（查找，搜索）樹

引入