如何構建一個給定水平順序遍歷的樹？

我已經讀過類似的question這個問題，但我不需要建立一個BST。如何構建一個給定水平順序遍歷的樹？

從給定的輸入，例如：2 0 3 0 1 0 3，將建立： input to tree

說明：

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(); 
    } 
}

來源

2014-12-29 Mark

你有任何僞代碼或什麼的，你明白這個問題嗎？ –

編輯了這個問題。我從ftree開始（0，-1） – Mark

此刻這個問題聽起來更像是一個謎語，很難弄清楚數字和樹之間的關係（root 2 3 1 3？），並且理解你正在努力去做。解決這個問題的一種方法是理解代碼，但是由於你有問題，假設代碼是*正確的* ... *澄清*是有點危險的。 –

最簡單的方法一棵樹，爲我工作，是第一構建樹，然後才能分叉樹並生成進程樹。

對於構建樹我做了一個結構的目的，這將代表節點：

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隊列對於這個特殊問題非常有用。

特別感謝我的coleague，這幫助我完成了這件事。

來源

2015-01-01 15:10:16 Mark

如何構建一個給定水平順序遍歷的樹？

回答

相關問題