我很难弄清楚如何为我的班级平衡 AVL 树。我已经用这个插入了它:
Node* Tree::insert(int d)
{
cout << "base insert\t" << d << endl;
if (head == NULL)
return (head = new Node(d));
else
return insert(head, d);
}
Node* Tree::insert(Node*& current, int d)
{
cout << "insert\t" << d << endl;
if (current == NULL)
current = new Node(d);
else if (d < current->data) {
insert(current->lchild, d);
if (height(current->lchild) - height(current->rchild)) {
if (d < current->lchild->getData())
rotateLeftOnce(current);
else
rotateLeftTwice(current);
}
}
else if (d > current->getData()) {
insert(current->rchild, d);
if (height(current->rchild) - height(current->lchild)) {
if (d > current->rchild->getData())
rotateRightOnce(current);
else
rotateRightTwice(current);
}
}
return current;
}
我的计划是调用 balance() 检查树是否需要平衡,然后根据需要进行平衡。问题是,我什至不知道如何遍历树来找到正确的不平衡节点。我知道如何递归地遍历树,但我似乎无法将该算法转换为找到最低的不平衡节点。我在编写迭代算法时也遇到了麻烦。任何帮助,将不胜感激。:)