树的静态写法和遍历

1、存储结构

由于普通树的子节点的个数不定，所以使用指针域的方式不妥(需要在结构体中定义最大子节点数的节点类型的指针个数)。故使用静态写法，用数组下标来代替所谓的地址。虽然也需要在结构体中定义子节点的下标作为指针域。但可以使用STL中的vector容器进行动态分配。

struct node{
    typename data;//数据域
    vector<typename> child;//指针域，存放所有子节点的下标
}Node[maxn];//节点数组，maxn为节点的上限个数

2、新建一个节点

int index=0;
int newNode(int x){
    Node[index].data=x;//数据域为x
    Node[index].child.clear();//清空子节点
    return index++;//返回节点下标，并令index自增
}

3、先根遍历

void preOrder(int root){
    cout<<Node[root].data<<" ";//访问当前节点
    for(int i=0;i<Node[root].child.size();i++){
        preOrder(Node[root].child[i]);//递归访问节点root的所有子节点
    }
}

4、层序遍历

void LayerOrder(int root){
    queue<int> q;
    q.push(root);//根节点入队
    while(!q.empty()){
        int now=q.front();//取队首元素
        q.pop();//队首元素出队
        cout<<Node[now].data<<" ";//访问当前节点的数据域
        for(int i=0;i<Node[now].child.size();i++){
            q.push(Node[now].child[i]);//将当前节点的所有子节点入队
        }
    }
}

如果需要计算每个节点的层次，存储结构和层序遍历如下：

struct node{
    int layer;
    typename data;
    vector<typename> child;
}

void LayerOrder(int root){
    queue<int> q;
    q.push(root);//根节点入队
    Node[root].layer=1;
    while(!q.empty()){
        int now=q.front();//取队首元素
        q.pop();//队首元素出队
        cout<<Node[now].data<<" ";//访问当前节点的数据域
        for(int i=0;i<Node[now].child.size();i++){
            Node[Node[now].child[i]].layer=Node[now].layer+1;//子节点的层数加1
            q.push(Node[now].child[i]);//将当前节点的所有子节点入队
        }
    }
}