王道資料結構自學-二叉排序樹（二叉查找樹）

二叉排序樹就是将比結點大的值放在右結點，比結點小的值放在左結點。

// 建構樹的結構
typedef int KeyType;
typedef struct BSTNode
{
	KeyType key;
	BSTNode* lchild;//樹的左孩子結點
	BSTNode* rchild;//樹的右孩子結點
}BSTNode, * BiTree;
           

1 插入

1. 首先判斷被插入的結點是否存在，不存在的話先給這個結點申請空間初始化（将左右孩子置空，數值等于要插入的值）
2. 如果存在，看一下元素是否一樣，一樣就不插入了
3. 如果存在且值不一樣，值小于結點的值就放入左子樹，反之放入右子樹

int BST_Insert(BiTree& T, KeyType k) {
	if (NULL == T) {
		//為新結點申請空間，第一個結點作為樹根
		T = (BiTree)malloc(sizeof(BSTNode));
		T->key = k;
		T->lchild = T->rchild = NULL;
		return 1;//代表插入成功
	}
	else if (k == T->key) {
		return 0;//元素相同就不插入
	}
	else if(k < T->key)
	{
		return BST_Insert(T->lchild, k);
	}
	else
	{
		return BST_Insert(T->rchild, k);
	}
}
           

2 建立

• 建立就是循環插入的過程

void Creat_BST(BiTree& T, KeyType str[], int n) {
	T = NULL;
	int i = 0;
	while (i < n) {
		BST_Insert(T, str[i]);//把某一個結點放入二叉樹
		i++;
	}
}
           

3 查找

查找就是根據要查找的值比結點大還是比結點小的關系進行查找的過程。比結點大就要去右孩子查找，比結點小就要求左孩子查找，直至周遊完。

BSTNode* BST_Search(BiTree T, KeyType key, BiTree& p) {
	p = NULL;//存儲要找的結點的父親
	while (T != NULL && key != T->key) {
		p = T;
		if (key < T->key) {
			T = T->lchild;//比目前結點小，就左邊找
		}
		else
		{
			T = T->rchild;//比目前結點大，就右邊找
		}
	}
	return T;
}
           

4 删除

了解原理即可，考察代碼幾率不大

• 被删除結點的左子樹存在，右子樹為空，左子樹直接頂替結點
• 被删除結點的左子樹為空，右子樹存在，右子樹直接頂替結點
• 被删除結點的左右子樹都存在，采取用左子樹最大值或者右子樹最小值頂替結點的方法，選一個即可

void DeleteNode(BiTree& root, KeyType x) {
	if (root == NULL) {
		return;
	}
	if (root->key > x) {
		DeleteNode(root->lchild, x);
	}
	else if (root->key < x) {
		DeleteNode(root->rchild, x);
	}
	else//找到了要删除的結點
	{
		if (root->lchild == NULL) {//左子樹為空，右子樹直接頂上去
			BiTree tempNode = root;//用臨時的存着的目的是一會要給他free
			root = root->rchild;
			free(tempNode);
		}
		else if (root->rchild == NULL) {//右子樹為空，左子樹直接頂上去
			BiTree tempNode = root;
			root = root->lchild;
			free(tempNode);
		}
		else//左右子樹都不為空
		{//一般的删除政策是：左子樹的最大資料 或 右子樹的最小資料 代替删除的結點
			//這裡采用使用左子樹最大資料代替删除結點的方法
			BiTree tempNode = root->lchild;
			if (tempNode->rchild != NULL) {
				tempNode = tempNode->rchild;
			}
			root->key = tempNode->key;
			DeleteNode(root->lchild, tempNode->key);
		}
	}
}
           

點選下載下傳源碼