当前位置：首页 > news >正文

c++里的族谱：树

news 2026/7/30 16:15:32

1.引入

Q\(_1\): 树在C++里是什么？

A\(_1\) 就是描述一对多关系的数据结构。

Q\(_2\) C++里的树，跟实际生活有什么关系？

A\(_2\) 就是你家的族谱。一个根，往下分叉出子孙，层层往下，C++的树与这是完全一样的

2.什么是树

2.1树的要素

父子： 树的上层和下层是父子关系
根：树最顶上的元素（没有父节点）
子树： 树中任何一个节点，连同它下面的所有后代，都可以构成一棵子树

2.2不同的树

2.2.1二叉树

2.2.1.1二叉树的定义

二叉树是\(n（n≥0）\)个节点的有限集合，该集合要么为空（称为空二叉树），要么由一个根节点和两棵互不相交的二叉树组成(一般称为左子树和右子树)。

2.2.1.2二叉树长什么样？

2.2.1.3满二叉树

定义： 每个节点要么没有孩子，要么正好有两个孩子。

2.2.1.4完全二叉树

定义： 除了最后一层可以不满，其他层必须排满，而且最后一层的节点必须从左往右连续排列，中间不能有空位。

2.2.2多叉树

有且仅有一个根节点（n=0 时为空树）。
除根节点外，每个节点有且仅有一个父节点。
每个节点可以有 0 到 m（m≥3）个子节点，且子节点之间无序或有序（有序多叉树也叫 m 叉树）。

3.树的代码实现

3.1二叉树版

#include<bits/stdc++.h>
using namespace std;
int n;//树的节点数
vector<int>e[1000005];//e用于记录节点的子节点
void dfs1(int now) {//前序遍历：按照 根，左子树，右子树 的顺序遍历cout<<now<<" ";//输出根for(int i:e[now]) {//枚举子节点if(i==0) continue;dfs1(i);//递归}return ;
}
void dfs2(int now) {//中序遍历：按照 左子树，根，右子树 的顺序遍历int a=e[now].front(),b=e[now].back();//a，b  为子节点编号if(a!=0) dfs2(a);//递归cout<<now<<" ";//输出根if(b!=0) dfs2(b);return ;
} 
void dfs3(int now) {//后序遍历：按照 左子树，右子树，根 的顺序遍历for(int i:e[now]) {//枚举子节点if(i==0) continue;//特判dfs3(i);//递归}cout<<now<<" ";//输出根return ;
}
int main() {cin>>n;//输入节点数量for(int i=1;i<=n;i++) {int u,v;cin>>u>>v;e[i].push_back(u);e[i].push_back(v);}dfs1(1);//前序cout<<endl;dfs2(1);//中序cout<<endl;dfs3(1);//后序cout<<endl;return 0;
}

输入 1:

输出 1:

1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1

3.2多叉树版

#include<bits/stdc++.h>
using namespace std;
int n,m;//n为节点数，m为边的数量
vector<int>e[100005];//e存储每个点的父节点和子节点
int dep[100005];//存储每个点的深度（距离根的距离）
int maxx=0;//最远距离（树的深度）
void dfs(int now,int fa) {//递归，now表示当前节点，fa表示当前节点的父节点dep[now]=dep[fa]+1;//深度+1maxx=max(maxx,dep[now]);//记录最大深度for(int i:e[now]) {//枚举子节点if(i==fa) continue;//特判dfs(i,now);//递归}
}
int main() {cin>>n>>m;//输入for(int i=1;i<=m;i++) {int u,v;cin>>u>>v;//u，v表示两个节点e[u].push_back(v);e[v].push_back(u);}dep[0]=0;//初始化dfs(1,0);//默认1的父节点为0cout<<maxx;//输出return 0;
}