c++ - 使用树排序修改数组

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