將一個二進制搜索樹壓平成一個列表

typedef struct node *blah; 

int *breath_search(struct node *root){ 

    int *numbers = calloc(20,sizeof(*numbers)); int listpointer = 0; 
    struct node **currentlist = calloc(20,sizeof(struct node*)); 
    struct node **updatedlist = calloc(20,sizeof(struct node*)); 
    currentlist[0] = root; 
    int iterations = 1; 

    int depths = 3; 
    while(depths){ 


     int i = 0; int j; 
     for(j=0;j<iterations;j++){ 
      if(currentlist[j] == NULL){ 
       updatedlist[i] = NULL; i++; 
       updatedlist[i] = NULL; i++; 
       numbers[listpointer] = 0; listpointer++; 
      } 
      else if(currentlist[j] != NULL){ 
       updatedlist[i] = currentlist[j]->left; i++; 
       updatedlist[i] = currentlist[j]->right; i++; 
       numbers[listpointer] = (int) alpabatise(currentlist[j]->newitem.key); listpointer++; 
      } 
     } 

     currentlist = updatedlist; 
     updatedlist = (blah[])  {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL}; 
     iterations = iterations*2; 

     depths--; 

    } 

    return numbers; 
}

我一直在看這個代碼幾個小時，它沒有任何意義，爲什麼它不工作。我打算給這個函數一個節點，它會返回給我一個指針，一個包含二叉樹中所有數字的列表。將一個二進制搜索樹壓平成一個列表

我二叉樹就像

 231 
    / \ 
    82  247 
/\ /\ 
    80 137 NULL 263

我的函數只返回一個指向列出

231,82,247,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

我預計

231,82,247,80,137,0,263,0,0,0,0,0,0...

來源

2015-12-10 Charana

你有什麼證據表明它試圖處理任何低於root的節點？ –

我有一個節點'當前列表'（最初是根節點）的列表，然後我將這些節點的所有節點存儲在'更新列表'中，這個新的更新列表然後成爲'當前列表'，並且它每次都會繼續創建一個當前列表，其中所有節點都低於前一個深度，除非我的邏輯錯誤 – Charana

我沒有多看它，但爲了檢索該列表，可以簡單地執行「Inorder Traversal」並將數據追加到列表中。 – bholagabbar

我相信，在你的代碼中的錯誤該行::

updatedlist = (blah[]) {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL};

我懷疑是一種有效的語法。因爲，你正試圖分配一個新的數組，你可以保存你剛纔訪問過的節點的子節點，所以calloc是一個新的數組，你可以在你的代碼中使用它。

因此，上述行應改變這種::

updatedlist = calloc(20,sizeof(struct node*));

的幾點，你應考慮採取，而分配這麼多的內存，以釋放它的不再是記憶使用，因爲C沒有明確地爲你做，你需要自己照顧，以避免任何內存泄漏。因爲，在while循環的每次迭代後，currentList是沒用的，你要添加的聲明（分配updatedList到currentList之前）

free(currentList);

，並在程序結束時釋放的updatedList爲好。其次，你現在正在做的事情就像二叉樹的層次遍歷一樣。所以，你可以嘗試使用STL queue，並且不需要像你在做的那樣創建和交換數組。像這樣的東西::

int *breath_search(struct node *root){ 

    int *numbers = calloc(20,sizeof(*numbers)); 
    int listpointer = 0; 
    queue<node*> q; 
    q.push(root); 
    int iterations = 1; 

    int depths = 3; 
    while(depths){ 
     int i = 0, j; 
     for(j=0; j<iterations; j++){ 
      node* currentNode = q.pop(); 
      if(currentNode == NULL){ 
       q.push(NULL); 
       q.push(NULL); 
       numbers[listpointer] = 0; 
       listpointer++; 
      } 
      else if(currentNode != NULL){ 
       q.push(currentNode->left); 
       q.push(currentNode->right); 
       numbers[listpointer] = (int) alpabatise(currentlist[j]->newitem.key); 
       listpointer++; 
      } 
     } 
     iterations = iterations*2; 
     depths--; 
    } 
    return numbers; 
}

我相信這會是一個更好的方法來做到這一點，因爲你不必保持對分配和釋放內存，因此它減輕該開銷。我使用STL隊列，你絕對可以使用你自己的隊列。

來源

2015-12-10 19:08:52 user007

將一個二進制搜索樹壓平成一個列表

回答

相關問題