C++ 使用数组结构创建平衡二叉搜索树

Question

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

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

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

我已经设法创建了一个我认为满足这些条件的插入方法，但是由于某种原因，在尝试打印我的 vector 值时，我似乎得到了负值。对于这个特定示例，我插入以下值

100 21 斯坦

50 30 菲尔

我尝试放置另一个节点

30 31 爱丽丝

根据消息来源，这会导致树变得不平衡。

所以我尝试使用存储在 vector 中的节点创建一个平衡的二叉搜索树。之前我使用之前的插入结构创建了一个不平衡树。但是，我不太明白平衡二叉搜索树是什么

所以我的问题如下:

1. 什么是平衡二叉搜索树？

2. 您有什么建议我应该更改插入函数以鼓励创建平衡树？

提前致谢!

这是我的代码:

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

using namespace std;
int index = 0;

struct Node
{
    int ID = -1;
    int age = -1;
    string name = "";

    Node()
    {


    }

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

vector<Node> binaryTree;


BST::BST()
{

}





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

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


    cin >> ID >> AGE >> NAME;

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



    if (!binaryTree.empty())
    {
        do
        {
            if (tree->ID > binaryTree.at(root).ID && binaryTree.at(root).ID != 0)
            {
                root = 2 * root + 2;
                if (root >= binaryTree.size()) binaryTree.resize((2 * root + 2 + 1) * 5);

            }

            if (tree->ID < binaryTree.at(root).ID && binaryTree.at(root).ID != 0)
            {
                root = 2 * root + 1;
                if (root >= binaryTree.size()) binaryTree.resize((2 * root + 2 + 1) * 5);

            }

            if (binaryTree.at(root).ID == -1)
            {
                binaryTree[root] = *tree;
                success = true;
            }
        } while (!success);
    }

    if (binaryTree.empty())
    {
        binaryTree.push_back(*tree);
    }

    delete tree;

}

Answer 1

我会使用 heap ，平衡二叉树的最极端形式(数组中的所有索引必须已满才能使用下一个索引)。

您正在使用的 2i、2i+1 算法应该可以正常工作(记住不要使用 0 索引)。

要插入，您可以执行以下操作:

1) 在数组中第一个未使用的索引处添加新元素。

2) 对其使用upheap算法。其工作方式是将元素与其父元素进行比较，并根据树的属性进行交换(例如，如果子元素 > 父元素，则在最大堆中进行交换)。您递归地执行此操作，直到树的根(索引 1)。这需要 O(log n) 时间。

这应该为您提供一个完美平衡的二叉树和一个数组实现。