数据结构找树根和孩子（树）

一时失言乱红尘 2022-06-09 01:12 198阅读 0赞

#     #

# **树的存储结构：** #

•方法1：数组，称为“父亲表示法”。

constint m = 10; //树的结点数

struct node

int data, parent; //数据域，指针域

\};

node tree\[m\];

例如：tree\[2\]=1;//表示节点2的父亲节点为1

优缺点：利用了树中除根结点外每个结点都有唯一的父结点这个性质。很容易找到树根，但找孩子时需要遍历整个线性表。

# **例题：找树根和孩子** #

【问题描述】

给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子

【输入格式】

第一行：n（结点数<=100），m（边数<=200）。

以下m行；每行两个结点x和y，

表示y是x的孩子(x,y<=1000)。

【输出格式】

第一行：树根：root。

第二行：孩子最多的结点max。

第三行：max的孩子。

【输入样例】

8 7

4 1

4 2

1 3

1 5

2 6

2 7

2 8

【输出样例】

6 7 8

# **分析：** #

![20170823225315055][]

#     #

# **代码：** #

#include<iostream>
    using namespace std;
    int n,m,tree[101]={0};
    int main()
    {
    	int i,x,y,root,maxroot,sum=0,j,Max=0;
    	cin>>n>>m;//节点和边的数目 
    	for(i=1;i<=m;i++)
    	{
    		cin>>x>>y;
    		tree[y]=x;//y是x的孩子 
    	}
    	for(i=1;i<=n;i++)//找出树根 
    	{
    		if(tree[i]==0)// i的父亲节点为0，即没有父亲节点 
    		{
    			root=i;
    			break;
    		} 
    	}
    	for(i=1;i<=n;i++)//找孩子最多的节点maxroot
    	{
    		sum=0;
    		for(j=1;j<=n;j++)
    		{
    			if(tree[j]==i) sum++;
    		}
    		if(sum>Max)
    		{
    			Max=sum;
    			maxroot=i;
    		}
    	} 
    	cout<<root<<endl<<maxroot<<endl;
    	for(i=1;i<=n;i++)//maxroot的孩子 
    	{
    		if(tree[i]==maxroot) cout<<i<<" ";
    	}
    	return 0;
    }

![20170823223816493][]

[20170823225315055]: /images/20220609/8ad65150983041f89e42cb7fb6cf496f.png
[20170823223816493]: /images/20220609/ea80fd61e3484ca4bf3255224a4e5b6b.png