数据结构OJ实验6-二叉树的遍历以及应用

A. DS二叉树—二叉树构建与遍历（不含框架）

题目描述

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘#’表示，例如AB#C##D##），建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果。

输入

第一行输入一个整数t，表示有t个二叉树

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

输出

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

样例查看模式?

正常显示查看格式

输入样例1

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

输出样例1

ABCD
BCAD
CBDA
ABC
BAC
BCA

AC代码

#include<iostream>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用！
	{
		char ch;
		cin >> ch;
		if (ch == '#')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new！
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.preorder();
		tt.midorder();
		tt.posorder();
	}
	return 0;
}

B. DS二叉树--叶子数量

题目描述

计算一颗二叉树包含的叶子结点数量。

提示：叶子是指它的左右孩子为空。

建树方法采用“先序遍历+空树用0表示”的方法，即给定一颗二叉树的先序遍历的结果为AB0C00D00，其中空节点用字符‘0’表示。则该树的逻辑结构如下图。

输入

第一行输入一个整数t，表示有t个测试数据

第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出

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

样例查看模式?

正常显示查看格式

输入样例1?

3
AB0C00D00
AB00C00
ABC00D00E00

输出样例1

2
2
3

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        int index=0;
        int cnt=0;
        while(index<(int)s.length()-2)//注意长度范围
        {
            //使用左右两边都无来判断是不是叶子
            if(s[index]!='0'&&s[index+1]=='0'&&s[index+2]=='0')
            {
                index+=2;
                cnt++;
            }
            else index++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

C. DS二叉树——二叉树之父子结点

题目描述

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。

编写程序输出该树的所有叶子结点和它们的父亲结点

输入

第一行输入一个整数t，表示有t个二叉树

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

输出

第一行按先序遍历，输出第1个示例的叶子节点

第二行输出第1个示例中与叶子相对应的父亲节点

以此类推输出其它示例的结果

样例查看模式?

正常显示查看格式

输入样例1?

3
AB0C00D00
AB00C00
ABCD0000EF000

输出样例1

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

AC代码

#include<iostream>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用！
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new！
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		//按照先序遍历
		if (!n->l &&!n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		//按照后序遍历
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		//左右节点的父亲相同
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.child();
		tt.father();
	}
	return 0;
}

D. DS二叉树--层次遍历

题目描述

层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。

建树方法采用“先序遍历+空树用0表示”的方法

建议使用队列结构实现，算法框架如下：

定义一个空白队列和一个树结点指针p

设T是指向根结点的指针变量，若二叉树为空，则返回；否则，令p=T，p入队，执行以下循环：

(1)队首元素出队到p；

(2)访问p所指向的结点；?

(3)p所指向的结点的左、右子结点依次入队。

(4)跳转步骤1循环，直到队列空为止

例如把上述算法中的访问操作定义为输出，算法结果就是把二叉树按层次遍历输出

输入

第一行输入一个整数t，表示有t个测试数据

第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出

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

样例查看模式?

正常显示查看格式

输入样例1?

2
AB0C00D00
ABCD00E000FG00H0I00

输出样例1

ABDC
ABFCGHDEI

AC代码

#include<iostream>
#include<queue>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用！
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new！
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		//按照先序遍历
		if (!n->l &&!n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		//按照后序遍历
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		//左右节点的父亲相同
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
	void lerorder()
	{
		queue<node*>q;
		q.push(root);
		while (!q.empty())
		{
			auto t = q.front();
			q.pop();
			if (!t)continue;//注意判断非空
			cout << t->data;
			q.push(t->l);
			q.push(t->r);
		}
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.lerorder();
	}
	return 0;
}

E. DS树--二叉树高度

题目描述

给出一棵二叉树，求它的高度。

注意，二叉树的层数是从1开始

输入

第一行输入一个整数t，表示有t个二叉树

第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出

每行输出一个二叉树的高度

样例查看模式?

正常显示查看格式

输入样例1?

1
AB0C00D00

输出样例1

3

AC代码

#include<iostream>
#include<queue>
using namespace std;
struct node
{
	node* l;
	node* r;
	char data;
	node(char d,node*ll=NULL,node*rr=NULL)
	{
		data = d;
		l = ll;
		r = rr;
	}
};
class tree
{
	node* root;
	void Create(node*& n)//记住创建树的时候要加引用！
	{
		char ch;
		cin >> ch;
		if (ch == '0')
		{
			n = NULL;
			return;
		}
		n = new node(ch);//记得要用new！
		Create(n->l);
		Create(n->r);
	}
	void Delete(node* n)
	{
		if (!n)
		{
			delete n;
			return;
		}
		Delete(n->l);
		Delete(n->r);
		delete n;
	}
	void Pre(node* n)
	{
		if (!n)return;
		cout << n->data;
		Pre(n->l);
		Pre(n->r);
	}
	void Mid(node* n)
	{
		if (!n)return;
		Mid(n->l);
		cout << n->data;
		Mid(n->r);
	}
	void Pos(node* n)
	{
		if (!n)return;
		Pos(n->l);
		Pos(n->r);
		cout << n->data;
	}
	void Child(node* n)
	{
		if (!n)return;
		//按照先序遍历
		if (!n->l &&!n->r)
		{
			cout << n->data << " ";
		}
		Child(n->l);
		Child(n->r);
	}
	void Fath(node* n)
	{
		if (!n)return;
		Fath(n->l);
		Fath(n->r);
		//按照后序遍历
		if (n->l && !(n->l->l) && !(n->l->r))
		{
			cout << n->data << " ";
		}
		//左右节点的父亲相同
		if (n->r && !(n->r->l) && !(n->r->r))
		{
			cout << n->data << " ";
		}
	}
	int high(node* n)
	{
		if (!n)return 0;
		int lefth = high(n->l);
		int righth = high(n->r);
		return max(lefth, righth) + 1;
	}
public:
	tree()
	{
		root = NULL;
	}
	void createtree()
	{
		Create(root);
	}
	~tree()
	{
		Delete(root);
	}
	void preorder()
	{
		Pre(root);
	     cout << endl;
	}
	void midorder()
	{
		Mid(root);
		cout << endl;
	}
	void posorder()
	{
		Pos(root);
		cout << endl;
	}
	void child()
	{
		Child(root);
		cout << endl;
	}
	void father()
	{
		Fath(root);
		cout << endl;
	}
	void lerorder()
	{
		queue<node*>q;
		q.push(root);
		while (!q.empty())
		{
			auto t = q.front();
			q.pop();
			if (!t)continue;//注意判断非空
			cout << t->data;
			q.push(t->l);
			q.push(t->r);
		}
		cout << endl;
	}
	void gethigh()
	{
		cout << high(root) << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.createtree();
		tt.gethigh();
	}
	return 0;
}

F. DS二叉树——二叉树之数组存储

题目描述

二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示。，如下图所示

从上图可以看出，右边的是一颗普通的二叉树，当它与左边的完全二叉树对比，发现它比完全二叉树少了第5号结点，所以在数组中用0表示，同样它还少了完全二叉树中的第10、11号结点，所以在数组中也用0表示。

结点存储的数据均为非负整数

输入

第一行输入一个整数t，表示有t个二叉树

第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数

连续输入t行

输出

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

样例查看模式?

正常显示查看格式

输入样例1?

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

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

提示

注意从数组位置和二叉树深度、结点位置进行关联，或者父子结点在数组中的位置存在某种管理，例如i, i+1, i/2, ?i+1/2........或者2i, 2i+1.......仔细观察哦

AC代码

#include<iostream>
#include<vector>
using namespace std;
class tree
{
	vector<int>node;
	void pre(int idx)
	{
		if (idx>=node.size()||node[idx]==0)return;
		cout << node[idx] << " ";
		pre(2 * idx + 1);//左
		pre(2 * idx + 2);//右
	}
public:
	tree()
	{
		int n;
		cin >> n;
		node.resize(n);
		for (int i = 0; i < n; i++)cin >> node[i];
	}
	void preorder()
	{
		pre(0);//下标从0开始
		cout << endl;
	}
};
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		tree tt;
		tt.preorder();
	}
	return 0;
}