1. 概念
子节点个数不限且没有顺序。
2.树的遍历
只有两种：
先根遍历和层序遍历
先根遍历就是先访问根节点，再访问子节点。
层序遍历跟二叉树的层次遍历类似。
3.树的存储结构
二叉树的存储结构有静态和动态，但是树的子节点可以不限，如果用指针的话，不方便，所以这里我用静态，也就是数组存下标，但是子树的个数可能不同，所以我用vector容器来存下标。
struct node{
int data;
vector<int> child;
} Node[range]; // Node前面要空一个空格
4.新生成一个节点
int index=0;
bool IsRoot[range];
int newnode(int v){
Node[index].data=v;
Node[index].child.clear();
return index++;
}
5.先根遍历
void preroot(int root)
{
cout<<Node[root].data<<" ";
for(int i=0;i<Node[root].child.size();i++)
{
preroot(Node[root].child[i]);
}
}
6.层序遍历
void layerorder(int root){
queue<int> s;
s.push(root);
while(!s.empty()){
int t=s.front();
s.pop();
cout<<Node[t].data<<" ";
for(int i=0;i<Node[t].child.size();i++)
s.push(Node[t].child[i]);
}
}
6.完整的代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define range 100
struct node{
int data;
vector<int> child;
} Node[range]; // Node前面要空一个空格
int index=0;
bool IsRoot[range];
int newnode(int v){
Node[index].data=v;
Node[index].child.clear();
return index++;
}
void preroot(int root)
{
cout<<Node[root].data<<" ";
for(int i=0;i<Node[root].child.size();i++)
{
preroot(Node[root].child[i]);
}
}
void layerorder(int root){
queue<int> s;
s.push(root);
while(!s.empty()){
int t=s.front();
s.pop();
cout<<Node[t].data<<" ";
for(int i=0;i<Node[t].child.size();i++)
s.push(Node[t].child[i]);
}
}
int main(){
int i,j,t,n,m,k,Root=-1;
cout<<"请输入树中节点个数:"<<endl;
cin>>n;
fill(IsRoot,IsRoot+n,true);
for(i=0;i<n;i++)
{
cout<<"请输入树中各节点值以及子树下标:"<<endl;
cin>>t;
newnode(t);
cout<<"请输入该节点子树个数:"<<endl;
cin>>m;
cout<<"请输入子树下标:"<<endl;
for(j=0;j<m;j++)
{
cin>>k;
IsRoot[k]=false;
Node[t].child.push_back(k);
}
}
for(i=0;i<n;i++)
if(IsRoot[i])
{
Root=i;
break;
}
preroot(Root);
cout<<endl;
layerorder(Root);
return 0;
}
如有错，请评论。