Doubt with binary tree

Question

Doubt with binary tree

Navigation

#1 by (1 votes)

1

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

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

Examples: Tree to:

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 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 only one, how to represent the image in C #.

c# array

asked by anonymous 05.07.2015 / 21:27

1 answer

I do not know how to read the array encoded with PHP in json How to integrate one table from the database to another?

score 1 · Answer 1

A binary tree is represented in an array as follows: [parent, left child, right child, ...]. More precisely, the index of the father is (i - 1) / 2 , that of the left child 2*i + 1 and that of the 2*i + 2 right.

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. link

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