Skip to content

Laboratório 10

Objetivo

Neste laboratório, você deve escrever um programa em linguagem assembly RISC-V que tenha uma função recursiva compatível com ABI, int recursive_tree_search(Node *root, int val). Seu código será vinculado a um código em C que chama a função recursive_tree_search e espera que o valor de retorno seja a profundidade do valor se o valor procurado estiver presente na árvore, 0 se não estiver.

img1

A imagem acima mostra um exemplo de uma árvore binária. Se o valor 361 estivesse sendo procurado, o valor de retorno da função seria 3, pois é a profundidade do valor na árvore.

Cada nó da árvore é uma estrutura que contém um valor em sua primeira posição, ponteiros para o filho esquerdo e filho direito nas segunda e terceira posições, respectivamente. No caso de um dos filhos não existir, o ponteiro será NULL.

Além da recursive_tree_search, você precisará implementar algumas funções utilitárias que serão necessárias para este lab:

  • void puts(const char * str);
Description Parameters Return Value
puts - C++ String terminando com '\0' Nenhum
  • char * gets ( char * str );
Description Parameters Return Value
gets - C++ Buffer a ser preenchido Em caso de sucesso uma string, em caso de erro NULL
  • int atoi (const char * str);
Description Parameters Return Value
atoi - C++ String terminando com '\0' Inteiro representado pela string
  • char * itoa ( int value, char * str, int base );
Description Parameters Return Value
itoa - C++ Valor a ser convertido, buffer a ser preenchido e base 10 Ponteiro para o buffer
  • void exit(int code);
Description Parameters Return Value
Chama a syscall exit para terminar o programa Código de retorno Nenhum
  • lib.h 
    typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

int recursive_tree_search(Node *root_node, int val);
void puts ( const char *str );
char *gets ( char *str );
int atoi (const char *str);
char *itoa ( int value, char *str, int base );

void exit(int code);

Entrada

Sua função receberá o endereço da raiz da árvore no registrador a0 e o valor sendo procurado no registrador a1

Saída

Sua função deve retornar no registrador a0 a profundidade do valor se o valor procurado estiver presente na árvore, 0 caso contrário

Exemplos

  • exemplo.c 
    #include "lib.h"

char buffer[100];

#define NULL 0

void _start(){
    int val;
    Node root_node, node_1, node_2, node_3, node_4, node_5, node_6, node_7;

    root_node.val = 12; root_node.left = &node_1; root_node.right = &node_2;
    node_1.val = 5; node_1.left = &node_3; node_1.right = &node_4;
    node_2.val = -78; node_2.left = NULL; node_2.right = &node_5;
    node_3.val = -43; node_3.left = NULL; node_3.right = NULL;
    node_4.val = 361; node_4.left = NULL; node_4.right = NULL;
    node_5.val = 562; node_5.left = &node_6; node_5.right = &node_7;
    node_6.val = 9; node_6.left = NULL; node_6.right = NULL;
    node_7.val = -798; node_7.left = NULL; node_7.right = NULL;

    val = atoi(gets(buffer));
    puts(itoa(recursive_tree_search(&root_node, val), buffer, 10));
    exit(0);
}
Input Output
12 1
Input Output
562 3
Input Output
-40 0

Dicas

  • A raiz da árvore tem profundidade 1.
  • Os campos da estrutura do nó da árvore binária são VAL, LEFT e RIGHT, nessa ordem. VAL é um valor int com sinal armazenado no nó, e LEFT e RIGHT são ponteiros para os filhos do nó. Se um nó não tiver um desses filhos, o respectivo ponteiro será NULL.
  • Para verificar se o valor recebido está no nó atual, deve-se fazer a comparação VAL = valor recebido.
  • Um ponteiro NULL é representado pelo valor 0.
  • Todos os nós terão valores diferentes.
  • A leitura dos nós a esquerda e a direita se dão da mesma forma que no lab anterior usando lw

Entrega

O código deve ser testado no seguinte link o report gerado deve ser submetido no Classroom com o nome de {SeuRA}_lab10.report

Warning

Esta é uma atividade que deve ser realizada programando-se em linguagem de montagem - A submissão de programas em linguagem de programação de alto nível, como C, ou de programas gerados por ferramentas de compilação, serão considerados como fraude