Невозможно вставить / распечатать все дерево двоичного поиска

Question

Я пытаюсь создать свою собственную библиотеку дерева двоичного поиска (BST) на языке C. Однако мне трудно вставить или распечатать все двоичное дерево. Подробно, это структура каждого двоичного узла, в котором Object уже был предопределен.

struct BinaryNode
{
    Object item;
    BinaryNode *left;
    BinaryNode *right;
};

Это исходный код операции insert, которая точно следовала свойствам дерева двоичного поиска следующим образом. Указатель root - это глобальная переменная, которая содержит заголовок дерева двоичного поиска, а Newnode() - это функция, которая создает новый узел для вставки в дерево двоичного поиска.

BinaryNode *insert(BinaryNode *tree, Object datain)
{
    if (tree == NULL)
    {
        return Newnode(datain);
    }
    else
    {
        BinaryNode *temp = Newnode(datain);
        root = tree;
        while(tree != NULL)
        {
            if (datain.key < tree->item.key)
                tree = tree->left;
            else if (datain.key > tree->item.key)
                tree = tree->right;
            else
                  break; //Break to insert into the proper place
        }
        tree = temp;
        return root;
    }
}

Вот мой источник код для функции printTree(), который, я уверяю, не ошибся здесь. Тем не менее, я все еще предоставляю его здесь, чтобы прояснить мой вопрос.

oid printTree(BinaryNode *tree)
{
    if (tree == NULL)
        return;
    printTree(root->left);
    printf("(%d - %s)-> ", tree->item.key, tree->item.name);
    printTree(root->right);
}

Моя проблема: Вывод моей программы проверки состоит в том, что она распечатывает только первый узел дерева. Когда я отлаживаю свой исходный код, я обнаружил, что кроме первой вставки, он не включал вновь созданный узел. Тем не менее, я понятия не имею, как это исправить, потому что я думаю, что моя программа все еще логически алгоритмическая c.

Answer 1

За исключением случаев, когда вы вставляете первый элемент, вы не сохраняете ссылку на новый узел в дереве. Ваши локальные переменные temp и tree go выходят из области видимости при возврате. Вы должны сохранить ссылку на новый узел в существующей структуре вашего дерева, либо как root, либо как одну из löeft или right ссылок родительского узла нового узла.

One способ сделать это будет:

BinaryNode *insert(BinaryNode *root, Object datain)
{
    BinaryNode *prev = NULL;
    BinaryNode *curr = root;
    int whence = 0;

    while (curr) {
        if (datain.key == curr->item.key) return root;

        if (datain.key < curr->item.key) {
            curr = curr->left;
            whence = 0;
        } else {
            curr = curr->right;
            whence = 1;
        }
    }

    BinaryNode *temp = Newnode(datain);

    if (prev == NULL) {
        root = temp;
    } else if (whence == 0) {
        prev->left = temp;
    } else {
        prev->right = temp;
    }

    return root;
}

Указатель узла prev хранит родительский элемент текущего узла. Если оно пустое, дерево изначально пустое, и вы должны вставить его в root. Флаг whence сообщает вам, попали ли вы в текущий узел через ветку left или right, так что вы знаете, где обновлять.

(Также обратите внимание, что распределение происходит только после того, как у нас есть установлено, что узел должен быть вставлен. В противном случае ранний возврат приведет к утечке вновь выделенного узла.)

Это решение вводит две дополнительные переменные. Вы можете уменьшить это, используя указатель на указатель узла: сначала этот указатель p указывает на указатель головы, при спуске по дереву он указывает на то, откуда вы пришли, то есть left или right член родительского узла:

BinaryNode *insert(BinaryNode *root, Object datain)
{
    BinaryNode **p = &root;

    while (*p) {
        if (datain.key == (*p)->item.key) return root;

        if (datain.key < (*p)->item.key) {
            p = &(*p)->left;
        } else {
            p = &(*p)->right;
        }
    }

    *p = NewNode(datain);

    return root;
}

Вы все равно должны перенастроить узел. Этот код короче, потому что он не должен иметь дело со специальным случаем вставки первого узла и не должен явно распределять guish между листовой и правой ветвями при вставке нового узла.

Если вы хотите изменить сигнатуру функции, есть одно улучшение: передайте указатель на указатель головы вместо возврата. Таким образом, указатель головы в вызывающей функции будет обновляться с помощью proot:

void insert(BinaryNode **proot, Object datain)
{            
    while (*proot) {
        if (datain.key == (*proot)->item.key) return;

        if (datain.key < (*proot)->item.key) {
            proot = &(*proot)->left;
        } else {
            proot = &(*proot)->right;
        }
    }

    *proot = NewNode(datain);
}

Вы вызываете эту функцию следующим образом:

BinaryNode *root = NULL;

insert(&root, mydata);

Избыточность root = insert(root, data) равна ушел, и вы не можете случайно забыть обновить указатель root, не сохраняя возвращаемое значение.