我正在尝试实现 AVL 树,但不确定插入和跟踪每个节点的父节点的最佳方法。这是教育性的,所以请不要建议“使用提升”:)
这可以编译,但我不相信它的正确性或者它是最好的方法。具体来说这个
insert(someNumber,root,root);
此外,当我重新平衡并向上移动树时,我将重做高度部分。
我这样插入
myTree.insert(someNumber);
这是方法。我不确定我的第二个参数应该在这里。我会认为 NULL 但编译器不喜欢这样(不同的函数定义)。
void Tree::insert(int someNumber){
insert(someNumber,root,root);
}
这是我的插入
void Tree::insert(int someNumber,Node*& subTreeRoot,Node*& parent){
if(subTreeRoot==NULL)
{
subTreeRoot = new Node(someNumber,parent);
if(subTreeRoot->myParent)
}
else if (someNumber<subTreeRoot->myNumber)
{
if((subTreeRoot->right==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
subTreeRoot->height++;
insert(someNumber,subTreeRoot->left,subTreeRoot);
}
else
{
if((subTreeRoot->left==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
subTreeRoot->height++;
insert(someNumber,subTreeRoot->right,subTreeRoot);
}
}
-