无根树转换成为有根树

忘是亡心i 2022-09-19 13:30 142阅读 0赞

/\*  
以前和大家说的都是二叉树，有一种更广义的，就是树，树可以有不仅仅两个子树，  
其实树和图没有多少差别，树都可以用图的表示方法来表示，就比如邻接矩阵和邻接表来表示树，都是可以的，  
今天给大家介绍一个两种数据结构之间的转换技巧，就是无根树和有根树之间的转换。  
  
  
无根树，顾名思义，就是一棵没有树根的树，在我这个例子中间，无根树是用邻接表来表示的，但是这棵树没有连通，也就是没有环，  
所以就可以根据指定的一个顶点来建立一棵树木，这个例子里边，树木是用父亲数组的形式来表示的。  
  
  
下边介绍代码：  
\*/  
\#include<iostream>  
\#include<algorithm>  
\#include<cstdio>  
\#include<cstdlib>  
\#include<cstring>  
\#include<vector>  
using namespace std;  
//树的最大节点数  
const int maxn = 1000;  
//邻接表  
vector<int> G\[maxn\];  
bool vis\[maxn\];  
//父亲数组  
int p\[maxn\];  
//节点数目  
int n;  
//建立图  
void create\_tree()  
\{  
    int i,j,u,v;  
    scanf("%d",&n);  
    for(i=0;i<n-1;i++)  
    \{  
        scanf("%d %d",&u,&v);  
        G\[u\].push\_back(v);  
        G\[v\].push\_back(u);  
    \}  
\}  
//先序遍历展示树  
void show\_tree(int root)  
\{  
    cout<<root;  
    for(int i=0;i<n;i++)  
    \{  
if(p\[i\]==root)  
show\_tree(i);  
    \}  
\}  
//dfs展示图  
void show\_graph(int root)  
\{  
    int len = G\[root\].size();  
    cout<<root;  
    vis\[root\] = 1;  
    for(int i=0;i<len;i++)  
    \{  
        if(!vis\[G\[root\]\[i\]\])  
            show\_graph(G\[root\]\[i\]);  
    \}  
\}  
//转换无根树成为有根树  
void dfs(int root,int parent)  
\{  
    int i,len = G\[root\].size();  
    for(i=0;i<len;i++)  
    \{  
int t = G\[root\]\[i\];  
        if(t!=parent)  
        \{  
            p\[t\] = root;  
            dfs(t,root);  
        \}  
    \}  
\}  
//转换有根树成为无根树  
void tograph(int root)  
\{  
    int i;  
    for(i=0;i<n;i++)  
    \{  
        if(root==p\[i\])  
        \{  
            G\[root\].push\_back(i);  
            G\[i\].push\_back(root);  
            tograph(i);  
        \}  
    \}  
\}  
int main()  
\{  
    int i;  
    freopen("in.txt","r",stdin);  
    memset(vis,0,sizeof(vis));  
    memset(p,0,sizeof(p));  
    p\[1\] = -1;  
    create\_tree();  
    show\_graph(0);  
    dfs(1,-1);  
putchar('\\n');  
    show\_tree(1);  
    for(i=0;i<n;i++)  
    \{  
        G\[i\].resize(0);  
    \}  
    putchar('\\n');  
    tograph(1);  
    memset(vis,0,sizeof(vis));  
    show\_graph(0);  
    return 0;  
\}  
/\*测试数据：  
8  
0 1 0 2 0 3 1 4 1 5 5 6 5 7\*/