Doubt with binary tree

Asked

Viewed 485 times

1

I have this question: Write a function that takes a tree and an id and returns an array of path ids from the root node to the node passed as parameter.

int[] caminho_arvore(Arvore a, int n);

Examples are: Tree to:

inserir a descrição da imagem aqui

caminho_arvore(a, 9) retorna  [1,4,2,12,13,9]
caminho_arvore(a,1) retorna [1]
caminho_arvore(a, 17) retorna []
caminho_arvore(a, 4) retorna [1,4]

The question is just one: How do I represent this image(tree) in an array or something like that. Although there are many elements in the construction of the question, they are only there for you to understand, but the answer is one, how to represent the image in C#.

c# array
  • 1

    You have here an implementation of a binary tree: https://msdn.microsoft.com/en-us/library/ms379572%28v=vs.80%29.aspx

  • 1

    A binary tree is represented in an array as follows: [father, left son, right son, ...]. More precisely, the father’s Dice is worth (i - 1) / 2, left son’s 2*i + 1 and that of law 2*i + 2.

  • Similar to what you need: http://www.introprogramming.info/tag/binary-search-trees/

  • @Alex, how I would represent the posted image, in an array as you are placing it. I still can’t implement.

  • pnet, managed to reach a solution, put there if possible ..

  • Not yet. I’m reading a lot on the subject.,

Show 1 more comment

1 answer

1

A binary tree is represented in an array as follows: [father, left son, right son, ...]. More precisely, the father’s Dice is worth (i - 1) / 2, left son’s 2*i + 1 and that of law 2*i + 2.

Implementation Quick and Dirty, assuming an AB (not ABP) of numbers:

/* Retorna o indice do nodo na arvore, ou UINT_MAX se nao encontrado -- O(n) */ 
size_t                                                                          
index(int *tree, size_t nmemb, int node)                                        
{                                                                               
  size_t i = 0;                                                                 
  while (i < nmemb && tree[i] != node)                                          
    ++i;                                                                        
  return i < nmemb ? i : -1;                                                    
}                                                                               

int                                                                             
parent(int *tree, size_t nmemb, int node)                                       
{                                                                               
  size_t i = index(tree, nmemb, node);                                          
  if (i >= nmemb || !i)                                                         
    return INT_MAX;                                                             
  return tree[(i - 1) / 2];                                                     
}                                                                               

int                                                                             
left(int *tree, size_t nmemb, int node)                                         
{                                                                               
  size_t i = index(tree, nmemb, node);                                          
  size_t ans = 2*i + 1;                                                         
  if (i >= nmemb || ans >= nmemb)                                               
    return INT_MAX;                                                             
  return tree[ans];                                                             
}                                                                               

int                                                                             
right(int *tree, size_t nmemb, int node)                                        
{                                                                               
  size_t i = index(tree, nmemb, node);                                          
  size_t ans = 2*i + 2;                                                         
  if (i >= nmemb || ans >= nmemb)                                               
    return INT_MAX;                                                             
  return tree[ans];                                                             
}

E.g. http://pastebin.com/iGkk0UPq

debian@pc:~ ./a.out 2
Pai de 1: 2147483647 Esquerda: 2 Direita: 2147483647
Pai de 2: 1 Esquerda: 2147483647 Direita: 2147483647
debian@pc:~ ./a.out 3
Pai de 1: 2147483647 Esquerda: 2 Direita: 3
Pai de 2: 1 Esquerda: 2147483647 Direita: 2147483647
debian@pc:~ ./a.out 4
Pai de 1: 2147483647 Esquerda: 2 Direita: 3
Pai de 2: 1 Esquerda: 4 Direita: 2147483647
debian@pc:~ ./a.out 5
Pai de 1: 2147483647 Esquerda: 2 Direita: 3
Pai de 2: 1 Esquerda: 4 Direita: 5

  • Alex, who is size_t? I couldn’t understand this part of the code.

  • @pnet size_t is a positive integer type, and, as the name implies, is used for "size" values, indexes, etc. Functions like malloc take it as parameter. By definition, it is the type returned by sizeof, and therefore securely supports at least the maximum index that a Virutal memory array can receive. Both the definition of size_t how the representation of the tree in array can be easily found with a search in Google. Search use it more before asking.

Browser other questions tagged c# array

You are not signed in. Login or sign up in order to post.