浙江大学数据结构练习笔记：链表，二叉树，二叉搜索树（更新中）

由于本人水平有限，整理的代码若有错漏欢迎指出

线性结构：多项式加法（链表实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
​```c++
#include<bits/stdc++.h>
#include<string>
#include<cctype>
using namespace std;
//浙江大学数据结构练习
//多项式加法的实现
struct PolyNode{
	int coef;//系数
	int expon;//指数
	struct PolyNode * link;//指向下一个结点的指针 
};
typedef struct PolyNode *Poly;
Poly P1, P2;
int Compare(int a,int b)
{
	if(a>b) return 1;
	else if(a==b) return 0;
	else return -1;
}
void Attach(int c,int e,Poly * pRear)
{
	Poly P;
	P=(Poly)malloc(sizeof(struct PolyNode));
	P->coef=c;
	P->expon=e;
	P->link=NULL;//对新结点赋值 
	(*pRear)->link=P;//把新结点插到rear的后面 
	*pRear=P;//pRear是指针的指针 
}
Poly PolyAdd(Poly P1, Poly P2)
{
	Poly front, rear, temp;
	int sum;
	rear = (Poly)malloc(sizeof(struct PolyNode));
	front = rear;//由front记录结果多项式链表的头节点
	while (P1&&P2) {
		switch(Compare(P1->expon,P2->expon)){
		//Compare函数第一个参数值大就返回1 
			case 1:
				Attach(P1->coef,P1->expon,&rear);
				//把这一项拷贝到结果多项式 
				P1=P1->link;//P1后挪 
				break;
			case -1:
				Attach(P2->coef,P2->expon,&rear);
				P2=P2->link;
				break;
			case 0:
				sum=P1->coef+P2->coef;
				if(sum) Attach(sum,P1->expon,&rear);
				P1=P1->link;
				P2=P2->link;
				break;
		}
	}
	//将未处理完的另一个多项式所有结点复制到结果 
	for(;P1;P1=P1->link) Attach(P1->coef,P1->expon,&rear);
	for(;P2;P2=P2->link) Attach(P2->coef,P2->expon,&rear);
	rear->link=NULL;
	temp=front;
	front=front->link;
	free(temp);
	return front;
}

Poly ReadPoly()
{
	int N,c,e;
	Poly Rear,P,t;
	
	cin>>N;
	P=(Poly)malloc(sizeof(struct PolyNode));//申请空结点 
	//链表空头节点 
	P->link=NULL;
	Rear=P;
	while(N--){
		cin>>c>>e;//输入系数指数 
		Attach(c,e,&Rear);
	}
	t=P;P=P->link;free(t);//删除临时生产的头节点 free释放malloc申请的内存 
	//P指向链表头节点 
	return P;
}
void PrintPoly(Poly p)
{
	int flag=0;
	if(!p) cout<<"0"<<endl;
	while(p){
		if(!flag) flag=1;//判断是不是第一项 
		else cout<<" ";
		cout<<p->coef<<" "<<p->expon<<" ";
		p=p->link;
	}
}
int main()//读入多项式 
{
	Poly P1,P2,PS;
	P1=ReadPoly();
	P2=ReadPoly();
	PS=PolyAdd(P1,P2);
	PrintPoly(PS);
	return 0;
}

二叉树：

二叉树的储存：链表储存

二叉树的储存结构

1
2
3
4
5
6
7
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
	ElementType Data;
	BinTree Left;//左儿子
	Bintree Right;//右儿子
};

二叉树的遍历：

前序遍历：递归实现

1
2
3
4
5
6
7
8
void PreOrderTraversal(BinTree BT)
{
	if(BT){
		cout<<BT->Data;
		PreOrderTraversal(BT->Left);
		PreOrderTraversal(BT->Right);
	}
}

中序遍历：递归实现

1
2
3
4
5
6
7
8
void InorderTraversal(BinTree BT)
{
	if(BT){
		InOrderTraversal(BT->Left);
		cout<<BT->Data;
		InorderTraversal(BT->Right);
	}	
}

后序遍历：递归实现

1
2
3
4
5
6
7
8
void PostOrderTraversal(BinTree BT)
{
	if(BT){
		PostOrderTraversal(BT->Left);
		PostOrderTraversal(BT->Right);
		cout<<BT->Data;
	}
}

层序遍历：队列实现

在这里插入图片描述

1.从队列中取出有个元素2.访问该元素所指的结点3.若该结点所指的左右结点非空则将其左右儿子是指针顺序入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
#define MaxSize 10000
//浙江大学数据结构二叉树
typedef struct TreeNode *BinTree;
typedef BinTree Position;

struct TreeNode{
	int Data;
	BinTree Left;
	BinTree Right;
}; 

struct QNode{
	BinTree Data[MaxSize];
	int rear;
	int front;
};
typedef struct QNode *Queue;//队列 

void CreatQueue(Queue Q)
{
 	Q->front=0;Q->rear=0;
}

bool IsemptyQ(Queue Q)
{
	return (Q->front==Q->rear);
}
void AddQ(Queue ptrQ,BinTree item)
{
	//入队函数
	if((ptrQ->rear+1)%MaxSize==ptrQ->front )
	cout<<"队列满";
	ptrQ->rear= (ptrQ->rear+1)%MaxSize;
	ptrQ->Data[ptrQ->rear]=item;
}

BinTree DeleteQ(Queue ptrQ)
{//出队函数 
	if(ptrQ->front==ptrQ->rear){
	cout<<"队列空";
	return ERROR;}
	else{
		ptrQ->front=(ptrQ->front+1)%MaxSize;
		return ptrQ->Data[ptrQ->front];
	}
}

void LevelOrderTraversal(BinTree BT)
{
	//层序遍历
	Queue Q;
	BinTree T;
	if(!BT) return;//若是空树则返回
	CreatQueue(Q);//创建并初始化队列
	AddQ(Q,BT);
	while(!IsemptyQ(Q)){
		T=DeleteQ(Q);
		cout<<T->Data<<endl;
		if(T->Left) AddQ(Q,T->Left);
		if(T->Right) AddQ(Q,T->Right);
	} 
}

由两种遍历序列确定二叉树必须要有中序遍历！

先序遍历和中序遍历确定一颗二叉树：

在这里插入图片描述

1.根据先序遍历第一个结点确定根节点

2.根据根节点在中序遍历中分割成左子树和右子树

3.分别递归实现
知前序和中序遍历求后续遍历（hdu1710)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
//hdu1710知道二叉树前序和中序遍历求后序遍历
const int N=1010;
int pre[N],in[N],post[N];
int k;
struct TreeNode{
	int value;
	TreeNode * Left;
	TreeNode * Right;
	TreeNode(int value=0,TreeNode * Left=NULL,TreeNode * Right=NULL):value(value),Left(Left),Right(Right){}
}; 
void buildtree(int L,int R,int &t,TreeNode* &root){
	//建树
	int flag=-1;
	for(int i=L;i<=R;i++)
		if(in[i]==pre[t]){//先序的第一个是根，找到对应中序的位置 
			flag=i;break;
		} 
	if(flag==-1) return;
	root=new TreeNode(in[flag]);//新建结点 
	t++;
	if(flag>L) buildtree(L,flag-1,t,root->Left);
	if(flag<R) buildtree(flag+1,R,t,root->Right);
}
void PostOrder(TreeNode* root){
	if(root!=NULL){
		PostOrder(root->Left);
		PostOrder(root->Right);
		post[k++]=root->value;
	}
}
void remove(TreeNode* root)
{
	if(root==NULL) return;
	remove(root->Left);
	remove(root->Right);
	delete root;//释放空间 
}
int main()
{
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++) cin>>pre[i];
		for(int j=1;j<=n;j++) cin>>in[j];
		TreeNode* root;
		int t=1;
		buildtree(1,n,t,root);
		k=0;

		PostOrder(root);
		for(int i=0;i<k;i++) {
			cout<<post[i];
			if(i==k-1) cout<<endl;
			else cout<<" ";
		}
		remove(root);
	}
	return 0;
}

树的同构：

两棵树通过若干次左右儿子的互换可变成对方则这两棵树同构

二叉树的表示：静态链表

判断根节点：静态数组里面没有用到的结点即对应的Element为根
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
//二叉树的表示：静态链表
#define MaxTree 10
#define ElementType char
#define ELT ElementType
#define Tree int
#define Null -1//区分NULL 

struct TreeNode{
	ELT Element;
	Tree Left;
	Tree Right;
}T1[MaxTree],T2[MaxTree];

建树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Tree BuildTree(struct TreeNode T[])//建树 
{
    char cl,cr;
	int N,check[MaxTree],Root;
	cin>>N;
	if(N){
		for(int i=0;i<N;i++) check[i]=0;
		for(int 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=cl-'0';
				check[T[i].Right]=1;
			}
			else T[i].Right=Null;
		}
		for(int i=0;i<N;i++)
			if(!check[i]) {	Root=i;break;}
	}
	return Root;
}

判断两棵树是否同构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
//二叉树的表示：静态链表
#define MaxTree 100
#define ElementType char
#define ELT ElementType
#define Tree int
#define Null -1//区分NULL 

struct TreeNode{
	ELT Element;
	Tree Left;
	Tree Right;
}T1[MaxTree],T2[MaxTree];
Tree BuildTree(struct TreeNode T[])//建树 
{
    char cl,cr;
	int N,check[MaxTree],Root;
	cin>>N;
	if(N){
		for(int i=0;i<N;i++) check[i]=0;
		for(int 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=cl-'0';
				check[T[i].Right]=1;
			}
			else T[i].Right=Null;
		}
		for(int i=0;i<N;i++)
			if(!check[i]) {	Root=i;break;}
	}
	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);
	
	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)) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

二叉搜索树：

判断是否为同一颗二叉搜索树：

主要思路：先建一棵树，然后把每个序列分别比较。对于一个序列，如果在查找过程中经过在树上有为被访问过的点则不是一棵树
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
// 判别是否同一颗二叉树
typedef struct TreeNode *Tree;
struct TreeNode{
	int v;//结点的值
	Tree Left,Right;
	int flag; //标志这个点是否访问过 
};

Tree NewNode(int V)
{
	Tree T=(Tree)malloc(sizeof(struct TreeNode));
	T->v=V;
	T->Left=T->Right=NULL;
	T->flag=0;
	return T;
}
Tree Insert(Tree T,int V)
{
	if(!T) T=NewNode(V);
	else{
		if(V>T->v) 
			T->Right=Insert(T->Right,V);
	    else
	    	T->Left=Insert(T->Left,V);
	}
	return T;
}
Tree MakeTree(int N)
{
	Tree T;
	int i,V;
	cin>>V;
	T=NewNode(V);
	for(int i=1;i<N;i++){
		cin>>V;
		T=Insert(T,V);
	}
	return T;
}
int check(Tree T,int V)
{
	if(T->flag){
		if(V<T->v) return check(T->Left,V);
		else if(V>T->v) return check(T->Right,V);
		else return 0;//同一个数字出现两次 
	}
	else{
		if(V==T->v){
			T->flag=1;
			return 1;
		}
		else return 0;
	}
}
int Judge(Tree T,int N)
{
	int i,V,flag=0;
	//flag=0代表目前还一致，1代表已经不一致
	cin>>V;
	if(V!=T->v) flag=1;
	else T->flag=1;
	for(int i=1;i<N;i++){
		cin>>V;
		if((!flag)&&(!check(T,V))) flag=1;
		//如果不行则不再check但要继续读完 
	} 
	if(flag) return 0;
	else return 1;
}
void ResetT(Tree T)
{
	if(T->Left) ResetT(T->Left);
	if(T->Right) ResetT(T->Right);
	T->flag=0;	
} 
void FreeTree(Tree T)//释放空间
{
	if(T->Left) FreeTree(T->Left);
	if(T->Right) FreeTree(T->Right);
	free(T);
} 
int main()
{
	int N,L,i;
	Tree T;
	cin>>N;
	while(N)
	{
		cin>>L;
		T=MakeTree(N);
		for(int i=0;i<L;i++)
		{
			if(Judge(T,N)) cout<<"Yes\n";
			else cout<<"No"<<endl;
			ResetT(T);//清楚T中的标记flag 
		}
		FreeTree(T);
		cin>>N;
    }
    return 0;
}