Insert element into a binary search tree

Question

Insert element into a binary search tree

Navigation

#1 by (2 votes)
#2 by (1 votes)

2

I'm having difficulty adding an element to a binary search tree. The function returns 1 if the element to be inserted is already in the tree and 0 otherwise. The function return works fine but when printing the tree the new element does not appear in the new tree . Here is my code:

int adiciona (Abin a, int x)
{

  int n;

  if (a == NULL)
  {
    Abin novi = (Abin)malloc (sizeof (struct sbin));
    novi->valor = x;
    novi->esq = NULL;
    novi->dir = NULL;
    n = 0;
  }
  else
  {
    if (x == a->valor)
    { n = 1; }
    if (x > a->valor)
    { n = adiciona (a->dir , x); }
    if (x < a->valor)
    { n = adiciona (a->esq , x); }

  }

   return n;
}

Is the error in my code? If so, what is the right way to solve this function?

c

asked by anonymous 06.07.2015 / 18:43

2 answers

How to make a responsive horizontal line? Search View without needing to click enter to appear the result

score 2 · Answer 1

At no point in this code do you add the new branches created to the upper branches of the tree. This is - you call the adiciona function recursively correctly, the adiciona function creates a new one-level tree and inserts the value, but does not insert this new tree at the parent levels.

Because in C it is complicated for a function to return more than one value (in this case its "n" and the new branch of the tree) - it is best to create the new branch when necessary without calling the add function with a " NULL "as root - (why does it have where to add the created branch).

So perhaps one of the simplest ways is to rearrange your function more or less like this

Abin cria(void)
{
  return (Abin)malloc (sizeof (struct sbin));
}

int adiciona (Abin a, int x)
{
  int n;

  if (x == a->valor)
    { n = 1; }
  if (x > a->valor)
    { 
      if (!a->dir)
      { 
        a->dir = cria();
        a -> dir -> valor = valor;   
        n = 0;
      }
      else
      { n = adiciona(a->dir, x); }
    }
  if (x < a->valor)
    { 
      if (!a->esq)
      { a -> esq = cria();
        a -> esq -> valor = valor;
        n = 0;
      }
      else
      { n = adiciona (a->esq , x); }
    }
  return n;
}

(Exceptionally I kept your indentation pattern - but it is not one of the preferred ways for languages with braces)

score 1 · Answer 2

1

You need to a point to your novi element. It does not print anything because you allocate a value in memory but do not add it to your tree.

06.07.2015 / 20:53