C++数据结构第二次作业

问题 A: 满二叉树的前序遍历

题目描述

给你一个满二叉树的层次遍历序列，请编程输出该二叉树的前序遍历序列。

输入

第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。

输出

输出该满二叉数的前序遍历序列。

样例输入 Copy

3
B A C

样例输出 Copy

BAC

#include
using namespace std;
char TreeNode[27];

void front(int n)
{
	if(TreeNode[n]!=NULL){
	
    cout<>n;
	for(int i=0;i>TreeNode[i];
	}
	front(0);

}

问题 B: 满二叉树的中序遍历

题目描述

给你一个满二叉树的层次遍历序列，请编程输出该二叉树的中序遍历序列。

输入

第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。

输出

输出该满二叉数的中序遍历序列。

样例输入 Copy

3
B A C

样例输出 Copy

ABC

#include
using namespace std;
char TreeNode[27];

void front(int n)
{
	if(TreeNode[n]!=NULL){

	front(2*n+1);//左孩子

    cout<>n;
	for(int i=0;i>TreeNode[i];
	}
	front(0);

}

问题 C: 满二叉树的后序遍历

题目描述

给你一个满二叉树的层次遍历序列，请编程输出该二叉树的后序遍历序列。

输入

第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。

输出

输出该满二叉数的后序遍历序列。

样例输入 Copy

3
B A C

样例输出 Copy

ACB

#include
using namespace std;
char TreeNode[27];

void front(int n)
{
	if(TreeNode[n]!=NULL){

	front(2*n+1);//左孩子
	
	front(2*n+2);//右孩子

    cout<>n;
	for(int i=0;i>TreeNode[i];
	}
	front(0);

}

问题 D: 任意二叉树的前序遍历

题目描述

有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的前序遍历序列。

输入

第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。

输出

输出该二叉数的前序遍历序列。

样例输入 Copy

样例输出 Copy

3 1 2 4

#include
using namespace std;
const int N = 110;//把N拎出来是为了方便改N的值

struct Node //用结构体是因为每一次需要三个数据
{
	int l, r;//left & right
	int val;//代表第一列输入的数据
}a[N];

int n;
bool judge[N];//用来判断该节点是否为根

void front(int u)//其他遍历就改变函数名 和 cout位置
{
	cout << u << " ";
	if (a[u].l != -1) front(a[u].l);
	if (a[u].r != -1) front(a[u].r);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x, l, r;
		cin >> x >> l >> r;
		a[x].l = l;
		a[x].r = r;
		if (l != -1) judge[l] = 1;//证明左孩子不是根
		if (r != -1) judge[r] = 1;//证明右孩子不是根
	}
	int root = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!judge[i]) {//n个编号对应n个位置，该位置没被证明不是根的 即为根（找根）
			root = i;
			break;
		}
	}
	front(root);
	return 0;
}

问题 E: 任意二叉树的中序遍历

题目描述

有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的中序遍历序列。

输入

输出

输出该二叉数的中序遍历序列。

样例输入 Copy

样例输出 Copy

2 1 4 3

#include
using namespace std;
const int N = 110;//把N拎出来是为了方便改N的值

struct Node //用结构体是因为每一次需要三个数据
{
	int l, r;//left & right
	int val;//代表第一列输入的数据
}a[N];

int n;
bool judge[N];//用来判断该节点是否为根

void middle(int u)//其他遍历就改变函数名 和 cout位置
{
	if (a[u].l != -1) middle(a[u].l);
	cout << u << " ";
	if (a[u].r != -1) middle(a[u].r);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x, l, r;
		cin >> x >> l >> r;
		a[x].l = l;
		a[x].r = r;
		if (l != -1) judge[l] = 1;//证明左孩子不是根
		if (r != -1) judge[r] = 1;//证明右孩子不是根
	}
	int root = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!judge[i]) {//n个编号对应n个位置，该位置没被证明不是根的 即为根（找根）
			root = i;
			break;
		}
	}
	middle(root);
	return 0;
}

问题 F: 任意二叉树的后序遍历

题目描述

有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的后序遍历序列。

输入

输出

输出该二叉数的后序遍历序列。

样例输入 Copy

样例输出 Copy

2 4 1 3

#include
using namespace std;
const int N = 110;//把N拎出来是为了方便改N的值

struct Node //用结构体是因为每一次需要三个数据
{
	int l, r;//left & right
	int val;//代表第一列输入的数据
}a[N];

int n;
bool judge[N];//用来判断该节点是否为根

void last(int u)//其他遍历就改变函数名 和 cout位置
{
	if (a[u].l != -1) last(a[u].l);
	if (a[u].r != -1) last(a[u].r);
	cout << u << " ";
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x, l, r;
		cin >> x >> l >> r;
		a[x].l = l;
		a[x].r = r;
		if (l != -1) judge[l] = 1;//证明左孩子不是根
		if (r != -1) judge[r] = 1;//证明右孩子不是根
	}
	int root = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!judge[i]) {//n个编号对应n个位置，该位置没被证明不是根的 即为根（找根）
			root = i;
			break;
		}
	}
	last(root);
	return 0;
}

问题 G: FBI树

题目描述

我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为 B 串，全“1”串称为 I 串，既含“0”又含“1”的串则称为 F 串。
FBI 树是一棵二叉树，它的结点类型也包括 F 结点，B 结点和 I 结点三种。由一个长度为 2N 的“01”串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：
(1) T 的根结点为 R，其类型与串 S 的类型相同；
(2) 若串 S 的长度大于 1，可将串 S 从中间分开，分为等长的左右子串 S1 和 S2；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R 的右子树 T2。

现在给定一个长度为 2N 的“01”串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

输入

第一行是一个整数 N（0≤N≤10），第二行是一个长度为 2N 的“01”串。

输出

包括一行，这一行只包含一个字符串，即 FBI 树的后序遍历序列。

样例输入 Copy

3 
10001011

样例输出 Copy

IBFBBBFIBFIIIFF

法1：

#include
#include
using namespace std;
int N;
char *FBI=new char[100];
char* S = new char[100];
char judge(int i,int len)
{
	char flag = 0;
	int j = i;
	for (; i < j + len; i++)
	{
		if (S[i] == '0')
		{
			if (flag == 0)
				flag = 'B';
			if (flag == 'I')
			{
				flag = 'F';
				break;
			}
		}
		if (S[i] == '1')
		{
			if (flag == 0)
				flag = 'I';
			if (flag == 'B')
			{
				flag = 'F';
				break;
			}
		}
	}
	return flag;
}
void houxu(int i)
{
	if (i < pow(2,N + 1)-1)
	{
		houxu(2*i + 1);
		houxu(2 * i + 2);
		cout << FBI[i];
	}
}
int main()
{
	cin >> N;
	cin >> S;
	int i=1, j,k, m ,len=pow(2,N),len1;
	FBI[0] = 'F';
	for (j = 0; j < N; j++)
	{
		m = 0; 
		for (k = 0; k < pow(2, j + 1); k++)
		{
			len1 = len / pow(2, j + 1);
			FBI[i] = judge(m , len1);
			i++; m = m + len1;
		}
	}
	houxu(0);
	return 0;
}

法2：

#include
#include
#include
using namespace std;
struct TreeNode{
	char data;
	TreeNode*left;
	TreeNode*right;
	TreeNode(char p)
	{
		data=p;
		left=NULL;
		right=NULL;
	}
};
TreeNode* Tree(int T[],int m,int n)//m：每一小段从m（下标）开始；n：每一小段的末位置；（n+m）/2：他左孩子的末尾位置，右孩子的起始位置
{
	bool k=true,g=true;
	//if(m==n)return NULL;
	//cout<<"m="<1)temp->left=Tree(T,m,(n+m)/2);//每一层都是八个数，每次都取一半
	if(n-m>1)temp->right=Tree(T,(n+m)/2,n);
	return temp;
}
void lateOrder(TreeNode*root)
{
	//cout<<"*"<left);
	lateOrder(root->right);
	cout<data;
	return;
}
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int len=pow(2,n);
	int *T=new int [len];
	for(int i=0;i 

问题 H: 满二叉树的深度 
题目描述 
给你一个满二叉树的层次遍历序列，请编程输出该二叉树的深度。 
 
输入 
第一行是n（n小于26）,表示有n个节点。第二行是该满二叉树的节点对应字母的层次遍历序列。 
 
输出 
输出该满二叉数的深度。 
 
样例输入 Copy 
3
B A C
 
样例输出 Copy 
2 
#include
#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	char ch;
	cin>>ch;
	int num=n;
	int count=0;
	int a=0;
	while(num)
	{
		num=num-pow(2,a);
		a++;
		count++;
	}
	cout<

C++数据结构 第二次作业

C/C++/C#相关栏目本月热门文章

C++数据结构第二次作业