数据结构-二叉排序树操作实践

数据结构-二叉排序树操作实践

编写函数，建立有序表，利用二叉排序树的插入算法建立二叉排序树

#include<iostream>
#include<malloc.h>
using namespace std;
#define MAXSIZE 50
// 定义二叉树的结点
typedef struct BiTNode {
   
	int data;
	struct BiTNode* lChild, * rChild;
}BiTNode, *BiTree;


/** * 在二叉排序树T中插入一个关键字为k的结点 * @param T 二叉排序树T * @param k 要插入的关键字k * @return 成功返回真，否则为假 */
bool BST_Insert(BiTree& T, int k) {
   
	if (T == NULL) {
     // 原数为空，新插入的记录为根结点
		T = (BiTree)malloc(sizeof(BiTNode));
		if (T) {
   
			T->data = k;
			T->lChild = T->rChild = NULL;
			return true;  // 成功
		}
	}
	else if (k == T->data)  // 树中存在相同关键字的结点
		return false;
	else if (k < T->data)  // 插入T的左子树
		return BST_Insert(T->lChild, k);
	else   // 插入T的右子树
		return BST_Insert(T->rChild, k);
}

/** * 用关键字数组构造二叉排序树 * @param T 二叉排序树T * @param keys 关键字数组 * @param n 关键字数组的元素个数 */
void Creat_BST(BiTree& T, int keys[], int n) {
   
	T = NULL;  // 初始化为空树
	int i = 0;
	while (i < n) {
     // 将为每个元素依次插入
		BST_Insert(T, keys[i]);
		i++;
	}
}

/** * 先序遍历二叉排序树 * @param T 二叉排序树T */
void PreOrder_BST(BiTree T) {
   
	if (T != NULL) {
   
		cout << T->data << " ";
		PreOrder_BST(T->lChild);
		PreOrder_BST(T->rChild);
	}
}

/** * 中序遍历二叉排序树 * @param T 二叉排序树T */
void InOrder_BST(BiTree T) {
   
	if (T != NULL) {
   
		InOrder_BST(T->lChild);
		cout << T->data << " ";
		InOrder_BST(T->rChild);
	}
}

/** * 后序遍历二叉排序树 * @param T 二叉排序树T */
void PostOrder_BST(BiTree T) {
   
	if (T != NULL) {
   
		PostOrder_BST(T->lChild);
		PostOrder_BST(T->rChild);
		cout << T->data << " ";
	}
}

int main() {
   
	int n;
	cin >> n;

	int keys[MAXSIZE];
	for (int i = 0; i < n; i++)
		cin >> keys[i];

	BiTree T;
	Creat_BST(T, keys, n);

	cout << "先序遍历：";
	PreOrder_BST(T);
	cout << endl;
	
	cout << "中序遍历：";
	InOrder_BST(T);
	cout << endl;

	cout << "后序遍历：";
	PostOrder_BST(T);
	cout << endl;

	return 0;
}

注：

  • 二叉排序树中默认没有相同的元素
  • 输入的顺序是随意的，自己可以手动的根据输入的顺序构造二叉排序树，再对该二叉排序树进行先、中、后序遍历，跟输出的遍历结果对照，即可判断程序所构造的二叉排序树是否正确。

在以上二叉排序树中删除某一指定关键字元素

/** * 从二叉排序树中删除结点p，并重接它的左或右子树 * @param p 要删除的结点 * @return 成功为真 */
bool Delete(BiTree& p) {
   
	BiTree q, s;
	if (!p->rChild) {
     // 右子树为空，则只需要重接它的左子树
		q = p;
		p = p->lChild;
		free(q);
	}
	else if (!p->lChild) {
     // 左子树为空，则只需要重接它的右子树
		q = p;
		p = p->rChild;
		free(q);
	}
	else {
     // 左右子树均不为空
		q = p;
		s = p->lChild;
		while (s->rChild) {
     // 转左，然后向右到尽头
			q = s;
			s = s->rChild;
		}
		p->data = s->data;  // s指向被删结点的前驱
		if (q != p)  // 重接*q的右子树
			q->rChild = s->lChild;
		else  // 重接*q的左子树
			q->lChild = s->rChild;
		free(s);
	}
	return true;
}
/** * 在二叉排序树中删除关键字等于key的结点 * @param T 二叉排序树T * @param key 要删除的关键字元素 * @return 成功返回真，否则返回假 */
bool DeleteBST(BiTree& T, int key) {
   
	if (!T)  // T为空
		return false;
	else
	{
   
		if (key == T->data)  //找到关键字等于key的数据元素
			return Delete(T);
		else if (key < T->data)
			return DeleteBST(T->lChild, key);
		else
			return DeleteBST(T->rChild, key);
	}
}

int key;
cin >> key;
DeleteBST(T, key);
cout << "------删除" << key << "------" << endl;

cout << "先序遍历：";
PreOrder_BST(T);
cout << endl;

cout << "中序遍历：";
InOrder_BST(T);
cout << endl;

cout << "后序遍历：";
PostOrder_BST(T);
cout << endl;

注：

  • 二叉排序树中默认没有相同的元素
  • 输入的顺序是随意的，自己可以手动的根据输入的顺序构造二叉排序树，再对该二叉排序树进行先、中、后序遍历，跟输出的遍历结果对照，即可判断程序所构造的二叉排序树是否正确。
  • 在二叉排序树中删除元素是一件比较麻烦的事，根据不同的情况，在删除后要对树进行不同的调整。

采用折半查找实现某一已知的关键字的查找（采用顺序表存储结构）

这里继续基于上面的程序来写，显然，二叉排序树的中序遍历即为一个递增的顺序。我们利用中序遍历来构造一个顺序表，再进行折半查找操作

int SeqT[MAXSIZE];  // 定义一个顺序表，用于折半查找
int t=0;

/** * 中序遍历二叉排序树 * @param T 二叉排序树T */
void InOrder_BST(BiTree T) {
   
	if (T != NULL) {
   
		InOrder_BST(T->lChild);
		cout << T->data << " ";
		SeqT[t++] = T->data;  // 按中序遍历的方式遍历二叉排序树即可得到一组有序的数
		InOrder_BST(T->rChild);
	}
}

/** * 折半查找 * @param SeqT 有序表 * @param n 有序表中元素个数 * @param key 待查找的关键字 * @return 该关键字在表中的位置（第几个），否则返回0 */
int Search_Bin(int SeqT[], int n, int key) {
   
	int low = 0;
	int high = n - 1;
	int mid;
	while (low <= high) {
   
		mid = (low + high) / 2;
		if (key == SeqT[mid])  // 找到待查元素
			return mid + 1;
		else if (key < SeqT[mid])  // 继续在前半区间查找
			high = mid - 1;
		else  // 继续在后半区间查找
			low = mid + 1;
	}
	return 0;  // 有序表中不存在待查元素
}

int key2;
cin >> key2;
cout << key2 << "在表中第" << Search_Bin(SeqT, n, key2) << "个位置";

完成程序代码

#include<iostream>
#include<malloc.h>
using namespace std;
#define MAXSIZE 50
int SeqT[MAXSIZE];  // 定义一个顺序表，用于折半查找
int t=0;

// 定义二叉树的结点
typedef struct BiTNode {
   
	int data;
	struct BiTNode* lChild, * rChild;
}BiTNode, *BiTree;


/** * 在二叉排序树T中插入一个关键字为k的结点 * @param T 二叉排序树T * @param k 要插入的关键字k * @return 成功返回真，否则为假 */
bool BST_Insert(BiTree& T, int k) {
   
	if (T == NULL) {
     // 原数为空，新插入的记录为根结点
		T = (BiTree)malloc(sizeof(BiTNode));
		if (T) {
   
			T->data = k;
			T->lChild = T->rChild = NULL;
			return true;  // 成功
		}
	}
	else if (k == T->data)  // 树中存在相同关键字的结点
		return false;
	else if (k < T->data)  // 插入T的左子树
		return BST_Insert(T->lChild, k);
	else   // 插入T的右子树
		return BST_Insert(T->rChild, k);
}

/** * 用关键字数组构造二叉排序树 * @param T 二叉排序树T * @param keys 关键字数组 * @param n 关键字数组的元素个数 */
void Creat_BST(BiTree& T, int keys[], int n) {
   
	T = NULL;  // 初始化为空树
	int i = 0;
	while (i < n) {
     // 将为每个元素依次插入
		BST_Insert(T, keys[i]);
		i++;
	}
}

/** * 先序遍历二叉排序树 * @param T 二叉排序树T */
void PreOrder_BST(BiTree T) {
   
	if (T != NULL) {
   
		cout << T->data << " ";
		PreOrder_BST(T->lChild);
		PreOrder_BST(T->rChild);
	}
}

/** * 中序遍历二叉排序树 * @param T 二叉排序树T */
void InOrder_BST(BiTree T) {
   
	if (T != NULL) {
   
		InOrder_BST(T->lChild);
		cout << T->data << " ";
		SeqT[t++] = T->data;  // 按中序遍历的方式遍历二叉排序树即可得到一组有序的数
		InOrder_BST(T->rChild);
	}
}

/** * 后序遍历二叉排序树 * @param T 二叉排序树T */
void PostOrder_BST(BiTree T) {
   
	if (T != NULL) {
   
		PostOrder_BST(T->lChild);
		PostOrder_BST(T->rChild);
		cout << T->data << " ";
	}
}


/** * 从二叉排序树中删除结点p，并重接它的左或右子树 * @param p 要删除的结点 * @return 成功为真 */
bool Delete(BiTree& p) {
   
	BiTree q, s;
	if (!p->rChild) {
     // 右子树为空，则只需要重接它的左子树
		q = p;
		p = p->lChild;
		free(q);
	}
	else if (!p->lChild) {
     // 左子树为空，则只需要重接它的右子树
		q = p;
		p = p->rChild;
		free(q);
	}
	else {
     // 左右子树均不为空
		q = p;
		s = p->lChild;
		while (s->rChild) {
     // 转左，然后向右到尽头
			q = s;
			s = s->rChild;
		}
		p->data = s->data;  // s指向被删结点的前驱
		if (q != p)  // 重接*q的右子树
			q->rChild = s->lChild;
		else  // 重接*q的左子树
			q->lChild = s->rChild;
		free(s);
	}
	return true;
}
/** * 在二叉排序树中删除关键字等于key的结点 * @param T 二叉排序树T * @param key 要删除的关键字元素 * @return 成功返回真，否则返回假 */
bool DeleteBST(BiTree& T, int key) {
   
	if (!T)  // T为空
		return false;
	else
	{
   
		if (key == T->data)  //找到关键字等于key的数据元素
			return Delete(T);
		else if (key < T->data)
			return DeleteBST(T->lChild, key);
		else
			return DeleteBST(T->rChild, key);
	}
}

/** * 折半查找 * @param SeqT 有序表 * @param n 有序表中元素个数 * @param key 待查找的关键字 * @return 该关键字在表中的位置（第几个），否则返回0 */
int Search_Bin(int SeqT[], int n, int key) {
   
	int low = 0;
	int high = n - 1;
	int mid;
	while (low <= high) {
   
		mid = (low + high) / 2;
		if (key == SeqT[mid])  // 找到待查元素
			return mid + 1;
		else if (key < SeqT[mid])  // 继续在前半区间查找
			high = mid - 1;
		else  // 继续在后半区间查找
			low = mid + 1;
	}
	return 0;  // 有序表中不存在待查元素
}


int main() {
   
	int n;
	cin >> n;

	int keys[MAXSIZE];
	for (int i = 0; i < n; i++)
		cin >> keys[i];

	BiTree T;
	Creat_BST(T, keys, n);

	cout << "先序遍历：";
	PreOrder_BST(T);
	cout << endl;
	
	cout << "中序遍历：";
	InOrder_BST(T);
	cout << endl;

	cout << "后序遍历：";
	PostOrder_BST(T);
	cout << endl;

	int key;
	cin >> key;
	DeleteBST(T, key);
	cout << "------删除" << key << "------" << endl;

	cout << "先序遍历：";
	PreOrder_BST(T);
	cout << endl;

	cout << "中序遍历：";
	InOrder_BST(T);
	cout << endl;

	cout << "后序遍历：";
	PostOrder_BST(T);
	cout << endl;

	int key2;
	cin >> key2;
	cout << key2 << "在表中第" << Search_Bin(SeqT, n, key2) << "个位置";

	return 0;
}

创作不易，喜欢的话加个关注点个赞，谢谢谢谢谢！

全部评论

相关推荐

11-16 00:02
阿里云_前端
点赞 评论 收藏
分享
11-18 12:05
华中科技大学 Java
点赞 评论 收藏
分享
11-15 18:12
北京航空航天大学 算法工程师
点赞 评论 收藏
分享
头像
11-11 15:50
西安科技大学 测试工程师
这给我整不会了😠
找不到工作死了算了：没事的，雨英，hr肯主动告知结果已经超越大部分hr了
点赞 评论 收藏
分享
11-20 08:16
华为_算法工程师
学历垫底，绩效拿A，在华为是什么体验？
学历垫底，绩效拿A，在华为是什么体验？本文是2024年11月2日公众号来知晓原创首发文章。我两手空空，但可以打败风。——少年，郑皓元，8岁读者朋友你好，欢迎来到来知晓。本期继续聊聊职场成长话题，分享下我在华为绩效拿A的工作体验和几点思考。在菊厂，为啥要积极冲击拿A？一方面，菊厂一直鼓励拉开差距，鼓励火车头文化，老板官宣火车跑得快，全靠车头带。于是，体现在各种激励、荣誉上都有较大区别。另一方面，如果你享受这种竞争机制，带来的个人成长的话，应该也会主动想去冲击绩效A。举个实例，我问上期提到的那位清华同事H，你来我司后感觉压力咋样？同事H说，我来还是想要有点压力的，不然不会来华为了。我不由想，积极主...
华为工作强度 796人发布 华子oc时间线 机械人还在等华为开奖吗？
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
248194次浏览 2013人参与
# 学历or实习经历，哪个更重要 #
41120次浏览 300人参与
# 北方华创开奖 #
22828次浏览 259人参与
# 地方国企笔面经互助 #
2558次浏览 6人参与
# 你最想要的公司福利是？ #
40055次浏览 126人参与
# 选完offer后，你后悔学本专业吗 #
10495次浏览 75人参与
# 面试题刺客退退退 #
137195次浏览 2092人参与
# 国企/银行/研究所公司爆料 #
89746次浏览 412人参与
# 应届生被毁约被毁意向了怎么办 #
27175次浏览 238人参与
# 一觉醒来，我觉醒了超级打工人系统 #
2910次浏览 35人参与
# 机械应届生薪资要多少才合适？ #
12397次浏览 60人参与
# 查收我的offer竞争力报告 #
16838次浏览 228人参与
# 校招入职后的感受 #
156970次浏览 1961人参与
# 你觉得第一学历对求职有影响吗？ #
14896次浏览 121人参与
# 没有实习经历，还有机会进大厂吗 #
805163次浏览 13814人参与
# 我的工作日记 #
21208次浏览 270人参与
# 不给转正的实习，你还去吗 #
1517108次浏览 16968人参与
# 寒假躺平还是提前实习 #
58454次浏览 438人参与
# 总结:哪家公司面试体验感最差 #
25771次浏览 129人参与
# 秋招OC许愿 #
226703次浏览 1872人参与
# 如何写一份好简历 #
602261次浏览 8442人参与
牛客网
牛客企业服务