0

我正在向您发布使用我开发的AVL 树的代码。插入的方法，avlinsert方法如下。我在纸上开发了这段代码，它没有经过测试，但我希望这能奏效。我要讨论的主要问题是节点的平衡因子首先看代码。通过这种方式，这个想法将变得清晰，我想问什么。所以这里是代码：

    treeNode* avlinsert(treeNode* tree, int info)
    {
        treeNode* newNode=new treeNode;
        newNode->setinfo(info);
        newNode->setbalance(0);
        treeNode* p,*q;
        bool duplicate=false;
        p=q=tree;
        stack s; //I have made this stack already and now I am using it here.
        //Now the the while loop block will check for duplicate nodes, this block prevents the duplicate insertion.
        while (q!=NULL)
        {
            p=q;
            if (info < p -> getinfo())
                q=p->getleft();
            else if (info>p->getinfo())
                q=p->getright();
            else
            {
                duplicate=true;
                cout<<"Trying to insert duplicate";
                break;
            }
        }//while loop ended.
        //Now checking for duplicates.
        if (duplicate)
            return tree;
        p=q=tree;
        //Now below is the main block of while loop which calculates the balance factors of nodes and helps in inserting nodes at proper positions.
        while (q!=NULL)
        {
            p=q;
            if (info < p -> getinfo())
            {
                p->setbalance(p -> getbalance()+1);
                s.push(p);//pushing into stack
                q=p->getleft();
            }

            else if (info > p -> getinfo())
            {

                p->setbalance(p->getbalance()-1);
                q=p->getright();
            }

        }//while loop ended
        //Now the below code block will actually inserts nodes.
        if (info < p -> getinfo())
            p->setleft(newNode);
        else if (info > p -> getinfo())
            p->setright(newNode);
        //After this insertion we need to check the balance factor of the nodesand perform the approprite rotations.

        while (!s.isempty())
        {
            treeNode node;
            node=s.pop();
            int balance;
            balance=node.getbalance();
            if (balance==2)
            {
                s.Makeempty();   // We have found the node whoes balance factor is violating avl condition so we don't need other nodes in the stack, therefor we are making stack empty.
                treeNode* k1,*k3;
                k1=&node; //This is the node whoes balance factor is violating AVL condition.
                k3=&(k1 -> getleft()); //Root of the left subtree of k1.
                //Identifying the cases of insertion
                if (info < k3 -> getinfo())  //This is the case of insertion in left subtree of  left child of k1 here we need single right rotation.
                    root=Rightrotation(k1);  //Here root is the private data member.

                //Next case is the insertion in right subtree of left child of k1.
                if (info > k3 ->getinfo())
                    root=LeftRightrotation(k1);
            }//end of if statement.
        }//while loop ended

这不是全部代码，但足以向您展示我正在尝试做的事情。您已经在这段代码中看到我在插入期间设置节点的平衡因子（第二个 while 循环块）。好的，这很好。但是在插入之后，我需要执行旋转。我也有旋转代码，但主要问题是当节点旋转时，我需要重置旋转代码中节点的平衡因子。这就是我的问题。我该怎么做？代码片段是什么？

4

1 回答 1

1

“……我需要重置轮换代码中节点的平衡因子。”

如果您想在旋转代码中添加一些内容，那么也许您还应该发布旋转函数的代码以获得帮助。

否则，如果您只想在旋转后更新每个节点的平衡因子，那么这个递归函数可能会对您有所帮助（只需调用它并传递树的根节点）：

int updateBalanceFactors(treeNode *node)
{
    if(node == NULL)
        return 0;
    node->setbalance(updateBalanceFactors(node->getright()) - updateBalanceFactors(node->getleft()));
    return ((node->getbalance() < 0 ? -node->getbalance() : node->getbalance()) + 1);
}

此外，我在您的代码中发现了一些错误，但我敢肯定，当您尝试运行程序时，您会发现它们。需要记住的一些事项：

  1. 我不确定您的堆栈实现是如何工作的，但我看到您将一个指针推入堆栈，然后弹出一个对象：

    s.push(p);

    树节点节点 = s.pop();

  2. 只有在遍历 AVL 树的左子树时才将节点推入堆栈，而不是在向右移动时。这是为什么？

  3. 当您将 newNode 插入树时，请记住将 newNode 的左右子节点设置为 NULL（也许您已经在构造函数中这样做了，但我不确定）。

  4. 通常，在 AVL 树中，当一个节点的左子树高于右子树时，该节点的平衡因子为负。您可能想在代码中更改它。如果你想保持这种状态，你将不得不改变我的递归函数。

  5. 最后但同样重要的是，您检查平衡因子是否等于 2（如果您的树需要旋转）。请记住，平衡因子也可以取负值（如果左子树高于右子树）。

祝大家新年快乐 ：-）

于 2009-12-31T20:38:03.037 回答