C语言-树的遍历

0x00、树的静态写法

    之前刷PAT的过程中已经接触过树的静态写法了，不过之前接触过的都是二叉树，这里是树。

使用数组当做内存，下标当做地址，即可存放静态树。比如这样：

struct node{
    ElementType data;    //数据域
    int child[MAX];    //孩子域
}Node[MAX];

这里MAX是最大节点个数，因为C语言中数组大小是固定的，所以必须定义这个MAX。当然也可以使用vector存放孩子节点的地址，使得孩子的量可变：

struct node{
    ElementType data;
    vector<int> child;
}Node[MAX];

这样，我们就定义了一个二叉树的节点类型。

0x01、树的先根遍历

和二叉树的先序遍历一样，二叉树是固定的有两个孩子，而树是不固定的。所以我们要将孩子域的数组遍历一遍，遍历数组每一个孩子。

先根遍历，顾名思义，要先遍历根部。这里我们仍然使用递归进行遍历：

Void PreOrder(int root){
    printf("%d ", Node[root].data);    //访问数据域数据
    for(int i = 0; i < Node[root].child[i])
        PreOrder(Node[root].child[i]);
}

我们明显的发现，上面的代码并没有递归边界，这是因为数组遍历完成后，递归就退出了，所以我们不需要递归边界。

0x02、树的层序遍历

    和二叉树一样，树也存在着层序遍历。我们可以使用队列来实现：

Void LayerOrder（int root）{
    queue<int> Q;
    Q.push(root);
    while(!Q.empty()){
        int front = Q.front();
        Q.pop();
        for(int i = 0; i < Node[front].child.size(); i++)
            Q.push(Node[front].child[i]);
    }
}

如果我们需要获取层次信息，我们可以在结构体中定义layer：

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

在遍历中只需要加上判断层号的代码即可