【算法笔记】一般意义上的树的基本操作集

简介

这里的树指的是一般意义上的树，即子结点个数不限且没有先后次序的树，并不仅仅是二叉树。

这里采用的是树的静态写法~

（参考《算法笔记》）

代码

struct node{int data, layer;vector<int> child;  //指针域，存放所有子结点的下标 
} Node[maxn];  //结点数组 int index = 0;
int newNode(int v) {Node[index].data = v;Node[index].child.clear();  //清空子结点return index++; 
}//树的先根遍历 
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 layerOrder(int root) {queue<int> q;Node[root].layer = 1;q.push(root);int now;while (!q.empty()) {now = q.front();q.pop();for (int i = 0; i < Node[now].child.size(); ++i) {int child = Node[now].child[i];Node[child].layer = Node[now].layer + 1;q.push(child);}}
}

例题

原题地址

应用即为PAT甲级的一题：

1053 Path of Equal Weight (30分)

参考代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef double db;
typedef long long LL;
typedef vector<int> VI;
const int inf = 2e9;
const LL INF = 8e18;
const int maxn = 110;int n, m, S;  //结点数、边数、给定的和 
int path[maxn];  //记录路径 struct node{int w;vector<int> child;
}Node[maxn];bool cmp(int a, int b) {return Node[a].w > Node[b].w;
} //当前访问结点为index，numNode为当前路径上结点个数 
void DFS(int index, int numNode, int sum) {if (sum > S) return;if (sum == S) {//还没到叶子结点，直接输出 if (Node[index].child.size()) return; //到达叶子结点，path中存放了完整路径，输出for (int i = 0; i < numNode; ++i) {if (i) printf(" ");printf("%d", Node[path[i]].w);}printf("\n");return;}for (int i = 0; i < Node[index].child.size(); ++i) {int child = Node[index].child[i];path[numNode] = child;  //将结点加到路径末尾 DFS(child, numNode + 1, sum + Node[child].w);}
}int main() {scanf("%d%d%d", &n, &m, &S);for (int i = 0; i < n; ++i) {scanf("%d", &Node[i].w);}int idx, k, tmp;for (int i = 0; i < m; ++i) {scanf("%d%d", &idx, &k);for (int i = 0; i < k; ++i) {scanf("%d", &tmp);Node[idx].child.pb(tmp);}sort(Node[idx].child.begin(), Node[idx].child.end(), cmp);} path[0] = 0;  //路径第一个点为0号结点 DFS(0, 1, Node[0].w);  //目前已有1个结点 return 0;
}