Неупорядоченный обход дерева в двоичном дереве в C

В приведенном ниже коде я создаю двоичное дерево, используя функцию вставки, и пытаюсь отобразить вставленные элементы, используя функцию упорядочения, которая следует логике обхода по порядку. Когда я запускаю его, числа вставляются, но когда я пытаюсь function(вход 3), программа переходит к следующему вводу, ничего не отображая. Я предполагаю, что это может быть логическая ошибка. Пожалуйста, помогите мне ее очистить. Заранее спасибо...

#include<stdio.h>
#include<stdlib.h>

int i;
typedef struct ll
{
  int data;
  struct ll *left;
  struct ll *right;
} node;

node *root1=NULL; // the root node

void insert(node *root,int n)
{
  if(root==NULL) //for the first(root) node
  {
    root=(node *)malloc(sizeof(node));
    root->data=n;
    root->right=NULL;
    root->left=NULL;
  }
  else
  {
    if(n<(root->data))
    {
      root->left=(node *)malloc(sizeof(node));
      insert(root->left,n);
    }
    else if(n>(root->data))
    {
      root->right=(node *)malloc(sizeof(node));
      insert(root->right,n);
    }
    else
    {
      root->data=n;
    }
  }
}

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

main()
{
  int n,choice=1;
  while(choice!=0)
  {
    printf("Enter choice--- 1 for insert, 3 for inorder and 0 for exit\n");
    scanf("%d",&choice);
    switch(choice)
    {
      case 1:
        printf("Enter number to be inserted\n");
        scanf("%d",&n);
        insert(root1,n);
        break;
      case 3:
        inorder(root1);
        break;
      default:
        break;
    }
  }
}

c binary-tree inorder
person srk    schedule 31.10.2013    source источник
comment
Не переводите возвращаемое значение malloc() в C.   -  person unwind    schedule 31.10.2013

Ответы (3)


arrow_upward
1
arrow_downward

Ваш insert принимает указатель на node, который является локальным для области действия функции. После возврата insert корень, к которому он был вызван, остается неизменным. И получаешь утечку.

Если вы хотите, чтобы изменения, которые делает insert, были видны за его пределами, начните с изменения его подписи.

void insert(node **root,int n)

И называя это так:

void insert(&root1, n);

Таким образом, он изменит root1, а не его копию.

Как правило, если функции нужно что-то изменить, ей следует передать указатель на нее. Ваша функция должна изменить node*, поэтому ей следует передать node**.

ИЗМЕНИТЬ

Как указывал unwind, вы также можете вернуть корень как средство его обновления.

root1 = insert(root1, n);

Это, конечно, работает, только если вам нужно изменить один объект.

person StoryTeller - Unslander Monica    schedule 31.10.2013
comment
Также рассмотрите возможность возврата нового корня. - person unwind; 31.10.2013

arrow_upward
0
arrow_downward

Ваш код распределения отключен, root1 всегда останется NULL, так как результат malloc назначается только локальной переменной. Передайте root в качестве указателя на указатель.

Кроме того, вы безоговорочно используете malloc слева и справа, даже если там уже могут быть данные, вы должны немедленно вызвать вставку и заставить вызываемую вставку обрабатывать malloc точно так же, как для root. Опять же с указателем на указатель, конечно.

Ваще else root->data = n смысла нет, это уже н. И я полагаю, вы не хотите дубликатов в своем дереве? Если вы это сделаете, вам нужно изменить свой код.

person wich    schedule 31.10.2013

arrow_upward
0
arrow_downward

Передайте ссылку node * на insert(), чтобы при выделении нового узла он соответствующим образом обновлялся.

Кроме того, в вашей функции insert() не выделяйте при переходе в дерево ниже. Если вы выделяете, то ваш код пытается проверить значение на этом узле и продолжить снова, что неверно.

Обновленный код будет:

void insert(node **root_ptr,int n)
    {
    if(root==NULL) //for the first(root) node
    {
        root=(node *)malloc(sizeof(node));
        root->data=n;
        root->right=NULL;
        root->left=NULL;
        *root_ptr = root;
    }
    else
    {
        if(n<(root->data))
        {
        //root->left=(node *)malloc(sizeof(node));
        insert(&root->left,n);
        }
        else if(n>(root->data))
        {
        //root->right=(node *)malloc(sizeof(node));
        insert(&root->right,n);
        }
        else
        {
        root->data=n;
        }
    }
    }

Из main() назовите его как insert(&root1,n);

person Rohan    schedule 31.10.2013