12.動态查找-二叉排序樹

實驗12 動态查找 二叉排序樹

代碼

#include <iostream>

using namespace std;

#define ENDFLAG '#'

struct ElemType
{
	char key;
	// Other info
};

struct BSTNode
{
	ElemType data;			  //結點資料域
	BSTNode *lchild, *rchild; //左右孩子指針
};

using BSTree = BSTNode *;

// 二叉排序樹的遞歸查找
BSTree SearchBST(BSTree T, char key)
{
	//在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的資料元素
	//若查找成功，則傳回指向該資料元素結點的指針，否則傳回空指針
	if (!T || T->data.key == key)
		return T; //查找結束
	else if (key < T->data.key)
		return SearchBST(T->lchild, key); //在左子樹中繼續查找
	else
		return SearchBST(T->rchild, key); //在右子樹中繼續查找
}

// 二叉排序樹的插入
void InsertBST(BSTree &T, ElemType e)
{
	//當二叉排序樹T中不存在關鍵字等于e.key的資料元素時，則插入該元素
	if (!T)
	{										   //找到插入位置，遞歸結束
		BSTNode *node = new BSTNode;		   //生成新結點*S
		node->data = e;						   //新結點*S的資料域置為e
		node->lchild = node->rchild = nullptr; //新結點*S作為葉子結點
		T = node;							   //把新結點*S連結到已找到的插入位置
	}
	else if (e.key < T->data.key)
		InsertBST(T->lchild, e); //插入左子樹
	else if (e.key > T->data.key)
		InsertBST(T->rchild, e); //插入右子樹
}

//　二叉排序樹的建立
void CreateBST(BSTree &T)
{
	T = nullptr;
	ElemType e;
	cin >> e.key;
	while (e.key != ENDFLAG) //ENDFLAG為自定義常量，作為輸入結束标志
	{
		InsertBST(T, e); //将此結點插入二叉排序樹T中
		cin >> e.key;
	}
}

// 從二叉排序樹T中删除關鍵字等于key的結點
void DeleteBST(BSTree &T, char key)
{
	BSTree target = T;		 // 要删除的結點
	BSTree parent = nullptr; // 要删除結點的父節點

	while (target) // 從根開始查找關鍵字等于key的結點
	{
		if (target->data.key == key)
			break; // 找到了

		parent = target; // 記錄父節點
		if (target->data.key > key)
			target = target->lchild;
		else
			target = target->rchild;
	}

	if (!target)
		return; // 找不到要删結點

	// 被删結點左右子樹均不空
	if ((target->lchild) && (target->rchild))
	{
		// 找到待删除結點中序周遊的前驅結點, 即左子樹中最右下的結點
		BSTree pre = target->lchild;	// 前驅結點
		BSTree parent_of_pre = nullptr; // 前驅結點的父節點
		while (pre->rchild)
		{
			parent_of_pre = pre;
			pre = pre->rchild;
		}
		target->data = pre->data;			 // 偷天換日, 把前驅結點的值扔到待删除的結點裡面
		parent_of_pre->rchild = pre->lchild; // 如果前驅結點有左子樹(不可能有右子樹), 把它換到前驅結點的位置(右邊)
		delete pre;							 // 把前驅删掉即可
		return;
	}

	// 其它兩種情況
	BSTree to_replace = nullptr;
	if (!target->lchild) // 如果要被删除的結點沒有左子樹, 用其右子樹代替它的位置
		to_replace = target->rchild;
	else if (!target->rchild) // 如果沒有右子樹, 用左子樹代替它的位置
		to_replace = target->lchild;

	if (!parent) // 沒有父節點就取代根結點位置
		T = to_replace;
	else if (target == parent->lchild) // 如果要被删除的結點是左邊的
		parent->lchild = to_replace;   // 取代左邊的位置
	else if (target == parent->rchild) // 如果被删除結點是右邊的
		parent->rchild = to_replace;   // 取代右邊的位置

	delete target; // 删掉目标結點
}

// 中序周遊
void InOrderTraverse(BSTree &T)
{
	if (T)
	{
		InOrderTraverse(T->lchild);
		cout << T->data.key << '\t';
		InOrderTraverse(T->rchild);
	}
}

int main()
{
	BSTree T;
	cout << "請輸入若幹字元(#表示輸入結束): ";
	CreateBST(T);
	cout << "中序周遊結果為" << endl;
	InOrderTraverse(T);
	cout << endl;

	char key; //待查找或待删除内容
	cout << "請輸入待查找字元: ";
	cin >> key;
	if (SearchBST(T, key))
		cout << "找到字元" << key << endl;
	else
		cout << "未找到" << key << endl;

	cout << "請輸入待删除的字元: ";
	cin >> key;
	DeleteBST(T, key);
	cout << "中序周遊結果為" << endl;
	InOrderTraverse(T);
	cout << endl;
}
           

截圖