使用樹排序來修改數組

Question

我正在尋找使用樹排序來存儲排序在數組中的數字，而不是僅僅按排序順序輸出數字。 n被初始化爲零。

void BinSearchTree::inOrder(TreeNodePtr subRoot, int A[], int n) 
{ 
    if (subRoot != NULL)    
    { 
     inOrder(subRoot->left, A, n);  

     A[n] = subRoot->key; 
     n++; 

     inOrder(subRoot->right, A, n); 
    } 
} 

我相信問題在於我繼續把A作爲inOrder的一個參數，但我不知道我該怎麼做。

Answer 1

你應該到n的引用，否則你無法知道什麼是分配的下一個元素，那就是：

void BinSearchTree::inOrder(TreeNodePtr subRoot, int A[], int& last) 
{ 
    if (subRoot != NULL)    
    { 
     inOrder(subRoot->left, A, n);  

     A[last++] = subRoot->key; 

     inOrder(subRoot->right, A, n); 
    } 
} 

其他選項是使用一個容器象一個功能的push_back矢量：

void BinSearchTree::inOrder(TreeNodePtr subRoot, std::vector<int>& vec) 
    { 
     if (subRoot != NULL)    
     { 
      inOrder(subRoot->left, vec);  

      vec.push_back(subRoot->key); 

      inOrder(subRoot->right, vec); 
     } 
    }