使用向量 return 类型遍历二叉树

Question

我正在尝试使用键值对和 return 所有值的向量遍历模板化 AVLtree。

当使用 cout 语句时，我可以看出该函数正在正确遍历树并且它将 return 树中的所有值。但是，当我尝试将其添加到向量中并在程序的另一部分中使用它时，只存储了根节点。


    vector<s> treeTraversal(){
         return treeTraversal(root);
    }

    vector<s> treeTraversal(AVLNode<t, s> *node ){
        vector<s> temp;

        if(node != nullptr){
            treeTraversal(node -> left);
            treeTraversal(node -> right);
            temp.push_back(node -> vectorToBe);
        }

        return temp;
    }

我打算将所有 returned 值存储在一个向量中，以便我可以在程序的后面部分访问它们

Answer 1

treeTraversal(node -> left);

这个递归调用函数，这是两个递归调用之一。您的 treeTraversal() 函数 return 是一个向量。然而，在这里，它的 return 值被丢弃并且没有存储在任何地方。

return temp;

这是您的函数 return 的向量。但是，正如我们所见，它不包括任何递归调用 returned 的任何内容，因为那些 returned 值被丢弃并被忽略。

有两种常用方法可以解决此问题：

不要忽略来自两个递归调用的 returned 向量。存储它们，然后将它们的内容附加到 temp.
而不是 returning std::vector 使其成为递归调用的附加参数。每个递归调用只是将其值附加到传入的向量（并将其转发给任何后续递归调用）。递归函数的调用者将负责实例化一个初始为空的向量，并将其传入。

Answer 2

我会尝试这样的事情。您将避免在堆栈中创建大量 vector<s>。

vector<s> treeTraversal(){
     vector<s> result;
     treeTraversal(root, result);
     return result;
}

void treeTraversal(AVLNode<t, s> *node, vector<s>& visited ){
    if(node != nullptr){
        treeTraversal(node -> left, visited);
        treeTraversal(node -> right, visited);
        visited.push_back(node->vectorToBe);
    }
}

使用向量 return 类型遍历二叉树

Traversing a binary tree using a vector return type

c++

vector

binary-search-tree

nodes