普通树的一些操作，杂记



 //树的数据结构，静态实现  struct Node{ typename data; //数据域 vector child; //指针域，存放所有子结点的下标  }node[maxn]; //结点数组，maxn为结点上限个数 //新建一个树结点，但是，一般考试中设计树（非二叉树）的考查时， //一般都给出了结点的编号，我们可以把给定的编号直接作为node数组的 //下标来使用。  int index=0; int new_node(int v) { node[index].data =v; node[index].child.clear(); //清空子结点 return index++; //返回结点下标，并令index自增  } //如果题目中不涉及结点的数据域只需要数的结构 //简化为： vector<int> child[maxn] //树的先根遍历 void preorder(int root) { printf("%d ",node[root].data); //访问当前结点 for(int i=0;i<node[root].child.size();i++) { preorder(node[root].child[i]); //递归访问结点root的所有子结点  } } //树的层序遍历 void layerorder(int root) { queue<int> queue; queue.push(root); while(!queue.empty()) { int front=queue.front(); printf("%d ",node[front].data); //访问当前结点的数据 queue.pop(); for(int i=0;i<node[front].child.size();i++) { queue.push(node[front].child[i]); //将当前结点的所有子结点如队列  } } } //带 层 的树的数据结构静态实现 struct Node{ int layer; //记录层号  int data; vector<int> child; }node[maxn]; //新的树的 层序遍历 void layerorder(int root) { queue<int> queue; queue.push(root); node[root].layer=1; while(!queue.empty()) { int front=queue.front(); //取出队首元素  printf("%d ",node[front].data); queue.pop(); for(int i=0;i<node[front].child.size();i++) { int child=node[front].child[i]; node[child].layer=node[front].layer+1; queue.push(child); //将当前结点的所有子结点入队列  } } }