Sumário da árvore de tipo de dados

Question

Estou fazendo uma unidade chamada estruturas de dados e algoritmos. Nós apenas começamos e meu professor acaba de nos ensinou o básico de árvores que algébricas Semântica é eo que Axiomas são etc. Até agora, eu só utilizados na forma de matrizes. Não utilizar a assinatura para árvore de pré-ordenada como a árvore (valor, árvore, árvore) onde o valor é o valor no nó, o nó esquerdo é a primeira árvore e nó direito é a segunda árvore.

Agora que eu estou definindo minha árvore como qualquer árvore (valor, árvore, árvore) ou Nil, eu não consigo descobrir como fazer para definir a álgebra para addNode (valor, árvore).

Ele só fica mais e mais complicado com cada nível, mais, eu possivelmente não pode pensar de qualquer maneira para fazer a varredura através de um nível que uma vez, tentando desde como uma hora agora. A álgebra apenas ramifica em mais e mais se-elses como nós vamos para baixo da árvore. Eu estou fazendo a coisa certa? você pode me apontar na direção certa? Ou árvores não pode ser implementada como uma árvore (valor, árvore, árvore)?

É uma parte do meu tutorial (não vale qualquer marca, nas questões adicionais), mas eu não estou procurando uma resposta instantânea, eu gosto do assunto, e gostaria de aprender mais.

Edit 1: Eu verifiquei Wikipédia, e eu não quero usar o livro-texto para a resposta clara, estou apenas procurando uma dica para a direção certa, se a minha abordagem é certo ou é completamente impossível definir uma árvore como árvore (valor, árvore, árvore). Eu sei que você pode representar um TAD árvore em forma de uma lista. Mas eu queria realmente pensar nisso. Espero que isso faz sentido. Thanks a lot guys!

Edit 2: Uhmm, é difícil de explicar através da internet. Vamos dizer que eu estou definindo uma nova estrutura de dados chamada "árvore". Posso defini-lo de qualquer maneira que eu quero, e deve comportar-se como uma árvore binária equilibrada (embora, valores de pais e filhos não importa) Então eu defini-la como a árvore: a árvore (valor, árvore, árvore) ou nula Não é a programação de código, é apenas como eu defini-lo. Árvore é um valor + 2 outras árvores ou árvore é nula. Agora addNode (valor, árvore) adiciona um nó em árvore enquanto ainda mantê-lo equilibrado. Não é a programação de código, é semântica apenas algébricas. Eu não sei se eu posso explicar isso corretamente. Mas eu tenho a uma solução que eu posso conseguir usando filas ou pilhas, mas isso é outra ADT eu vou ter que definir, o que não é válido.

Editar 3: Parece que eu tinha assumido muitas coisas que tornaram o problema mais difícil do que realmente deveria ser. Primeiro de tudo, desde a pequena explicação que dei, a resposta de Gamecat foi perfeito. Mas eu concordo com os comentários, é perfeitamente válida para incluir outros ADTs. Na verdade, quando nós construímos qualquer coisa que usa um Int, estamos usando um ADT para essa estrutura. Eu pensei que cada ADT teve que ser único. De qualquer forma, muito obrigado homens por suas respostas!

Answer 1

Se você quiser adicionar um nó a uma árvore, você pode usar uma função recursiva.

Eu assumo a árvore está ordenada. Portanto, você deve obter algo como isto:

AddNode(value, tree)

if tree is empty, create a new tree with value as node and no subtrees.
if value lesser than the treenode, call AddNode on the left branch.
else call AddNode on the right branch. (if duplicates are allowed).

Certifique-se de atualizar as subárvores se forem alteradas!

Você pode converter isso em uma função não recursiva por:

if tree is empty, return a new tree with value as node and no subtrees.
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees.
if value is lesser that treenode, and there is a left subtree, try again with the left subtree.
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees.
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree.

Se as necessidades de árvore para ser equilibrado. Você precisa armazenar obter um peso de equilíbrio (que pode ser -1, 0 ou 1). Se você precisar adicionar um nó em um site "pesado", você precisa reorganizar isso. Por exemplo, se o lado esquerdo tem um nó mais do que o lado direito e você precisa adicionar mais um nó para a esquerda. Você precisa obter o nó com o maior valor da subárvore esquerda e promover esse ao topo atual. O topo anterior é adicionado à subárvore direita. Certifique-se de manter as sub-árvores equilibradas também.

Exemplo: adicionar os nós 0,1,2,3,4

Add(0)           0

Add(1)           0
                  \
                   1

Add(2)           0 (2)  =>      1 (2) =>  1
                  \            /         / \
                   1          0         0   2

Add(3)           1
                / \
               0   2
                    \ 
                     3

Add(4)           1 (4)     => 2 (4)  =>      2
                / \          / \            / \
               0   2        1   3          1   3
                    \      /              /     \
                     3    0              0       4

Answer 2

Esta é uma pergunta difícil, já que é tão vaga. Eu suponho que você tem um livro de texto ou algo semelhante como parte de seu material do curso. Mesmo assim, ele se sente como se muitas das coisas que você está tendo problemas com são explicados por um recurso básico, como a entrada Wikipedia em árvores binárias.

Esta página descreve como fazer várias travessias de árvores, e como as árvores podem ser representados.