c++ - 如何使用从 C++ 中的 vector 读取的值启动二叉树？

Question

我正在尝试对用 C++ 实现的二叉树运行一些测试。我使用一个结构来创建树节点:

    struct TreeNode
    {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

我想测试它是否是平衡二叉树，倒置二叉树等。所以我必须像这样启动一棵树:

   4
    \
     2
    /
   6

...对于 vector 输入 = {4, NULL, 2, 6}，或 {4, -9999, 2, 6} 如果 C++ 不能在一个 vector 中采用不同类型(可以吗？)。

但我能找到的所有二叉树节点插入的 C++ 实现都是关于根据节点的值插入节点，这实际上创建了一个有序的二叉搜索树。

我想知道是否以及如何仅基于输入 vector 创建二叉树，并将第一个 (input[0]) 值作为根值？

Answer 1

不，C++ vector 不能在同一个 vector 中包含不同的类型(不过，如果你非常想这样做，你可以创建类似于 vector<boost::variant> 或类似的东西)。它适用于 {4, NULL, 2, 6} 的特定情况, 但可能不会产生您想要的效果( NULL 是一个扩展为值为 0 的整数常量的宏，因此它与 {4, 0, 2, 6} 基本相同，并且代码不会有任何方法知道这个零是不寻常的，并且只会将值为 0 的节点插入树中。

是的，完全有可能创建一棵树，它只按照给定的顺序创建和插入节点，而不是尝试创建排序的二叉搜索树。一旦决定了指定特定分支结束的方法，您只需创建节点并将它们拼接到树上。当您到达特定分支的末尾时，跟踪开始添加下一个节点的正确位置可能有点挑剔，但除此之外一切都非常简单。