树形结构 —— 树与二叉树 —— 无根树转有根树

本文主要是介绍树形结构 —— 树与二叉树 —— 无根树转有根树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【概述】

无根树转有根树是指：当给出 n 个结点与 n-1 条边后，给定一个要指定的根结点的编号 root，建立以 root 为根的树。

利用 STL 中的 vector，在输入 n-1 条边后，从 root 开始进行 dfs，遍历其邻接点，递归的将其转换为子树。

【实现】

vector<int> G[N];
int father[N];
void dfs(int x,int fa){//递归的转化以x为为根的子树，x的父节点为faint n=G[x].size();//x的邻接点个数for(int i=0;i<n;i++){//遍历x的邻接点int y=G[x][i];//x的第i个邻接点yif(y!=fa)//将y的父结点设为x，递归转成y为根的子树dfs(y,father[y]=x);}
}
int main(){int n;scanf("%d",&n);for(int i=1;i<=n-1;i++){int x,y;scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}int root;scanf("%d",&root);father[root]=-1;dfs(root,-1);for(int i=1;i<=n;i++)printf("%d\n",father[i]);return 0;
}

 

这篇关于树形结构 —— 树与二叉树 —— 无根树转有根树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---