由于无法确定子节点个数，因此需要使用STL中的vector，即长度根据实际需要而自动变化的“数组”。

定义：

//树的定义 
struct Node{
   
	int data;//数据域
	vector<int> child; 
	int level;
}node[maxn];

新建结点：

//新建结点
int index=0;
int newNode(int data){
   
	node[index].data=data;
	node[index].child.clear();//清空子节点
	return index++; 
}
  • 在考试中涉及树（非二叉树）的考查时，一般都是很人性化的给出了结点的编号，并且编号一定是0,1，…，N-1 。在这种情况下，就不需要newNode函数，题目给定的编号作为node【maxn】数组的下标。
  • 如果题目中不涉及结点的数据域，即只需要树的结构，简化携程vector数组 
vector<int> child[maxn];
  • 树的DFS过程就是先序遍历的过程
  • 树的BFS过程就是层序遍历的过程

先序遍历

void preorder(int root){
   
	printf("%d ",node[root].data);
	for(int i=0;i<node[root].child.size();i++){
   
		preorder(node[root].child[i]);
	}
}

层序遍历

void levelorder(int root){
   
	queue<int> q;
	q.push(root);
	node[root].level=0;//记根结点的层号为0 
	while(!q.empty()){
   
		int front=q.front();
		printf("%d ",node[front].data);
		q.pop();
		for(int i=0;i<node[front].child.size();i++){
   
			int child=node[front].child[i];//当前结点的第i个子结点的编号
			//子结点层号为当前结点层号加1
			node[child].level=node[front].level+1; 
			q.push(node[front].child[i]);
		}
	}
}

（暂未实现）题目链接：

1004 Counting Leaves (30)

1053 Path of Equal Weight (30)

1079 Total Sales of Supply Chain (25)

1090 Highest Price in Supply Chain (25)

1094 The Largest Generation (25)

1106 Lowest Price in Supply Chain (25)