Árvore binária de busca de strings. Escreva um programa baseado no programa da Figura 12.19 que aceite uma lista de texto, separe a sentença em palavras, insira as palavras em uma árvore binária de busca e imprima as travessias in order, pré-ordem e pós-ordem da árvore.

[Dica: leia a linha de texto para um array. Use strtok para separar o texto em palavras. Quando uma palavra for encontrada, crie um novo nó para a árvore, atribua o ponteiro retornado por strtok ao membro string do novo nó e insira o nó na árvore.]

Passo 1

Criaremos uma estrutura de árvore binária e a usaremos para classificar os dados tokenizados e imprimir os percursos em ordem, pré-ordem e pós-ordem.

Cabeçalho do programa (a estrutura, bem como os protótipos de função, são baseados na Fig. 12.19):

#define MAX_WORD_LENGTH 46

struct treeNode

{

struct treeNode* leftPtr;

char* data;

struct treeNode* rightPtr;

};

typedef struct treeNode TreeNode;

typedef TreeNode* TreeNodePtr;

void insertNode(TreeNodePtr* treePtr, char* value);

void inOrder(TreeNodePtr treePtr);

void preOrder(TreeNodePtr treePtr);

void postOrder(TreeNodePtr treePtr);

Passo 2

Vamos começar com a função insertNode().

A função vai inserir o valor desreferenciado do ponteiro de valor em um nó de árvore correspondente comparando o valor com o valor do nó atual usando a função strcmp().

Comece verificando se o nó da árvore foi inicializado:

void insertNode(TreeNodePtr* treePtr, char* valor)

{

if (*treePtr == NULL)

{

*treePtr = malloc(sizeof(TreeNode));

...

}

...

}

Se a alocação foi bem-sucedida, aloque memória suficiente para o membro da estrutura de dados e copie e cole o valor da string de valor utilizando a função strcpy().

Em vez de atribuir os ponteiros, o que resultaria em todos os dados do nó da árvore com o mesmo ponteiro, usamos a função strcpy() para copiar por valor.

void insertNode(TreeNodePtr* treePtr, char* value)

{

if (*treePtr == NULL)

{

...

if (*treePtr != NULL)

{

(*treePtr)->data = malloc(MAX_WORD_LENGTH);

strcpy((*treePtr)->data, value);

(*treePtr)->leftPtr = NULL;

(*treePtr)->rightPtr = NULL;

}

else

{

printf("%s not inserted. No memory "

"available.\n", value);

}

}

...

}

Se o nó da árvore for inicializado, temos que determinar em qual nó inseriremos o novo nó.

Para tomar essa decisão, utilizaremos a função strcmp() que comparará os valores das duas strings da seguinte forma:

void insertNode(TreeNodePtr* treePtr, char* value)

{

...

else

{

if (strcmp(value, (*treePtr)->data)

insertNode(&((*treePtr)->leftPtr), value);

else if (strcmp(value, (*treePtr)->data) > 0)

insertNode(&((*treePtr)->rightPtr), value);

else

printf("dup");

}

}

O resto das funções são as mesmas da figura indicada, mas em vez de inteiros, estamos gerando strings:

void inOrder(TreeNodePtr treePtr)

{

if (treePtr != NULL)

{

inOrder(treePtr->leftPtr);

printf("%s ", treePtr->data);

inOrder(treePtr->rightPtr);

}

}

void preOrder(TreeNodePtr treePtr)

{

if (treePtr != NULL)

{

printf("%s ", treePtr->data);

preOrder(treePtr->leftPtr);

preOrder(treePtr->rightPtr);

}

}

void postOrder(TreeNodePtr treePtr)

{

if (treePtr != NULL)

{

postOrder(treePtr->leftPtr);

postOrder(treePtr->rightPtr);

printf("%s ", treePtr->data);

}

}

Passo 3

Na função main, primeiro receberemos a entrada da seguinte forma:

int main()

{

char* line = (char*)malloc(100);

gets(line);

...

}

Declare a raiz da árvore binária:

int main()

{

...

TreeNodePtr rootPtr = NULL;

...

}

Obtenha o primeiro token usando a função strtok() da seguinte forma:

int main()

{

...

char* token = strtok(line, " ");

...

}

Itere pelo restante dos tokens, inserindo os tokens (palavras) na árvore chamando a função insertNode():

int main()

{

...

while (token != NULL)

{

insertNode(&rootPtr, token);

token = strtok(NULL, " ");

}

...

}

Resposta

Ver o desenvolvimento.