Двоичное дерево: алгоритм вставки узла

Question

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

class BinaryTree {
    class Node {
        char data;

        Node* leftChild;
        Node* rightChild;

        Node(char d, Node* lc, Node* rc):
            data(d), leftChild(lc), rightChild(rc) {}
    } *head;
    int treeSize;
public:
    BinaryTree(): head(0), treeSize(0) {}

    // totally wrong code
    void createNode(char dat) {
        if (head->data < dat)
            head->leftChild = new Node(dat, 0, 0);
        if (head->rightChild == 0)
            head->rightChild = new Node(dat, 0, 0);
        if (head == 0) {
            head = new Node(dat, head, head);
        }
    }
};

Ну, я подумал реализовать двоичное дерево, используя связанный список, но в этом случае проблема будет в том, что head Указатель будет указывать на один из последних добавленных узлов, а не на корень. Другая проблема, связанная с использованием связанного списка таким способом, может заключаться в том, чтобы найти пустого дочернего элемента узла, в который необходимо добавить новый узел.
Есть кто-то, кто мог бы помочь мне и, возможно, предложить лучший способ реализации бинарного дерева?

Примечание: я планировал сделать этот класс template, char только для того, чтобы попробовать это на лету.

Answer 1

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

void addNode( char data ) {
    // when root is uninitialized
    if ( NULL == head ) {
        head = new Node( data, NULL, NULL );
    } else {
        Node *currentNode = head;
        // search for the place to insert the new value
        while ( true ) {
            if ( currentNode->data < data ) {
                // if the current node already has left child
                // so we concern it further
                if ( NULL != currentNode->leftChild ) {
                    currentNode = currentNode->leftChild;
                    continue;
                // if the current node has no left child
                // so we create it with the new value
                } else {
                    currentNode->leftChild = new Node( data, NULL, NULL );
                    return;
                }
            } else {
                // similarly for the value that should be inserted into
                // right subtree
                if ( NULL != currentNode->rightChild ) {
                    currentNode = currentNode->rightChild;
                    continue;
                } else {
                    currentNode->rightChild = new Node( data, NULL, NULL );
                    return;
                }
            }
        }
    }
}

Answer 2

Я предполагаю, что это какое-то домашнее задание, поэтому я думаю, что важно подчеркнуть основные принципы и дать вам понять остальное. Поскольку это отправная точка для любого обхода дерева, Head никогда не должен меняться, если вы не удаляете корневой узел. Любой обход должен быть выполнен другим объектом Node, который может (и, вероятно, часто будет) выходить из области действия в конце каждого вызова функции без каких-либо побочных эффектов в программе.

Как уже указывалось, вам нужно рассмотреть случай, когда head = NULL в качестве первого условия, а затем обработать последующий обход head!= NULL. При вставке вы должны учитывать, как вы хотите, чтобы вставка происходила с правильной связью с другими элементами дерева. Может быть полезно помнить, что лист - это любой объект Node, в котором правый и левый члены данных имеют значение NULL.

Удачи в вашей программе.

Answer 3

Вот лишь несколько вещей, которые я заметил:

1. Ваша проверка на head!= Null должна идти первой, иначе ваш первый createNode() потерпит крах. Все остальные ветви должны быть в "else".

2. Ваш последний (или я должен сказать первым) новый узел (dat,head, head) должен быть новым Node(dat,0,0) для ясности кода и / или как часть Международной кампании по признанию программистов обслуживания.

3. Вы, вероятно, хотите увеличить TreeSize.

В противном случае вы на правильном пути. Продолжайте идти.