c - 给定层序遍历如何构造树？

Question

我读过类似的question在这件事上，但我不需要建立 BST。

根据给定的输入，例如:2 0 3 0 1 0 3，它将构建:

解释:

2 -> the root has 2 children
0 -> the left child of the root has no children
3 -> the rigth child of the root has 3 children
0 -> the leftmost child on the second level (whose grandparen is the root) has no children
1 -> the middle child on the second level has 1 child
0 -> the right most child on the second level has no children
3 -> the only node on the third level has 3 children
<empty> -> the nodes on the last level have no children

我的问题是获取节点的子节点的索引。

我的想法是获取父节点索引的值，然后将计数器添加到它，我遇到的问题是如果节点没有任何子节点会发生什么？所有其他的都向右移动 1。

请给我一些建议。

编辑:这是我用来生成树的代码块: 它必须构建给定序列的进程树

void ftree(int index, int parentIndex) {
    int i, tmp, pid, child;
    if(input[index] == 0){
        sleep(1);
    } else if(index >= inputSize) {
        sleep(1);
    } else if(index < inputSize) {
        for(i = 0; i < input[index]; i++) {
            if(parentIndex == -1) {
                child = 1;
            } else {
                child = index + input[parentIndex] + i; // here is the calculation of the index of the child
            }
            pid = fork();
            if (pid == 0) {
                ftree(child, index);
                break;
            }
        }
    }
    if(getpid() == pidOrg) {
        pid = fork();
        if(pid == 0) {
            execlp("pstree", "pstree", pidString, "-c", NULL); 
        } else {
            wait();
        }
    } else {
        wait();
    }
}

Answer 1

对我有用的最简单的方法是首先构建树，然后才 fork 树并生成进程树。

为了构建一棵树，我制作了一个表示节点的结构:

typedef struct _node {
    int val; // how many children the node has
    struct _node **children; // all the children of the node
} node, *pNode;

还有一个表示队列的结构:

typedef struct _queue {
    pNode el;
    struct _queueInt *next;
} queue, *pQueue;

然后我检查输入并将新节点添加到队列中(首先手动添加根节点，然后在队列不为空时添加其他节点)，同时构建树结构。

我发现 ADT 队列非常适合这个特定的问题。

特别感谢我的一位同事帮助我完成了这项工作。