使用树排序来修改数组

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