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