树；二叉树

༺ཌༀཉི𝓍𝓎x༃ༀད༻🕸

2025-07-28 14:05:16

发布于：浙江

5阅读

0回复

0点赞

$\Huge \color{blue}{树}$
是一种非线性结构，能够很好的描述有分支和参差特性的数据集合。
树作为一种非线性的数据结构，是由 $n（n>0）$ 个结点组成的集合。除根节点外的其他结点划分为m,( $m \geq 0$ ) 。
其中每个集合本身又称一棵树，称为子树。
部分图eg：
$\overbrace{A 、 B 、C}^{A}$
$\overbrace{B}^{}$ $\overbrace{C}^{}$ $\overbrace{D}$

$\Huge \color{blue}{二叉树}$

一、介绍

二叉树简称BT（~~和变态无关~~）是一种度数最大为
二的树形结构，即二叉树的每个节点最多有两个子节点

二、五大性质

1，在二叉树的第i层上最多有 $2^i$ -1个节点 $i \geq 1$ ;
2，深度为k的二叉树至多有 $2^k$ -1个节点 $k \geq 1$ ;
3，任意一颗二叉树，若其叶子节点（度为0节点）的
数量为n0，度为2的节点数量为n2，则：n0与n2一
定满足：n0=n2+1
//n0+n1+n2=n(式一）
//n1+2n2+1=n(式2）*

注意：

若某二叉树深k层，除第k层外其他层的节点总数达
最大值，且第k层节点数小于等于 $2^(k-1)$ 并靠左侧连续
，这种特殊形态的二叉树，称为完全二叉树。
4，具有n(n>=0)个节点的完全二叉树的深度为floor(log2(n))+1。
5，若将一棵有n个节点的完全二叉树自顶向下，同一层自左向右连续給节点编号1，2，3，4，5，6，……n-2,n-1,n,则：
1.若节点编号i=1，则节点i为跟，无父结点
2.若i>1,则i的父节点编号为i/2。
3.针对编号为i的节点：
3.1 其左孩子编号为 $2^i$ （ $2^i \leq n$ );
3.1 其右孩子编号为 $2^i$ +1（ $2^i+1 \leq n$ );

三，遍历：

先序遍历（根左右）
中序遍历（左根右）
后序遍历（左右根）

输的输入

伪码：

#include<bits/stdc++.h>
using namespace std;
vector<int>V[N];//v[i] i,儿子编号是哪些 
int main(){
	//1.父亲表示法：每个结点只记录父亲的编号
	//fa数组表示
	//根节点：fa[1]=0;
	//fa[2]=1,fa[3]=1;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		fa[u]=v;
	}
	//2.孩子表示法
	 for(int i=1;i<=n-1;i++){
	 	int x;cin>>x;
	 	for(int j=0;i<x;j++){
	 		int t;cin>>t;
	 		v[i].push_back(t);
		 }
	 }
	return 0; 
}

层次：

根节点为第一层，根节点的孩子为第二层，以此类推

树的深度/高度：

树中结点的最大层次

树的直径

1BFS

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
vector<int>V[maxn];
int maxu,maxstep;
struct node{
	int u;//结点编号 
	int step;
};
int vis[maxn];//判断结点不重复访问 
void bfs(int x){
	maxstep=0;maxu=0;
	queue<node>q;
	memset(vis,0,sizeof(vis));
	vis[x]=1;
	q.push(node{x,0});
	while(!q.empty()){
		node tmp=q.front();
		q.pop();
		if(tmp.step>maxstep){
			maxstep=tmp.step;
			maxu=tmp.u;
		}
		//走到下一个结点 
		for(int i=0;i<V[tmp.u].size();i++){
			int v=V[tmp.u][i];//结点编号 
			if(vis[v])continue;
			vis[v]=1;
			q.push(node{v,tmp.step+1});
		}
	}
}
int main(){
	int n;cin>>n;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	bfs(1);//范围距离1 最远的结点 得到距离1最远的点
	bfs(maxu);//最远的点出发就可以到达直径
	cout<<maxstep<<endl; 
	return 0; 
}

2、DFS

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
vector<int>V[maxn];
int maxu,maxstep;
void dfs(int u,int pre,int step){
	if(step>maxstep){
		maxu=u;
		maxstep=step;
	}
	for(auto v:V[u]){
		if(v==pre)continue;
		dfs(v,u,step+1);
	}
}
int main(){
	int n;cin>>n;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	maxstep=0;
	dfs(1,0,0);
	maxstep=0;
	dfs(maxu,0,0);
	
	cout<<maxstep<<endl; 
	return 0; 
}

已知中序后序求前序

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],b[200005],c[200005],x;
void f(int l1,int r1,int l2,int r2)//在中序数组的l1,r1,后序数组中的l2,r2
{ 	//边界
	if(l1==r1){
		cout<<a[l1]<<" ";
		return;
	} 
	//递归划分 
	int root=b[r2];//找到根
	int pos=c[root];
	cout<<root<<" "; 
	int len1=pos-l1;
	if(pos-1>=l1)f(l1,pos-1,l2,l2+len1-1);//递归左子树
	int len2=r1-pos;
	if(r1>=pos+1)f(pos+1,r1,r2-len2,r2-1);//递归右子树 	
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		c[a[i]]=i;//位置
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
	}
	f(0,n-1,0,n-1);
	return 0; 
}