插入完全二叉树

Question

我正在尝试插入一个完整的二叉树来完成一项学校作业。我的树的结构是这样的

typedef struct TreeNode {
void * data;
struct TreeNode * left;
struct TreeNode * right;
struct TreeNode * parent;
} TNode;

typedef struct CompleteBinaryTree {
TNode * root;
TNode * last;
int numelm;
} CBTree;

我有4种插入方式视情况而定

树是空的
作为一个节点的树
CBT的最后一个节点是他的parent左child
最后我上树只要当前结点是他的右结点parent，如果当前结点不是根我就去找他哥往左下，否则我往左走

我目前卡在第三条路上，我不知道我的代码有什么问题。

有人能把我推向正确的方向吗？

谢谢！

void CBTreeInsert(CBTree* tree, void* data) {
    TNode * tmp = newTNode(data);
    TNode * curr = tree->last;

    if(tree->root == NULL) //empty
    { 
        tree->root = tmp;
    }
    else if(tree->last == tree->root) //one node
    {
        tree->last->left = tmp;
    }
    else if(tree->last->parent->right == NULL) //general
    {
        tree->last->parent->right = tmp;
    }
    else if(tree->last->parent == tree->last->parent->right) //degenarated
    {
        while(curr->parent == curr->parent->right)
                curr = curr->parent;

        if(curr != tree->root)
        {
            curr = curr->parent->right;
            while(curr->left != NULL)
                curr = curr->left;
        }
        curr->left = tmp;
        }
    else
        {
            while(curr->left != NULL)
                curr = curr->left;

            curr->left = tmp;
        }
}
else
{
    fprintf(stderr,"Error\n");
}

tree->last = tmp;
tree->numelm++;
}

Answer 1

我想你或多或少有过，但是：

我没看到新节点的tmp->parent设置在哪里？
else if(tree->last->parent == tree->last->parent->right)坏了，我觉得应该是else if(tree->last == tree->last->parent->right)，到时候肯定是真的
while(curr->parent == curr->parent->right) curr = curr->parent; 对 curr == tree->root 可能会有问题，但可以通过设置 tree->root->parent = tree->root
你有两个副本：

    while(curr->left != NULL)
    {
        curr = curr->left;
    }
    curr->left = tmp;`

我很想这样做：

else if (tree->last == tree->last->parent->right)
{
    TNode * curr = tree->last->parent ; // NB: know that tree->last != tree->root
                                        //     so can step up.  
    while (1)
    {
        if (curr == tree->root)
            break ;

        if (curr == curr->parent->left)
        {
            // The parent of the curr node is to the right of the last node, so
            // step to its right, and then insert to the extreme left of that.
            curr = curr->parent->right ;
            assert(curr != NULL) ;
            break ;
        } ;
        curr = curr->parent ;
    } ;

    // Arrive here with curr as root of sub-tree in which now want to insert the
    // new node as the left-most child.

    while (curr->left != NULL)
    {
        assert(curr->right != NULL) ;
        curr = curr->left ;
    } ;
    assert(curr->right == NULL) ;
    tmp->parent = curr ;
    curr->left  = tree->last = tmp;
}

但我还没有测试过这个。（还有其他地方需要设置tmp->parent。）

插入完全二叉树

Inserting in a Complete Binary Tree

c

binary-tree

if-statement

while-loop