【数据结构】二叉排序树

Alex_Shen
2020-12-16 / 0 评论 / 0 点赞 / 82 阅读 / 7,950 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-04-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

问题 A: DS二叉排序树之创建和插入

题目描述

给出一个数据序列,建立二叉排序树,并实现插入功能
对二叉排序树进行中序遍历,可以得到有序的数据序列

输入

第一行输入t,表示有t个数据序列
第二行输入n,表示首个序列包含n个数据
第三行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第四行输入m,表示要插入m个数据
从第五行起,输入m行,每行一个要插入的数据,都是自然数且和前面的数据不等
以此类推输入下一个示例

输出

第一行输出有序的数据序列,对二叉排序树进行中序遍历可以得到
从第二行起,输出插入第m个数据后的有序序列,输出m行
以此类推输出下一个示例的结果

样例输入

1
6
22 33 55 66 11 44
3
77
50
10

样例输出

11 22 33 44 55 66
11 22 33 44 55 66 77
11 22 33 44 50 55 66 77
10 11 22 33 44 50 55 66 77

题解

#include<iostream>
using namespace std;

class node {
public:
	int key;
	node* lchild;
	node* rchild;
	node(int e) {
		key = e;
		lchild = NULL;
		rchild = NULL;
	}
};

class BST {
public:
	node* root;
	BST();
	void InsertBST(int e);
	void Show();
	void InorderShow(node* p);
};

BST::BST()
{
	root = NULL;
}

void BST::InsertBST(int e)
{
	node* t = root;
	while (true) {
		if (e < t->key){
			if (t->lchild == NULL) {
				t->lchild = new node(e);
				return;
			}
			else {
				t = t->lchild;
			}
		}
		else {
			if (t->rchild == NULL) {
				t->rchild = new node(e);
				return;
			}
			else {
				t = t->rchild;
			}
		}
	}
}

void BST::Show()
{
	InorderShow(root);
	cout << endl;
}

void BST::InorderShow(node* p)
{
	if (!p)
		return;
	if (p->lchild)
		InorderShow(p->lchild);
	cout << p->key << ' ';
	if (p->rchild)
		InorderShow(p->rchild);

}

int main() {
	int t;
	cin >> t;
	while (t--) {
		BST tree;
		int n;
		cin >> n;
		int num;
		cin >> num;
		n--;
		tree.root = new node(num);
		while (n--) {
			int num;
			cin >> num;
			tree.InsertBST(num);
		}
		tree.Show();
		cin >> n;
		while (n--) {
			int num;
			cin >> num;
			tree.InsertBST(num);
			tree.Show();
		}	

	}
	
	return 0;
}

问题 B: DS二叉排序树之查找

题目描述

给出一个数据序列,建立二叉排序树,并实现查找功能
对二叉排序树进行中序遍历,可以得到有序的数据序列

输入

第一行输入t,表示有t个数据序列
第二行输入n,表示首个序列包含n个数据
第三行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第四行输入m,表示要查找m个数据
从第五行起,输入m行,每行一个要查找的数据,都是自然数
以此类推输入下一个示例

输出

第一行输出有序的数据序列,对二叉排序树进行中序遍历可以得到
从第二行起,输出查找结果,如果查找成功输出查找次数,如果查找失败输出-1
以此类推输出下一个示例的结果

样例输入

1
6
22 33 55 66 11 44
7
11
22
33
44
55
66
77

样例输出

11 22 33 44 55 66
2
1
2
4
3
4
-1

题解

#include<iostream>
using namespace std;

class node {
public:
	int key;
	node* lchild;
	node* rchild;
	node(int e) {
		key = e;
		lchild = NULL;
		rchild = NULL;
	}
};

class BST {
public:
	node* root;
	BST();
	void InsertBST(int e);
	void Show();
	void Search(int e);
	void InorderShow(node* p);
};

BST::BST()
{
	root = NULL;
}

void BST::InsertBST(int e)
{
	node* t = root;
	while (true) {
		if (e < t->key){
			if (t->lchild == NULL) {
				t->lchild = new node(e);
				return;
			}
			else {
				t = t->lchild;
			}
		}
		else {
			if (t->rchild == NULL) {
				t->rchild = new node(e);
				return;
			}
			else {
				t = t->rchild;
			}
		}
	}
}

void BST::Show()
{
	InorderShow(root);
	cout << endl;
}

void BST::Search(int e)
{
	int num = 1;
	node* p = root;
	while (true) {
		if (p == NULL) {
			cout << "-1" << endl;
			return;
		}
		if (e < p->key) {
			p = p->lchild;
			num++;
		}
		else if (e > p->key) {
			p = p->rchild;
			num++;
		}
		else {
			cout << num << endl;
			return;
		}
	}
}

void BST::InorderShow(node* p)
{
	if (!p)
		return;
	if (p->lchild)
		InorderShow(p->lchild);
	cout << p->key << ' ';
	if (p->rchild)
		InorderShow(p->rchild);

}

int main() {
	int t;
	cin >> t;
	while (t--) {
		BST tree;
		int n;
		cin >> n;
		int num;
		cin >> num;
		n--;
		tree.root = new node(num);
		while (n--) {
			int num;
			cin >> num;
			tree.InsertBST(num);
		}
		tree.Show();
		cin >> n;
		while (n--) {
			int num;
			cin >> num;
			tree.Search(num);
		}	

	}	
	return 0;
}

问题 C: DS二叉排序树之删除

题目描述

给出一个数据序列,建立二叉排序树,并实现删除功能
对二叉排序树进行中序遍历,可以得到有序的数据序列

输入

第一行输入t,表示有t个数据序列
第二行输入n,表示首个序列包含n个数据
第三行输入n个数据,都是自然数且互不相同,数据之间用空格隔开
第四行输入m,表示要删除m个数据
从第五行起,输入m行,每行一个要删除的数据,都是自然数
以此类推输入下一个示例

输出

第一行输出有序的数据序列,对二叉排序树进行中序遍历可以得到
从第二行起,输出删除第m个数据后的有序序列,输出m行
以此类推输出下一个示例的结果

样例输入

1
6
22 33 55 66 11 44
3
66
22
77

样例输出

11 22 33 44 55 66
11 22 33 44 55
11 33 44 55
11 33 44 55

题解

#include<iostream>
using namespace std;

class node {
public:
	int key;
	node* lchild;
	node* rchild;
	node(int e) {
		key = e;
		lchild = NULL;
		rchild = NULL;
	}
};

class BST {
public:
	node* root;
	BST();
	void InsertBST(int e);
	void Show();
	void Search(int e);
	void InorderShow(node* p);
	void Delete(int e);
};

BST::BST()
{
	root = NULL;
}

void BST::InsertBST(int e)
{
	node* t = root;
	while (true) {
		if (e < t->key){
			if (t->lchild == NULL) {
				t->lchild = new node(e);
				return;
			}
			else {
				t = t->lchild;
			}
		}
		else {
			if (t->rchild == NULL) {
				t->rchild = new node(e);
				return;
			}
			else {
				t = t->rchild;
			}
		}
	}
}

void BST::Show()
{
	InorderShow(root);
	cout << endl;
}

void BST::Search(int e)
{
	int num = 1;
	node* p = root;
	while (true) {
		if (p == NULL) {
			cout << "-1" << endl;
			return;
		}
		if (e < p->key) {
			p = p->lchild;
			num++;
		}
		else if (e > p->key) {
			p = p->rchild;
			num++;
		}
		else {
			cout << num << endl;
			return;
		}
	}
}

void BST::InorderShow(node* p)
{
	if (!p)
		return;
	if (p->lchild)
		InorderShow(p->lchild);
	cout << p->key << ' ';
	if (p->rchild)
		InorderShow(p->rchild);

}

void BST::Delete(int e)
{
	node* p = root;
	node* parent = NULL;
	while (true) {
		if (p == NULL)
			return;
		if (e < p->key) {
			parent = p;
			p = p->lchild;
		}
		else if (e > p->key) {
			parent = p;
			p = p->rchild;
		}
		else {
			if (!p->lchild && !p->rchild) {
				if (parent->lchild == p)
					parent->lchild = NULL;
				else if (parent->rchild == p)
					parent->rchild = NULL;
				delete p;
				p = NULL;
			}
			else if (!p->rchild) {
				if (parent->lchild == p)
					parent->lchild = p->lchild;
				else if (parent->rchild == p)
					parent->rchild = p->lchild;
				auto q = p;
				p = p->lchild;
				delete q;
			}
			else if (!p->lchild) {
				if (parent->lchild == p)
					parent->lchild = p->rchild;
				else if (parent->rchild == p)
					parent->rchild = p->rchild;
				auto q = p;
				p = p->rchild;
				delete q;
			}
			else {
				auto q = p;
				auto s = p->lchild;
				while (s->rchild) {
					q = s;
					s = s->rchild;
				}
				p->key = s->key;
				if (q != p)
					q->rchild = s->lchild;
				else
					q->lchild = s->rchild;
				delete s;
			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		BST tree;
		int n;
		cin >> n;
		int num;
		cin >> num;
		n--;
		tree.root = new node(num);
		while (n--) {
			int num;
			cin >> num;
			tree.InsertBST(num);
		}
		tree.Show();
		cin >> n;
		while (n--) {
			int num;
			cin >> num;
			tree.Delete(num);
			tree.Show();
		}	

	}	
	return 0;
}

问题 D: DS查找—二叉树平衡因子

题目描述

二叉树用数组存储,将二叉树的结点数据依次自上而下,自左至右存储到数组中,一般二叉树与完全二叉树对比,比完全二叉树缺少的结点在数组中用0来表示。
计算二叉树每个结点的平衡因子,并按后序遍历的顺序输出结点的平衡因子。
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求

输入

测试次数t
每组测试数据一行,数组元素个数n,后跟n个字符,二叉树的数组存储。

输出

对每组测试数据,按后序遍历的顺序输出树中结点的平衡因子(测试数据没有空树)

样例输入

2
6 ABC00D
24 ABCD0EF0000H00000000000I

样例输出

B 0
D 0
C 1
A -1
D 0
B 1
I 0
H 1
E 2
F 0
C 2
A -2

题解

#include<iostream>
using namespace std;

class BTree {
	int num;
	char* Tree;
	int d;
public:
	BTree() {
		cin >> num;
		Tree = new char[num];
		for (int i = 0; i < num; i++)
			cin >> Tree[i];
	}
	int cal(int i) {
		int num;
		d = 0;
		int d1 = calDepth(2 * i + 1, 0);
		d = 0;
		int d2 = calDepth(2 * i + 2, 0);
		return d1 - d2;
	}
	int calDepth(int i, int n) {
		if (Tree[i] != '0' && i < num) {
			n++;
			if ((Tree[2 * i + 1] == '0' && Tree[2 * i + 2] == '0') || (2 * i + 1 > num && 2 * i + 2 > num)) {
				if (d < n)
					d = n;
			}
			calDepth(2 * i + 1, n);
			calDepth(2 * i + 2, n);
		}
		return d;
	}
	void show(int i) {
		if (Tree[i] != '0' && i < num) {
			show(2 * i + 1);
			show(2 * i + 2);
			cout << Tree[i] << ' ' << cal(i) << ' ' << endl;
		}
	}
};

int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree tree;
		tree.show(0);
	}
	return 0;
}


问题 E: DS二叉树判断--同一棵二叉树?

题目描述

二叉树分别以数组存储方式创建、以先序遍历序列创建。输入二叉树的数组存储、先序遍历结果,判断根据它们创建的二叉树是否是同一棵二叉树。

输入

测试次数t
每组测试数据两行:
第一行:二叉树的数组存储(英文字母表示树结点,#表示空树)
第二行:二叉树的先序遍历结果(英文字母表示树结点,#表示空树)

输出

对每组测试数据,如果两种方式创建的是同一棵二叉树,输出YES,否则,输出NO。

样例输入

3
ABCDE
ABD##E##C##
ABC##DE####W##F
AB##CDW###E#F##
abc##d
ab##c#d##

样例输出

YES
YES
NO

题解

#include<iostream>
#include<queue>
using namespace std;

typedef struct BTree_node {
	char data;
	struct BTree_node* LChild;
	struct BTree_node* RChild;
}BTree_1;

string str2;
string str1;

void Create_BTree(BTree_1*& t)
{
	char s;
	cin >> s;
	if (s == '#')
		t = NULL;
	else
	{
		t = new BTree_node;
		t->data = s;
		Create_BTree(t->LChild);
		Create_BTree(t->RChild);
	}
}

class BTree_B {
	int num;
	char* Tree;
	int d;
public:
	string preorderstr;
	string inorderstr;
	BTree_B() {
		string str;
		cin >> str;
		num = str.size();
		Tree = new char[num];
		for (int i = 0; i < num; i++)
			Tree[i] = str[i];
	}
	void inorder(int i) {
		if (i < num)
		{
			if (Tree[i] != '#')
			{
				inorder(2 * i + 1);
				inorderstr += Tree[i];
				inorder(2 * i + 2);
			}
		}
		return;
	}
	void preorder(int i) {
		if (i < num)
		{
			if (Tree[i] != '#')
			{
				preorderstr += Tree[i];
				preorder(2 * i + 1);
				preorder(2 * i + 2);
			}
		}
		return;
	}
};

void PreShow_BTree(BTree_1* t)
{
	if (t != NULL)
	{
		PreShow_BTree(t->LChild);
		str2.push_back(t->data);
		PreShow_BTree(t->RChild);
	}
}

void InShow_BTree(BTree_1* t)
{
	if (t != NULL)
	{
		str1.push_back(t->data);
		InShow_BTree(t->LChild);
		InShow_BTree(t->RChild);
	}
}

void compare(BTree_B t, BTree_1* root) {
	str1.clear();
	str2.clear();
	t.inorder(0);
	t.preorder(0);
	PreShow_BTree(root);
	InShow_BTree(root);
	if (str1 == t.preorderstr && str2 == t.inorderstr)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree_B tree;
		BTree_1* root;
		Create_BTree(root);
		compare(tree, root);
	}
	return 0;
}


0

评论区