Бинарные деревья в C

Question

Я пытаюсь вставить узлы в дерево по порядку. Моя функция работает нормально ... когда есть только три узла.

У меня есть этот код:

typedef struct _Tnode Tnode;
struct _Tnode {
    char* data;
    Tnode* left;
    Tnode* right;
};

Наряду с этим:

Tnode* add_tnode(Tnode* current_node, char* value) {
Tnode* ret_value; 

if(current_node == NULL) {
    current_node = (Tnode*) malloc(sizeof(Tnode));

    if(current_node != NULL) {
      (current_node)->data = value;
      (current_node)->left = NULL;
      (current_node)->right = NULL;
      ret_value = current_node; }
    else 
        printf("no memory");    
}
else {
    if(strcmp(current_node->data,value)) {  //left for less than 

        ret_value = add_tnode((current_node->left), value);
        current_node -> left = (Tnode*) malloc(sizeof(Tnode));
        (current_node -> left) -> data = value;
    }

    else if(strcmp(current_node->data,value) > 0) {

        ret_value = add_tnode((current_node -> right), value);
        current_node -> right = (Tnode*) malloc(sizeof(Tnode));
        (current_node -> right) -> data = value;
    }

    else {
        printf("duplicate\n");
        ret_value = current_node;
    }
}

return ret_value;

}

Я знаю, что здесь не так, я просто не знаю, как это исправить. Это просто перезаписывает два узла, прикрепленных к корневому узлу. т.е.

         |root_node|
        /           \
|node_2|             |node_3|

Я не могу добавить узел четыре. Он просто перезаписывает узел 2 или 3 в зависимости от ввода. После отладки и небольшого исследования я не совсем уверен, куда идти дальше ...

Если кто-нибудь может помочь, я буду очень признателен.

Answer 1

Вы должны оставить неправильный выбор только в том случае, когда вставка достигает листового узла (т. Е. NULL). В других случаях все, что вам нужно сделать, это перейти на следующий уровень в зависимости от вашего сравнения. В вашем случае вы переходите на следующий уровень, а затем убиваете его новым malloc. Из-за этого вы никогда не пройдете первый уровень.

например.

if (current_node == NULL) // Do initialization stuff and return current_node

if (strcmp(current_node->data, value) < 0) {
    current_node->left = add_tnode((current_node->left), value);
} else if (strcmp(current_node->data, value) > 0) {
    current_node->right = add_tnode((current_node->right), value);
}

return current_node;

Answer 2

struct _Tnode {
        char* data;
        struct _Tnode * left, * right;
    };
    typedef struct _Tnode Tnode;

void addNode(Tnode ** tree, Tnode * node){

    if(!(*tree)){
        *tree = node;
        return;
    }

    if(node->data < (*tree)->val){
       insert(&(*tree)->left, node);
    }else if(node->data>(*tree)->data){
       insert(&(*tree)->right, node);
    }

}

Answer 3

Казалось бы, это просто школьный проект.

С чего начать.

1) Вы бьете влево / вправо по всему дереву. Я не уверен, почему вы ожидаете, что они будут сохранены, так как: а) Вы всегда пишете в эти узлы. б) Единственный раз, когда вы возвращаете существующий узел, находится на совпадении strcmp.

2) Вам действительно нужно проверить strcmp <0 при первом сравнении. </p>

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

4) Рекурсивно ... Возвращать NULL во всех случаях, кроме случаев, когда вы создаете узел (то есть: первая часть, в которой у вас есть текущий == NULL).

5) Влево / вправо сохраните возвращаемое значение во временном локальном узле *. Только если возвращаемое значение не равно NULL, вы должны назначать влево / вправо.

Даже мне это не кажется правильным, но если бы я начал с нуля, это бы совсем не выглядело так. :) Мы даже не попадем в утечки / сбои памяти, с которыми вы, вероятно, столкнетесь, просто поместив значения 'char *' вокруг всех willy nilly.

Answer 4

для начинающих - первый strcmp

if (strcmp (current_node-> data, value))

, вероятно, не правильно - это верно как для меньших, так и для больших, а затем для второго, если не имеет смысла

Answer 5

Вам не нужно знать родителя узла. только значение в текущем узле.

псевдокод:

add_treenode(root, value)

{

 //check if we are at a leaf  
 if root == null
     allocate space for new node.
     set children to null
     save root->value = value
     return root // if you need to return something, return the node you inserted.
 //if not, this node has a value
 if root->value < value  //use strcmp since value is a string
       add_tnode(root->left, value)
 else
       add_tnode(root->right, value)
 return NULL

}

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

Answer 6

Если вы не реализуете это для своего собственного назидания, я бы просто использовал libavl

Answer 7

Как только вы узнали, что current_node-> data не является нулевым, и сравнили его со значением, вы должны сначала проверить, используется ли соответствующий указатель current_node-> left (или -> right) (! = NULL) .

Если он нулевой, вы продолжаете, как вы делаете. Это тот случай, когда он работает нормально.

Если нет, вы должны повторно протестировать все это на соответствующем узле, снова вызывая вашу функцию на соответствующем узле. Вот какой-то псевдокод:

Оберните код:

void Add_node(Tnode* current_node) {
...
else {
        if(strcmp(current_node->data,value) < 0) {  //left for less than 
           if(current_node->left != NULL) {
                Add_node(current_node->left);
           } else {
                ret_value = add_tnode((current_node->left), value);
                current_node -> left = (Tnode*) malloc(sizeof(Tnode));
                (current_node -> left) -> data = value;
        } else if(strcmp(current_node->data,value) > 0) {
                Add_node(current_node->right);
           } else {
           ...
}

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

Answer 8

Проблема в том, что после выполнения рекурсивного вызова функции add_tnode в левой ветви, скажем, вы стираете эту же ветку с помощью вашего malloc. Malloc должен произойти только тогда, когда вы вернулись к точке, где вы будете добавлять узел, а не когда вы делаете рекурсивный вызов.

По сути, в конкретном вызове функции вы должны либо сделать рекурсивный вызов, либо malloc новый узел, а не оба.

Это также вызывает утечку памяти, вероятно.

Answer 9

Полагаю, вам нужно добавить указатель на родительский узел в структуру _Tnode.