Вставка в полное двоичное дерево - PullRequest
Новая
       3

Вставка в полное двоичное дерево

1 голос
/ 10 февраля 2020

Я пытаюсь вставить в полное двоичное дерево школьное задание. Структура моего дерева такова 

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 является его родительский левый потомок
  • Наконец, я go вверх по дереву, пока текущий узел является правым узлом его родителя, если текущий узел не root Я передам go его брату и go вниз влево, иначе я просто go вниз влево

В настоящее время я застрял на своем третьем пути, и я не ' Я не знаю, что не так с моим кодом.

Может ли кто-нибудь направить меня sh в правильном направлении.

Спасибо! 

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++;
}

1 Ответ

0 голосов
/ 10 февраля 2020

Я думаю, что у вас более или менее было это, но:

  1. Я не вижу, где установлен новый узел tmp->parent?

  2. else if(tree->last->parent == tree->last->parent->right) сломан, я думаю, что это должно быть else if(tree->last == tree->last->parent->right), что определенно должно быть верно в этой точке.

  3. while(curr->parent == curr->parent->right) curr = curr->parent; может быть проблематичным c для curr == tree->root, хотя это можно обойти, установив tree->root->parent = tree->root

  4. у вас есть две копии: 

    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.)

...