简介

很多像我一样的蒟蒻也已经明白树十分重要，所以树是必须要熟记的。

树的存储（无权）

树是个神奇的东西，因为它不确定指向几个数，所以用邻接表（vector）存储最合适。

如图，vector存储后为：

vector[1]="2 5 8";

vector[2]="3"

vector[3]="4";

vector[4]=""

vector[5]="6";

vector[6]=""

vector[7]="";

vector[8]="7 9"

vector[9]=" 10";

vector[10]=""

二叉树的存储代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> t[100];
int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		if(l!=0) t[i].push_back(l);
		if(r!=0) t[i].push_back(r);
	}
	for(int i=1;i<=n;i++){
		if(t[i].size()>=1){
			cout<<"子节点个数："<<t[i].size();
		if(t[i][0]!=0) cout<<" 左节点："<<t[i][0];
		if(t[i][0]==0) cout<<" 无左节点";
		if(t[i][1]!=0) cout<<" 右节点："<<t[i][1];
		if(t[i][1]==0) cout<<" 无右节点"; 
		}
		if(t[i].size()==0) cout<<"为叶子结点";
		cout<<endl;
	}
	return 0;
}
/*
in:
4
2 3
4 0
0 0
0 0
out:
子节点个数：2 左节点：2 右节点：3
子节点个数：1 左节点：4 无右节点
为叶子结点
为叶子结点
*/

二叉树的遍历

前序遍历为：根左右

中序遍历为：左根右

后序遍历为：左右根

如图:

前序遍历为：1 2 4 5 3 6

中序遍历为：4 2 5 1 6 3

后序遍历为：4 5 2 6 3 1

所以，题P1305 新二叉树 - 洛谷为前序遍历

代码见我：P1305 新二叉树—＞vector与dfs和树-CSDN博客

           我恩师hnjzsyjyj的：洛谷 P1305：新二叉树 ← DFS + 哈希表优化-CSDN博客

代码见下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
vector<int> t[1005];
bool st[maxn];//标记是否遍历
int x1[maxn];//标记遍历过的数
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) {
		st[i]=true;
	}
	for(int i=1; i<=n; i++) {
		int l,r;
		cin>>l>>r;
		t[i].push_back(l);
		t[i].push_back(r);
	}
	int j=0;
	int x=1;
	x1[j]=x;
	while(st[t[1][0]]!=false||st[t[1][1]]!=false) {//把左与右全遍历一遍
		if(st[t[x][0]]==false&&st[t[x][1]]==false) {
			cout<<x<<" ";//为叶子结点时，可以输出
			st[x]=false;//标记，也可以说是删除
			while((st[t[x][0]]==false&&st[t[x][1]]==false)&&x!=1) {
				x=x1[--j];//进行返回
			}
		} else {
			for(int i=0; i<t[x].size(); i++) {
				if(st[t[x][i]]!=false) {
					x=t[x][i];
					x1[++j]=x;
					break;//寻找下一个数，先遍历左，后遍历右
				}
			}
		}
	}
	cout<<1;//最后遍历根节点
	return 0;
}

中序遍历：未完待续...