Faz sentido implementar iteradores para contêineres que não têm um fim óbvio - por exemplo, árvores?

Question

Estou escrevendo modelo de árvore de pesquisa binária por dois motivos - aprendendo C ++ e aprendendo algoritmos e estruturas de dados mais comuns.
Então, aqui está a pergunta - desde que eu queira implementar iteradores, parece -me que não há uma definição estrita para onde termina a árvore. Quais são suas sugestões? Como eu faço isso?

Answer 1

Para as árvores, existem padrões para atravessar a árvore, ou seja, enumerando os nós: travessia de pré -encomenda, travessia de encomenda e travessia postal. Em vez de descrever tudo isso aqui, vou redirecioná -lo para http://en.wikipedia.org/wiki/tree_traversal. Os conceitos são aplicados principalmente a árvores binárias, mas você pode estender a idéia para árvores arbitrárias adicionando mais casos: efetivamente, manuseie um nó e depois repousando, repouse e depois manuseie um nó, manuseie todas as crianças e depois volte a cada ... etc. Não há categorização canônica dessa abordagem que eu conheço.

Answer 2

Você precisa manter algo claro ao escrever um iterador - um iterador para uma estrutura de dados fornece acesso a uma coleção como uma sequência linear de itens. Certas coleções, como matrizes, listas e filas, são naturalmente compatíveis com serem tratadas como uma sequência linear. Outros tipos de coleções - árvores, dicionários, gráficos - não têm necessariamente uma interpretação simples como uma lista linear. De fato, múltiplas interpretações são geralmente válidas.

O que você realmente deve fazer ao escrever um iterador para uma coleção como uma árvore é abordar as seguintes preocupações:

1. Onde começa a iteração da coleção (raiz? Folhas?)
2. Como a iteração progride para o próximo elemento (infix? Postfix? Sufixo? Largura?)
3. Quando a iteração termina (folhas? Raiz? Nó final?)

O que você escolher, você deve ficar muito claro em como nomear (e documentar) seu iterador para tornar óbvio como ele visitará e emitirá nós.

Pode ser necessário escrever múltiplos iteradores para os diferentes tipos de travessias que você pretende apoiar. Existem alguns bons artigos aqui que dicuss Modelos de Traversal de Árvores.

Answer 3

Se por 'rigoroso', você quer dizer: uma única definição abrangente, você está certo, não há uma.

Mas 'fim' para árvores é muito bem definido, embora dependente do método de travessia que você está escolhendo.

• Se você fizer uma travessia em ordem (ou simétrica), o elemento mais à direita seria end.
• em pré -encomenda (ou profundidade primeiro), o elemento mais à direita seria end, etc.
• Na pós -ordem, o elemento raiz seria end, etc.

Mais comum travessia de árvores métodos.

Answer 4

Sua definição de iterador está um pouco errada. Iteradores não vão de começar para Finalizar, nem frente para de volta. Em vez disso, eles vão através Todos os membros dessa estrutura.

Se você pedir iteração sobre uma estrutura ordenada, ou seja, uma matriz, lista vinculada etc., você (geralmente) fará com que seus membros retornem em ordem.

Para itens não ordenados, por exemplo, um conjunto, você os obtém em que qualquer ordem que o Set-Arterator deseja dar-lhes, mas você os receberá todos e um a um tempo, assim como você fará com uma matriz -iterator.

Quanto às árvores, outras pessoas já mencionaram: elas têm uma noções bem definidas de ordem total, você só precisa escolher uma :)

Answer 5

Depende do que você deseja fazer com a árvore-talvez seja bom ter, por exemplo, iteradores de pesquisa ou primeira pesquisa na primeira pesquisa (ou ambos).

Se você tem alguma maneira específica de vasculhar a árvore, então, com efeito, você tem um começo e um fim. Não é tão óbvio quanto as relações lineares em listas e conjuntos, mas está lá se você deseja impor algum pedido a ela.

Answer 6

Faz sentido especialmente Em casos como esse, porque oferece aos usuários de sua classe uma maneira de acompanhar facilmente todos os elementos de maneiras diferentes, conforme a situação exige. Sem eles, os usuários precisam escrever maneiras complicadas e geralmente recursivas. Comparado aos vetores por exemplo, onde os iteradores estão mais digitando do que usar para (i = 0; i

Answer 7

Eu acho que no iterador de uma maneira mais abstrata. Não vejo no padrão do iterador nada que realmente diga que há um começo ou um fim! Então, por que ser restringido a essa visão. Podemos imaginar o Iterator que apenas se preocupa com o próximo elemento, é tudo. Quero dizer, eu enfrentei (especialmente em situações de processamento em massa) em que desde o início não sabemos a extensão da coleção, não sabemos se ela terá um fim algum dia, ou não temos toda a sua Elementos carregados na memória e não nos importamos. Nós apenas nos preocupamos em obter o próximo elemento. Em uma dessas implementações, o próximo nó é criado logo após o próximo método do elemento ser chamado. Podemos abrir nossas mentes e pensar em coleções infinitas (no final de uma coleção é um tipo de conjunto matemático), como as coleções de todos os números, a coleção de todos os números aleatórios. Você não precisa realmente ter todos os elementos na memória (isso é óbvio para coleções infinitas). É claro que esses não são exemplos práticos, mas minha mensagem é que um usuário de um iterador não precisa confiar na estrutura ou extensão real de uma coleção. Apenas me dê o próximo (se você tiver).