【数据结构】二叉树及其应用

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

1、DS二叉树—二叉树构建与遍历(不含框架)

题目描述

给定一颗二叉树的逻辑结构如下图,(先序遍历的结果,空树用字符‘#’表示,例如AB#C##D##),建立该二叉树的二叉链式存储结构,并输出该二叉树的先序遍历、中序遍历和后序遍历结果。
在这里插入图片描述

输入

第一行输入一个整数t,表示有t个二叉树
第二行起输入每个二叉树的先序遍历结果,空树用字符‘#’表示,连续输入t行。

输出

输出每个二叉树的先序遍历、中序遍历和后序遍历结果。

样例输入

2
AB#C##D##
AB##C##

样例输出

ABCD
BCAD
CBDA
ABC
BAC
BCA

题解

#include<iostream>
using namespace std;

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

void Create_BTree(BTree*& 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);
	}
}

void PreShow_BTree(BTree* t)                 //先序遍历输出二叉树
{
	if (t != NULL)
	{
		cout << t->data;
		PreShow_BTree(t->LChild);
		PreShow_BTree(t->RChild);
	}
}

void InShow_BTree(BTree* t)                 //先序遍历输出二叉树
{
	if (t != NULL)
	{		
		InShow_BTree(t->LChild);
		cout << t->data;
		InShow_BTree(t->RChild);
	}
}

void PostShow_BTree(BTree* t)                 //先序遍历输出二叉树
{
	if (t != NULL)
	{
		PostShow_BTree(t->LChild);
		PostShow_BTree(t->RChild);
		cout << t->data;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree* root;
		Create_BTree(root);
		PreShow_BTree(root);
		cout << endl;
		InShow_BTree(root);
		cout << endl;
		PostShow_BTree(root);
		cout << endl;
	}
	
	return 0;
}

2、DS二叉树——二叉树之数组存储

题目描述

二叉树可以采用数组的方法进行存储,把数组中的数据依次自上而下,自左至右存储到二叉树结点中,一般二叉树与完全二叉树对比,比完全二叉树缺少的结点就在数组中用0来表示。,如下图所示
在这里插入图片描述从上图可以看出,右边的是一颗普通的二叉树,当它与左边的完全二叉树对比,发现它比完全二叉树少了第5号结点,所以在数组中用0表示,同样它还少了完全二叉树中的第10、11号结点,所以在数组中也用0表示。
结点存储的数据均为非负整数

输入

第一行输入一个整数t,表示有t个二叉树
第二行起,每行输入一个数组,先输入数组长度,再输入数组内数据,每个数据之间用空格隔开,输入的数据都是非负整数
连续输入t行

输出

每行输出一个示例的先序遍历结果,每个结点之间用空格隔开

样例输入

3
3 1 2 3
5 1 2 3 0 4
13 1 2 3 4 0 5 6 7 8 0 0 9 10

样例输出

1 2 3
1 2 4 3
1 2 4 7 8 3 5 9 10 6

题解

#include<iostream>
using namespace std;

class BTree {
	int num;
	int* Tree;
public:
	BTree() {
		cin >> num;
		Tree = new int[num];
		for (int i = 0; i < num; i++)
			cin >> Tree[i];
	}
	void show(int i) {
		if (Tree[i] != 0 && i < num) {
			cout << Tree[i] << ' ';
			show(2 * i + 1);
			show(2 * i + 2);
		}
	}
};

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

3、DS二叉树–叶子数量

题目描述

计算一颗二叉树包含的叶子结点数量。
提示:叶子是指它的左右孩子为空。
建树方法采用“先序遍历+空树用0表示”的方法,即给定一颗二叉树的先序遍历的结果为AB0C00D00,其中空节点用字符‘0’表示。则该树的逻辑结构如下图。
在这里插入图片描述

输入

第一行输入一个整数t,表示有t个测试数据
第二行起输入二叉树先序遍历的结果,空树用字符‘0’表示,输入t行

输出

逐行输出每个二叉树的包含的叶子数量

样例输入

3
AB0C00D00
AB00C00
ABC00D00E00

样例输出

2
2
3

题解

#include<iostream>
using namespace std;

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

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

void PreShow_BTree(BTree* t) 
{
	if (t != NULL)
	{
		cout << t->data;
		PreShow_BTree(t->LChild);
		PreShow_BTree(t->RChild);
	}
}

void count(BTree* t, int& num) {
	if (t != NULL)
	{
		if (t->LChild == NULL && t->RChild == NULL)
			num++;
		count(t->LChild, num);
		count(t->RChild, num);
	}
	
}


int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree* root;
		Create_BTree(root);
		int num = 0;
		count(root, num);
		cout << num << endl;
	}
	return 0;
}

4、DS二叉树–左叶子数量

题目描述

计算一颗二叉树包含的叶子结点数量。
左叶子是指它的左右孩子为空,而且它是父亲的左孩子
提示:可以用三叉链表法,也可以用现有算法对两层结点进行判断
建树方法采用“先序遍历+空树用0表示”的方法

输入

第一行输入一个整数t,表示有t个测试数据
第二行起输入二叉树先序遍历的结果,空树用字符‘0’表示,输入t行

输出

逐行输出每个二叉树的包含的左叶子数量

样例输入

3
AB0C00D00
AB00C00
ABCD0000EF000

样例输出

0
1
2

题解

#include<iostream>
using namespace std;

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

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

void PreShow_BTree(BTree* t)
{
	if (t != NULL)
	{
		cout << t->data;
		PreShow_BTree(t->LChild);
		PreShow_BTree(t->RChild);
	}
}

void count(BTree* t, int& num) {
	if (t != NULL)
	{
		if (t->LChild != NULL)
			if (t->LChild->LChild == NULL && t->LChild->RChild == NULL)
				num++;
		count(t->LChild, num);
		count(t->RChild, num);
	}
	
}


int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree* root;
		Create_BTree(root);
		int num = 0;
		count(root, num);
		cout << num << endl;
	}
	return 0;
}

5、DS二叉树——二叉树之父子结点

题目描述

给定一颗二叉树的逻辑结构如下图,(先序遍历的结果,空树用字符‘0’表示,例如AB0C00D00),建立该二叉树的二叉链式存储结构。
编写程序输出该树的所有叶子结点和它们的父亲结点
在这里插入图片描述

输入

第一行输入一个整数t,表示有t个二叉树
第二行起,按照题目表示的输入方法,输入每个二叉树的先序遍历,连续输入t行

输出

第一行按先序遍历,输出第1个示例的叶子节点
第二行输出第1个示例中与叶子相对应的父亲节点
以此类推输出其它示例的结果

样例输入

3
AB0C00D00
AB00C00
ABCD0000EF000

样例输出

C D
B A
B C
A A
D F
C E

题解

#include<iostream>
using namespace std;

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

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

void PreShow_BTree(BTree* t)
{
	if (t != NULL)
	{
		cout << t->data;
		PreShow_BTree(t->LChild);
		PreShow_BTree(t->RChild);
	}
}

void print_leaf(BTree* t) {
	if (t != NULL)
	{
		if (t->LChild == NULL && t->RChild == NULL)
			cout << t->data << ' ';
		print_leaf(t->LChild);
		print_leaf(t->RChild);
	}	
}

void print_father_leaf(BTree* t) {
	if (t != NULL)
	{
		
		print_father_leaf(t->LChild);
		print_father_leaf(t->RChild);
		if (t->LChild != NULL) {
			if (t->LChild->LChild == NULL && t->LChild->RChild == NULL)
				cout << t->data << ' ';
		}
		if (t->RChild != NULL) {
			if (t->RChild->LChild == NULL && t->RChild->RChild == NULL)
				cout << t->data << ' ';
		}
	}
}


int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree* root;
		Create_BTree(root);
		print_leaf(root);
		cout << endl;
		print_father_leaf(root);
		cout << endl;
	}
	return 0;
}

6、DS二叉树–层次遍历

题目描述

层次遍历二叉树,是从根结点开始遍历,按层次次序“自上而下,从左至右”访问树中的各结点。
建树方法采用“先序遍历+空树用0表示”的方法
要求:采用队列对象实现,函数框架如下:
在这里插入图片描述

输入

第一行输入一个整数t,表示有t个测试数据
第二行起输入二叉树先序遍历的结果,空树用字符‘0’表示,输入t行

输出

逐行输出每个二叉树的层次遍历结果

样例输入

2
AB0C00D00
ABCD00E000FG00H0I00

样例输出

ABDC
ABFCGHDEI

题解

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

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

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

void PreShow_BTree(BTree* t)
{
	if (t != NULL)
	{
		cout << t->data;
		PreShow_BTree(t->LChild);
		PreShow_BTree(t->RChild);
	}
}

void print_leaf(BTree* t) {
	if (t != NULL)
	{
		if (t->LChild == NULL && t->RChild == NULL)
			cout << t->data << ' ';
		print_leaf(t->LChild);
		print_leaf(t->RChild);
	}	
}

void print_father_leaf(BTree* t) {
	if (t != NULL)
	{
		
		print_father_leaf(t->LChild);
		print_father_leaf(t->RChild);
		if (t->LChild != NULL) {
			if (t->LChild->LChild == NULL && t->LChild->RChild == NULL)
				cout << t->data << ' ';
		}
		if (t->RChild != NULL) {
			if (t->RChild->LChild == NULL && t->RChild->RChild == NULL)
				cout << t->data << ' ';
		}
	}
}

queue<char> q;

void level_order(BTree* t) {
	queue<BTree_node*> tq;
	BTree_node* p = t;
	if (p) {
		tq.push(p);
		while (!tq.empty())
		{
			p = tq.front();
			tq.pop();
			cout << p->data;
			if (p->LChild)
				tq.push(p->LChild);
			if (p->RChild)
				tq.push(p->RChild);
		}
	}
}

void show_level_order(BTree* t) {
	level_order(t);
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		BTree* root;
		Create_BTree(root);
		show_level_order(root);
		cout << endl;
	}
	return 0;
}

0

评论区