將二叉樹轉換爲排序數組

有沒有辦法將Binary變爲排序數組而不必遍歷每個數組索引的樹？將二叉樹轉換爲排序數組

Node root; 
Node runner; 
int current_smallest; 

void findsmallest(Node root){ 
    //Pre-order traversal 
    if(root == null){ 
     return; 
    }else{ 
     runner = root; 
     if(current_smallest == null){ 
      current_smallest = runner.element; 
     }else{ 
      if(current_smallest > runner.element){ 
      current_smallest = runner.element; 
      } 
     } 
     findsmallest(runner.left); 
     findsmallest(runner.right); 
    } 
} 

void fill_array(int [] array){ 

    for(int i =0; i < array.length(); i++){ 
     findsmallest(root); 
     array[i] = current_smallest; 
    } 
}

正如您所看到的，如果樹中有很多節點，可能需要很長時間。順便說一句，我忘了顯示整個樹將不得不遍歷在開始獲得數組的長度。

來源

2013-04-23 Adegoke A

二叉樹可以用數組表示;如果是這種情況，你需要做的就是對數組進行排序。

這裏有代表陣列中的樹一些更多的信息：wikipedia

這不一定是最節省空間的表示; 「帶引用的節點」表示可能會浪費更少的空間。

來源

2013-04-23 23:02:55 Tom

你需要的是一箇中序遍歷，這是一般遞歸實現，如：

遍歷左子樹。
處理該節點（即插入數組中的下一個元素）
遍歷右子樹。

來源

2013-04-23 23:04:35 femtoRgon

是的，你可以這樣做：運行樹的in-order traversal，保留數組的當前位置，並將節點的值存儲在數組的當前位置。

您可以遞歸地進行按順序遍歷，或者您可以使用堆棧數據結構進行按順序遍歷。如果你想遞歸地做到這一點，你可以這樣做：

int fill_array(Node root, int [] array, int pos) { 
    if (root.left != null) { 
     pos = fill_array(root.left, array, pos); 
    } 
    array[pos++] = root.element; 
    if (root.right != null) { 
     pos = fill_array(root.right, array, pos); 
    } 
    return pos; // return the last position filled in by this invocation 
}

注意，爲了使上述遞歸過程的工作，調用者必須在array傳遞給函數分配足夠的空間。

來源

2013-04-23 23:04:42 dasblinkenlight

將二叉樹轉換爲排序數組

回答

相關問題