C Рекурсивное программирование вставки двоичного дерева (не двоичного дерева поиска)

Это мой код здесь. Я хочу рекурсивно вставлять элементы в двоичное дерево. Это не бинарное дерево поиска (левый дочерний элемент не обязательно должен быть ‹ родителем или правый дочерний элемент не обязательно должен быть > родителем).

Это просто бинарное дерево, в котором для каждого узла может быть не более двух дочерних элементов. Когда я выполняю обход, он просто бесконечно печатает начальный узел в бесконечном цикле (5-> 5-> 5->....). Пожалуйста, помогите мне.

Я искал через переполнение стека, и ничего не основано на этом. Большинство из них представляют собой бинарные деревья поиска. Извините, если это плохой вопрос.

struct node {
    int info;
    struct node* left;
    struct node* right;
}*temp, *ptr, *prev;

struct node *root, *start=NULL;

void insert(struct node*);
void inorder(struct node*);

void insert(struct node* ptr)
{
    int ch;

    if(start==NULL)  // if start is null, new node is made as start node.
        start=ptr;
    else
    {
        temp=(struct node*)malloc(sizeof(struct node)); //new node created
        temp->left=NULL;
        temp->right=NULL;
        puts("Enter value");
        scanf("%d", &temp->info);
        ptr=temp;     //ptr is set as new node
    }

    printf("Does %d have a left node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        if(ptr==start)
            insert(start->left); //start->left will be the new 'ptr' in the next insertion scenario
        else
            insert(ptr->left);  //same principle as above
    }

    printf("Does %d have a right node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        if(start==ptr)
            insert(start->left);
        else
            insert(ptr->right);
    }

}

void inorder(struct node* ptr)
{
    while(ptr!=NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

void main(){
    int ch;
    do{
        puts("1. Insert 2.Traverse 3.Exit");
        scanf("%d",&ch);
        switch(ch){
            case 1:
                puts("Enter root node");
                root=(struct node *)malloc(sizeof(struct node));
                root->left=NULL;
                root->right=NULL;
                scanf("%d", &root->info);
                insert(root);
                break;
            case 2:
                inorder(start);
        }
    }while(ch!=3);
}

Заранее спасибо, ребята.


c binary-tree insertion
person akkhil    schedule 10.04.2015    source источник
comment
Ваша функция обхода выглядит нормально, но ваш код вставки повсюду. Я бы предложил две вещи: 1. остановиться на глобалах. Как правило, это плохая практика, особенно при работе со связанными списками. 2. Используйте функцию (или функции) для управления вашим деревом и добавления/вставки узлов.   -  person Eregrith    schedule 10.04.2015
comment
Если вы никогда раньше не пользовались отладчиком, это отличная возможность научиться. См. thegeekstuff.com/2010/03/debug-c- program-using-gdb, если в вашей системе есть gdb.   -  person ericzundel    schedule 10.04.2015
comment
@Eregrith Функция обхода не выглядит нормально — она зацикливается навсегда, если ptr != NULL.   -  person CiaPan    schedule 10.04.2015
comment
@CiaPan вау, извините, я думаю, мне нужно больше спать ›_‹. Не видел while   -  person Eregrith    schedule 12.04.2015

Ответы (3)


arrow_upward
0
arrow_downward

Попробуйте этот способ добавления узлов:

struct node *createTree()
{
    struct node *node;
    int resp;

    node=malloc(sizeof(struct node)); //new node created
    node->left=NULL;
    node->right=NULL;
    puts("Enter value");
    scanf("%d", &node->info);

    printf("Does %d have a left node? (1/0)\n", node->info);
    scanf("%d", &resp);
    if(resp==1)
        node->left = createTree();

    printf("Does %d have a right node? (1/0)\n", node->info);
    scanf("%d", &resp);
    if(resp==1)
        node->right = createTree();

    return node;
}

затем в main() выполните:

root = createTree();

Обратите внимание, что переменная resp имеет тип int, если вы сканируете ее в формате "%d". Для типа char следует использовать формат "%c".

person CiaPan    schedule 10.04.2015

arrow_upward
2
arrow_downward

ваш обход создает бесконечный цикл, вы должны изменить while на if

void inorder(struct node* ptr)
{
    if (ptr != NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

в insert(struct node* ptr), когда вы делаете ptr=temp;, ptr изменяется только внутри области действия функции, поэтому на самом деле вы никогда не назначаете левый и правый узлы для корня

person huxley    schedule 10.04.2015
comment
Спасибо за указание на ошибку функции обхода. Также о функции вставки, то, что вы сказали, имеет смысл. Что было бы подходящим решением? - person akkhil; 10.04.2015

arrow_upward
0
arrow_downward

Я нашел решение для этого. Извините, что потратил ваше время. Проблема с моим кодом была:

1) while вместо if в функции обхода 2) во-вторых, когда я передаю аргумент ptr, он не знает, куда связать этот ptr. Все, что я делал, это ptr=temp. Он должен ссылаться на левый/правый предыдущий узел, верно?

Объяснение @ Huxley относительно области действия функции было неверным. Он должен указывать на один и тот же объект — вот почему мы используем указатели, верно? Однако в моей голове прозвенел звонок. Итак, вот решение ниже:

void insert(struct node* ptr, int side)
{
    int ch;

    if(start==NULL)  // if start is null, new node is made as start node.
        start=ptr;
    else
    {
        temp=(struct node*)malloc(sizeof(struct node)); //new node created
        temp->left=NULL;
        temp->right=NULL;
        puts("Enter value");
        scanf("%d", &temp->info);
        ptr=temp;
        if(side==1)
            prev->left=ptr;
        else
            prev->right=ptr;
    }

    printf("Does %d have a left node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        insert(ptr->left, 1);
    }

    printf("Does %d have a right node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        insert(ptr->right, 2);
    }

}

void inorder(struct node* ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

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

Спасибо всем, кто помог.

Привет, Ахил

person akkhil    schedule 10.04.2015