矿第二次数据结构实验

【阿二叉树真的很多都不怎么会，最近也没咋练题，def打得非常苦手。】问题 A: 满二叉树的前序遍历

题目描述

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

输入

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

输出

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

样例输入

3
B A C

样例输出

BAC

【A,B,C,H都是一个板，输出的时候改一下函数就可以捏。】

【先用数组内的字母对其初始化，然后从根开始依次连接，填满换行。】

#include
using namespace std;
typedef struct tnode{
    char v;
    tnode* l;
    tnode* r;
    tnode* f;
}tn,*tree;
int n;
char a[26];
int l1=0,r1=0,i=0,sum=0;
tree creat(char a[],int n)
{
    tree root=NULL;
    tree p[n-1];
    for(int i=0;iv=a[i];
    }
    for(int i=0;il==NULL)
            {
                p[sum]->l=p[i];
            }
            else if(p[sum]->r==NULL)
            {
                p[sum]->r=p[i];
                sum++;
            }
        }
    }
    return root;
}
void qx(tree x)
{
    cout<v;
    if(x->l!=NULL) qx(x->l);
    if(x->r!=NULL) qx(x->r);
}
void zx(tree x)
{
     
    if(x->l!=NULL) zx(x->l);
    cout<v;
    if(x->r!=NULL) zx(x->r);
}void hx(tree x)
{
     
    if(x->l!=NULL) hx(x->l);
    if(x->r!=NULL) hx(x->r);
    cout<v;
}
int main()
{
    int n;
    cin>>n;
    char a[n];
    for(int i=0;i>a[i];
    }
    tree x=creat(a,n);
    qx(x);
}

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

题目描述

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

输入

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

输出

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

样例输入

3
B A C

样例输出

ABC

#include
using namespace std;
typedef struct tnode{
	char v;
	tnode* l;
	tnode* r;
	tnode* f;
}tn,*tree;
int n;
char a[26];
int l1=0,r1=0,i=0,sum=0;
tree creat(char a[],int n)
{
	tree root=NULL;
	tree p[n-1];
	for(int i=0;iv=a[i];
	}
	for(int i=0;il==NULL)
			{
				p[sum]->l=p[i];
			}
			else if(p[sum]->r==NULL)
			{
				p[sum]->r=p[i];
				sum++;
			}
		}
	}
	return root;
}
void qx(tree x)
{
	cout<v;
	if(x->l!=NULL) qx(x->l);
	if(x->r!=NULL) qx(x->r);
}
void zx(tree x)
{
	
	if(x->l!=NULL) zx(x->l);
	cout<v;
	if(x->r!=NULL) zx(x->r);
}void hx(tree x)
{
	
	if(x->l!=NULL) hx(x->l);
	if(x->r!=NULL) hx(x->r);
	cout<v;
}
int main()
{
	int n;
	cin>>n;
	char a[n];
	for(int i=0;i>a[i];
	}
	tree x=creat(a,n);
	zx(x);
}

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

题目描述

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

输入

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

输出

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

样例输入

3
B A C

样例输出

ACB

#include
using namespace std;
typedef struct tnode{
    char v;
    tnode* l;
    tnode* r;
    tnode* f;
}tn,*tree;
int n;
char a[26];
int l1=0,r1=0,i=0,sum=0;
tree creat(char a[],int n)
{
    tree root=NULL;
    tree p[n-1];
    for(int i=0;iv=a[i];
    }
    for(int i=0;il==NULL)
            {
                p[sum]->l=p[i];
            }
            else if(p[sum]->r==NULL)
            {
                p[sum]->r=p[i];
                sum++;
            }
        }
    }
    return root;
}
void qx(tree x)
{
    cout<v;
    if(x->l!=NULL) qx(x->l);
    if(x->r!=NULL) qx(x->r);
}
void zx(tree x)
{
     
    if(x->l!=NULL) zx(x->l);
    cout<v;
    if(x->r!=NULL) zx(x->r);
}void hx(tree x)
{
     
    if(x->l!=NULL) hx(x->l);
    if(x->r!=NULL) hx(x->r);
    cout<v;
}
int main()
{
    int n;
    cin>>n;
    char a[n];
    for(int i=0;i>a[i];
    }
    tree x=creat(a,n);
    hx(x);
}

问题 H: 满二叉树的深度

题目描述

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

输入

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

输出

输出该满二叉数的深度。

样例输入

3
B A C

样例输出

【因为是满二叉树所以只用计算左边就好捏.】


#include
using namespace std;
typedef struct tnode{
    char v;
    tnode* l;
    tnode* r;
    tnode* f;
}tn,*tree;
int n;
char a[26];
int l1=0,r1=0,i=0,sum=0,flag=0;
tree creat(char a[],int n)
{
    tree root=NULL;
    tree p[n-1];
    for(int i=0;iv=a[i];
    }
    for(int i=0;il==NULL)
            {
                p[sum]->l=p[i];
            }
            else if(p[sum]->r==NULL)
            {
                p[sum]->r=p[i];
                sum++;
            }
        }
    }
    return root;
}
int sd(tree x)
{
    if(x!=NULL&&flag==0)
    {
        l1=1;
        flag=1;
    }
    if(x->l!=NULL)
    {
        l1++;
        sd(x->l);
    }
    return l1;
}
void qx(tree x)
{
    cout<v;
    if(x->l!=NULL) qx(x->l);
    if(x->r!=NULL) qx(x->r);
}
void zx(tree x)
{
     
    if(x->l!=NULL) zx(x->l);
    cout<v;
    if(x->r!=NULL) zx(x->r);
}void hx(tree x)
{
     
    if(x->l!=NULL) hx(x->l);
    if(x->r!=NULL) hx(x->r);
    cout<v;
}
int main()
{
    int n;
    cin>>n;
    char a[n];
    for(int i=0;i>a[i];
    }
    tree x=creat(a,n);
    cout< 
问题 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 树的后序遍历序列。 
样例输入  
3 
10001011
 
样例输出  
IBFBBBFIBFIIIFF
 
【这个题没有用建树写因为感觉字符比较快，（但是记不得string函数进行了现场搜索函数大全xdd.）在a的长度大于1的情况下不断把它分割为等长的两半，并在每次分割进行判断a被分出的字串类型并返回对应字符。】 
（交了两遍因为第一遍把右边定义成了a.substr（a.length（）/2+1），导致中间被吃掉了一部分出不来。）【说起来n好像在这个方法里用不怎么着的样子。】 
字符串： 
#include
using namespace std;
char zl(string a)
{
    if(a.length()>1)
    {
        cout<>n;
    string a;
    cin>>a;
    int sum=pow(2,n);
    cout< 
建树：（待补充.【不一定写得出来orz.】） 
问题 D: 任意二叉树的前序遍历 
 
题目描述 
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的前序遍历序列。 
输入 
第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。 
输出 
输出该二叉数的前序遍历序列。 
样例输入 Copy 
4
1 2 4
3 1 -1
2 -1 -1
4 -1 -1
 
样例输出 Copy 
3 1 2 4
 
【还是三个题套一个板。】 
（第一遍交判错函数条件了只有50%，因为把输出条件打出有父节点才能进入，错判根了属于是。） 
#include
using namespace std;
typedef struct tnode{
	int v;
	tnode* l;
	tnode* r;
	tnode* f;
};
void qx(tnode *x1)
{
	cout<v<<" ";
	if(x1->l!=NULL) qx(x1->l);
	if(x1->r!=NULL) qx(x1->r);
}
void zx(tnode *x1)
{
	
	if(x1->l!=NULL) zx(x1->l);
	cout<v<<" ";
	if(x1->r!=NULL) zx(x1->r);
}
void hx(tnode *x1)
{
	
	if(x1->l!=NULL) hx(x1->l);
	if(x1->r!=NULL) hx(x1->r);
	cout<v<<" ";
}
int main()
{
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	tnode x[1001];
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		x[a[i]].v=a[i];
		if(b[i]!=-1)
		{
			x[a[i]].l=&x[b[i]];
			x[b[i]].f=&x[a[i]];
		}
			if(c[i]!=-1)
		{
			x[a[i]].r=&x[c[i]];
			x[c[i]].f=&x[a[i]];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(x[i].f==NULL)
		{
			qx(&x[i]);
			break;
		}
	}
}
 
问题 E: 任意二叉树的中序遍历 
 
 
题目描述 
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的中序遍历序列。 
输入 
第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。 
输出 
输出该二叉数的中序遍历序列。 
样例输入 Copy 
4
1 2 4
3 1 -1
4 -1 -1
2 -1 -1
 
样例输出 Copy 
2 1 4 3
 
#include
using namespace std;
typedef struct tnode{
	int v;
	tnode* l;
	tnode* r;
	tnode* f;
};
void qx(tnode *x1)
{
	cout<v<<" ";
	if(x1->l!=NULL) qx(x1->l);
	if(x1->r!=NULL) qx(x1->r);
}
void zx(tnode *x1)
{
	
	if(x1->l!=NULL) zx(x1->l);
	cout<v<<" ";
	if(x1->r!=NULL) zx(x1->r);
}
void hx(tnode *x1)
{
	
	if(x1->l!=NULL) hx(x1->l);
	if(x1->r!=NULL) hx(x1->r);
	cout<v<<" ";
}
int main()
{
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	tnode x[1001];
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		x[a[i]].v=a[i];
		if(b[i]!=-1)
		{
			x[a[i]].l=&x[b[i]];
			x[b[i]].f=&x[a[i]];
		}
			if(c[i]!=-1)
		{
			x[a[i]].r=&x[c[i]];
			x[c[i]].f=&x[a[i]];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(x[i].f==NULL)
		{
			zx(&x[i]);
			break;
		}
	}
}
 
问题 F: 任意二叉树的后序遍历 
 
题目描述 
有若干个节点，每个节点上都有编号，把这些节点随意地构成二叉树，请编程输出该二叉树的后序遍历序列。 
输入 
第一行是n（n小于100）,表示有n个节点，每个节点按从1到n依次编号。第一行后有n行，每行三个正整数i、l、r，分别表示节点i及对应的左右孩子的编号，如果不存在孩子则以-1表示。三个整数之间用一个空格隔开。 
输出 
输出该二叉数的后序遍历序列。 
样例输入 Copy 
4
1 2 4
4 -1 -1
2 -1 -1
3 1 -1
 
样例输出 Copy 
2 4 1 3
 
#include
using namespace std;
typedef struct tnode{
	int v;
	tnode* l;
	tnode* r;
	tnode* f;
};
void qx(tnode *x1)
{
	cout<v<<" ";
	if(x1->l!=NULL) qx(x1->l);
	if(x1->r!=NULL) qx(x1->r);
}
void zx(tnode *x1)
{
	
	if(x1->l!=NULL) zx(x1->l);
	cout<v<<" ";
	if(x1->r!=NULL) zx(x1->r);
}
void hx(tnode *x1)
{
	
	if(x1->l!=NULL) hx(x1->l);
	if(x1->r!=NULL) hx(x1->r);
	cout<v<<" ";
}
int main()
{
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	tnode x[1001];
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
		x[a[i]].v=a[i];
		if(b[i]!=-1)
		{
			x[a[i]].l=&x[b[i]];
			x[b[i]].f=&x[a[i]];
		}
			if(c[i]!=-1)
		{
			x[a[i]].r=&x[c[i]];
			x[c[i]].f=&x[a[i]];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(x[i].f==NULL)
		{
			hx(&x[i]);
			break;
		}
	}
}

矿 第二次数据结构实验

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

矿第二次数据结构实验