流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （Java代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

03-树--浙大数据结构-2019秋

　　作者: 流离之人追逐幻影　　　　发表时间：2019-11-09 20:42:17 浏览：396　|　评论：0　

```
03-树1 树的同构 (25 分)
```
![](/image_editor_upload/20191109082851_54960.png)
![](/image_editor_upload/20191109082923_84610.png)
![](/image_editor_upload/20191109082948_16206.png)
题解：
```
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。
步骤：
1.建立两颗二叉树
2.判断这两颗树是否同构
核心：同构算法
	//如果两个二叉树为空，则是同构 
	//其中一个是空树，一个不是空树，则非同构 
	//树根的值不一样，非同构 
	//左孩子为空，则判断右孩子是否是同构 
	
	//左孩子非空，且左孩子相同
	//则判断两个树的左子树与左子树是否同构，右子树与右子树是否同构，
	//否则判断T1左子树和T2右子树是否同构，T1右子树和T2左子树是否同构 
```

AC代码：
```
#include<stdio.h>
 
#define MaxTree 10 
#define ElementType char 
#define Tree int 
#define Null -1
struct TreeNode {
	ElementType Element; 
	Tree Left; 
	Tree Right;
} T1[MaxTree], T2[MaxTree];

Tree BuildTree( struct TreeNode T[] ) {
	int N,i,check[MaxTree],cl,cr,Root=Null; 
	scanf("%d\n", &N); 
	if (N) {
		for (i=0; i<N; i++) check[i] = 0; 
		//排除有指向的节点，那么没有指向的就是root了。 
		for (i=0; i<N; i++) { 
			scanf("%c %c %c\n", &T[i].Element, &cl, &cr); 
			if (cl != '-') { 
				T[i].Left = cl-'0'; 
				check[T[i].Left] = 1;
			}
			else 
				T[i].Left = Null; 
			if (cr != '-') { 
				T[i].Right = cr-'0'; 
				check[T[i].Right] = 1;
			}
			else 
				T[i].Right = Null; 
		}
		for (i=0; i<N; i++) 
			if (!check[i]) 
				break;
		Root = i; 
	} 
	return Root; 
}

int Isomorphic ( Tree R1, Tree R2 ) {
	//如果两个二叉树为空，则是同构 
	if ( (R1==Null )&& (R2==Null) ) 
		 return 1;
	//其中一个是空树，一个不是空树，则非同构 
	if ( ((R1==Null)&&(R2!=Null)) || ((R1!=Null)&&(R2==Null)) ) 
		return 0;
	//树根的值不一样，非同构 
	if ( T1[R1].Element != T2[R2].Element ) 
		return 0; 
	//左孩子为空，则判断右孩子是否是同构 
	if( ( T1[R1].Left == Null )&&( T2[R2].Left == Null ) ) 
		return Isomorphic( T1[R1].Right, T2[R2].Right ); 
	//左孩子非空，且左孩子相同
	//则判断两个树的左子树与左子树是否同构，右子树与右子树是否同构，
	//否则判断T1左子树和T2右子树是否同构，T1右子树和T2左子树是否同构 
	if ( ((T1[R1].Left!=Null)&&(T2[R2].Left!=Null))&& ((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)) )
		return ( Isomorphic( T1[R1].Left, T2[R2].Left ) && Isomorphic( T1[R1].Right, T2[R2].Right ) );
	else
		return ( Isomorphic( T1[R1].Left, T2[R2].Right) && Isomorphic( T1[R1].Right, T2[R2].Left ) );	
}

int main() {
	Tree R1, R2;
	//建立二叉树 
	R1 = BuildTree(T1); 
	R2 = BuildTree(T2); 
	//判断这两棵树是否同构 
	if (Isomorphic(R1, R2)) 
		printf("Yes\n"); 
	else 
		printf("No\n");
	return 0;

}

```
```
03-树2 List Leaves (25 分)
```
![](/image_editor_upload/20191109083218_78831.png)
题解：
```
步骤：
1.先建立二叉树
2.层次遍历
```
AC代码：
```
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<queue>
using namespace std;

#define MaxTree 10 
#define ElementType char 
#define Tree int 
#define Null -1
struct TreeNode {
	Tree Left; 
	Tree Right;
} T1[MaxTree];

Tree BuildTree( struct TreeNode T[] ) {
	int N,i,check[MaxTree],Root=Null;
	char cl,cr; 
	scanf("%d", &N); 
	if (N) {
		for (i=0; i<N; i++) check[i] = 0; 
		//排除有指向的节点，那么没有指向的就是root了。 
		for (i=0; i<N; i++) { 
			scanf("\n%c %c",  &cl, &cr); 
			if (cl != '-') { 
				T[i].Left = cl-'0'; 
				check[T[i].Left] = 1;
			}
			else 
				T[i].Left = Null; 
			if (cr != '-') { 
				T[i].Right = cr-'0'; 
				check[T[i].Right] = 1;
			}
			else 
				T[i].Right = Null; 
		}
		for (i=0; i<N; i++) 
			if (!check[i]) 
				break;
		Root = i; 
	} 
	return Root; 
}
//层次遍历 
void PrintLeaves(Tree R){
	Tree tmp;
    int ct=0;
    if(R==Null)
    	return ;
    queue<int> q;
    q.push(R);
    while(!q.empty()){
    	tmp =q.front();
    	q.pop();
    	if(T1[tmp].Left==Null&&T1[tmp].Right==Null){
    		if(ct++!=0)
    			cout<<" ";
    		cout<<tmp;
		}
		if(T1[tmp].Left!=Null) q.push(T1[tmp].Left);
		if(T1[tmp].Right!=Null) q.push(T1[tmp].Right);
	}	
}

int main() {
	Tree R1;
	//建立二叉树 
	R1 = BuildTree(T1); 
	//判断这两棵树是否同构 
	PrintLeaves(R1);
	return 0;

}
```
```
03-树3 Tree Traversals Again (25 分)
```
![](/image_editor_upload/20191109083345_18726.png)
![](/image_editor_upload/20191109083405_16440.png)
题解：
```
Push 序列是前序遍历，Pop 序列是中序遍历，题意就是根据前序遍历和中序遍历求后序遍历。
```
AC代码：
```
#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
using namespace std;
int ct=0;
void LastSearchOrder(int *pr,int *in,int length) {
    if(!length) return ;
    int RootPos = 0;
    for(;RootPos<length;RootPos++) {
        if(in[RootPos] == *pr) break;
    }
    LastSearchOrder(pr+1,in,RootPos);
    LastSearchOrder(pr+1+RootPos,in+1+RootPos,length-RootPos-1);
    if(ct++!=0)
    	cout<<" ";
    cout<<*pr;
}
int pr[10005], in[10005];
int main()
{
	stack<char> s;
    int n,pr_i=0,in_i=0;
    char op[20];
    cin>>n;
    for(int i=0;i<2*n;i++){
    	cin>>op;
    	if(strcmp("Push",op)==0){
    		cin>>pr[pr_i];
    		s.push(pr[pr_i++]);
		}
		else{
			in[in_i++]=s.top();
			s.pop();
		}	
	}
    LastSearchOrder(pr,in,n);
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （Java代码）

地宫取宝（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

03-树--浙大数据结构-2019秋

评论区

精彩推荐

不容易系列2 （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

字符逆序（C语言代码）

愚蠢的摄影师（C++代码）

1014题解

1054题解

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （Java代码）

地宫取宝 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C++代码）（其实不需要开数组，一个一个字符读入并判断就好了）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

03-树--浙大数据结构-2019秋

评论区

精彩推荐

不容易系列2 （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

字符逆序 （C语言代码）

愚蠢的摄影师 （C++代码）

1014题解

1054题解

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

地宫取宝（C语言代码）

　　评论区

【亲和数】（C语言代码）

字符逆序（C语言代码）

愚蠢的摄影师（C++代码）