C++ 使用向量的二叉树

Question

我的任务是在向量中存储二叉树。在每个节点中存储一个 int ID、int Age 和一个字符串名称。

节点按 ID 在向量中存储和组织。

在向量中存储二叉树时，我使用算法 2i 和 2i+1 分别指定节点的左子节点和右子节点。

我已经设法创建了一个插入方法，我认为它满足这些条件并将一个节点插入到一个向量中，但是，在尝试将这些节点插入到向量中之后

50 21 蒂姆

75 22 史蒂夫

我注意到它实际上并没有将这些节点插入向量中。

我放置了一行在插入后打印索引，我发现在第一次插入后，索引不再更新。

一个例子运行使用这个例子的insert方法

我的 insert() 方法有问题吗？

这是我的代码。

#include "BinaryTree.h"
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int index = 0;

struct Node
{
    int ID;
    int age;
    string name;

    Node()
    {

    }

    Node(int id, int Age, string nm)
    {
        this->ID = id;
        this->age = Age;
        this->name = nm;
    }
};

vector<Node> binaryTree(30);


BST::BST()
{

}



void BST::start()
{
    int choice;


    cout << "What would you like to do?" << endl;
    cout << "1. Add a node to the tree" << endl;
    cout << "2. Delete a node from the tree" << endl;
    cout << "3. Find a node in the tree" << endl;
    cout << "4. Report the contents of the tree" << endl;
    cout << "5. Exit program" << endl;

    cin >> choice;

    if (choice == 1)
    {
        insert();
    }

    if (choice == 2)
    {
        Delete();
    }

    if (choice == 3)
    {
        find();
    }

    if (choice == 4)
    {
        report();
    }


}


void BST::insert()
{
    int ID;
    int AGE;
    string NAME;
    int root = 1;

    bool success = false;
    cout << "Please enter the ID number, age and name:" << endl;

    do
    {
        cin >> ID >> AGE >> NAME;
    } while (ID < 0);

    Node *tree = new Node(ID, AGE, NAME);


    if (index == 0)
    {
        binaryTree[1] = *tree;
    }

    if (index > 0)
    {
        do
        {
            if (tree->ID > binaryTree.at(root).ID)
            {
                root = 2 * root + 1;

            }

            if (tree->ID < binaryTree.at(root).ID)
            {
                root = 2 * root;
            }

            if (binaryTree.at(root).ID == NULL)
            {
                binaryTree.at(root) = *tree;
                cout << "Added!" << endl;
                cout << "Vector size: " << binaryTree.size() << endl;
                success = true;
            }
        } while (!success);
    }

    index++;
    cout << index << endl;
    delete tree;

    start();
}

编辑：我意识到我没有检查索引，所以我将它从“=”更改为“==”比较以启动循环。但是，现在我得到一个 _Xout_of_range("invalid vector subscript");向量抛出的异常 class

这里是错误。

Answer 1

do
{
    cin >> ID >> AGE >> NAME;
} while (ID < 0);

不是真正的问题，但你应该在这个操作后检查 std::cin 它的状态 - 如果用户确实输入了无效的输入 ("xyz")，cin 仍然处于失败状态，你不会'永远不会获得有效输入...此外，如果您使 id 和 age 无符号，则不必检查负输入。

我的个人变体：

for(;;)
{
    std::cin >> id >> age >> name;
    if(std::cin)
        // input is valid!
        break;
    std::cout << "invalid input" << std::endl; // some better text?
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

详情见this answer...

if (index = 0)
//        ^ this is an assignment! always sets index to 0 and then
//          checks the value; for COMPARISON, you need to use ==
{
    binaryTree[1] = *tree;
//             ^ and when do you ever fill index 0???
}

实际上是赋值而不是比较导致了您的问题！

如果 index 表示向量中元素的数量，您可以完全放弃它，改用 binaryTree.size()...

if (binaryTree.at(root).ID == NULL)
{
    binaryTree.at(root) = *tree;
    cout << "Vector size: " << binaryTree.size() << endl;
}

等等，你要用默认值预填充向量吗？？？如果是这样，binaryTree.size() 将总是具有相同的大小......并且您可能需要一个巨大的预分配数组并且可能会获得较差的填充等级。稍后再说。请注意 NULL 是一个表示空指针的宏（如果您真的要处理，请改用 nullptr 关键字！）。不要用它来进行整数比较，直接使用值0。

另外：如果向量不够大，at 将抛出异常。接着？更喜欢使用索引运算符，但在此之前，请检查向量是否足够大。如果不是，请适当增加矢量的大小（例如，使其成为之前大小的两倍）。

Node* tree = new Node(id, age, name);
binaryTree[x] = *tree;
delete tree;

那么，为什么还要在堆上呢？只需这样做：

Node             tree(id, age, name);
//  no pointer!  creating object directly on the stack!
binaryTree[x] = tree; // assign directly
// no delete necessary, object will be destructed automatically when leaving scope

在当前情况下没有必要，移动和复制的结果相同，但对于更复杂的对象，移动而不是复制可能会有价值，因此您可以优化为：

binaryTree[x] = std::move(tree); // creates an rvalue reference...

回到 size/fillgrade 问题：二叉树只有在保持平衡的情况下才有效率。通常，在运行时，如果存储在数组之类的结构中，例如向量，在内存中也是如此。所以你应该保持你的树平衡。变体可能不是从树的根开始，而是简单地在末尾附加元素（使用 push_back），然后向上移动，只要它大于父节点，如果在左树中，或小于，如果在正确的树中。如果提供移动构造函数，则可以使用 std::swap 来交换元素。这种替代方法还避免了标记值的需要 (node.id == 0)...

编辑回复您的评论：

OK，现在先让索引0也包含在算法中，不需要跳过位置0。

那么，您的问题可能已经是第一个插入：您确定向量确实已经包含两个虚拟元素了吗？最好考虑一下我们从一开始就有一个空向量。那么我们可以简单的做：

unsigned int index = 0;
// renaming root to index, assuming we dropped
// the other index variable already
// benefit: you can clearly differentiate my and your code...

Node node(id, age, name);
for(;;)
{
    if(index <= binaryTree.size()) // covers empty vector, too, as 0 <= 0...
    {
        binaryTree.resize(index + 1);
        // vector with size of n can store n elements
        // at indices [0 .. n - 1] - deduce the inverse yourself
        // and you know why index + 1...
        binaryTree[index] = node;
        // if we needed to resize, the new elements are unoccupied
        // anyway, so we simply can insert and are done...
        break;
    }
    if(binaryTree[index].id == 0)
    {
        // sentinel found, can insert here:
        binaryTree[index] = node;
        break;
    }
    // now calculate the child index just as before
}

下一个子索引的计算也有错误：

 if (tree->ID > binaryTree.at(root).ID)
     root = 2 * root + 1;

 if (tree->ID < binaryTree.at(root).ID)
     root = 2 * root;

如果 ID 相同呢？？？其中至少有一个也必须包含相等性，否则您将陷入无限循环。但是，一个条件正好与另一个条件相反，因此您可以简单地使用 if/else:

 if (node.id > binaryTree[index].id)
     index = 2 * index + 1;
 else
     index = 2 * index;

现在一些不错的调整：在 C++ 中，比较总是产生布尔值，然后将这些值提升为（无符号）int 总是得到 0 或 1，所以如果你愿意，你可以将上面的内容缩短为以下一行（好吧，我的重命名再次适用...）：

 index = 2 * index + (tree->ID > binaryTree[index].ID);

C++ 使用向量的二叉树

C++ Binary Tree Using Vector

c++

binary-tree

vector

binary-search-tree

data-structures