的任务是在向量中存储二叉树。每个节点中存储一个 int ID、int Age 和一个字符串名称。
节点按 ID 在矢量中存储和组织。
当将二叉树存储在向量中时，我使用算法 2i 和 2i+1 分别指示节点的左子节点和右子节点。
我已经设法创建了一个我认为满足这些条件的插入方法，但是由于某种原因，在尝试打印我的矢量值时，我似乎得到了负值。对于此特定示例，我插入以下值
100 21 斯坦
50 30 菲尔
我尝试放置另一个节点
30 31 爱丽丝
据消息人士称，这会导致树变得不平衡。
所以我正在尝试使用存储在向量的节点创建一个平衡的二叉搜索树。之前，我使用以前的插入结构创建了一个不平衡树。但是，我不完全了解什么是平衡的二叉搜索树
所以我的问题如下：
-
究竟什么是平衡二叉搜索树？
-
您建议我应该更改插入函数以鼓励创建平衡树吗？
提前感谢！
这是我的代码：
#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;
}
我会使用堆，这是平衡二叉树的最极端形式(数组中的所有索引都必须已满才能使用下一个索引)。
您使用的2i，2i+1算法应该可以正常工作(请记住保持0索引未使用)。
要插入，您可以执行以下操作：
1) 在数组中第一个未使用的索引处添加新元素。
2) 使用upheap算法。其工作方式是将元素与其父元素进行比较，并根据树的属性进行交换(例如，如果子元素>父元素，则在最大堆中)。您可以递归地执行此操作，直到树的根(索引 1)。这需要O(log n)时间。
这应该会给你一个完美平衡的二叉树和一个数组实现。