Algoritmo para testar se uma árvore binária é uma árvore de pesquisa e contar ramos completos
Eu preciso criar um algoritmo recursivo para ver se uma árvore binária é uma árvore de pesquisa binária e contar quantas ramificações completas existem (um nó pai com nós filhos esquerdo e direito) com uma variável de contagem global assumida. Esta é uma atribuição para minha classe de estruturas de dados.
Até agora eu tenho
Mas eu realmente não consigo entender isso. Eu sei que esse algoritmo não resolverá o problema porque a contagem será zero se a segunda se a instrução não for verdadeira.
Como o operador de comparação é <definido nos nós?
— 21712 Joe
Deseja calcular a contagem, mesmo que não seja uma árvore de pesquisa binária?
Seu algoritmo deve retornar algo como trueou false?
Talvez você deva primeiro definir duas funções separadas: uma para verificar se é uma BST e outra para contar as ramificações completas. Isso deve ser mais gerenciável.
@OghmaOsiris, imagino que ele tenha dito isso porque a pergunta é basicamente "Aqui está o meu código, como faço para funcionar?". Se o código não fosse da variedade pseudo (ish), seria definitivamente uma pergunta SO.
— sepp2k 22/03
Como outros já indicaram nos comentários, você realmente tem duas funções não relacionadas aqui: testar se a árvore é uma árvore de pesquisa e contar os ramos completos. A menos que a tarefa o exija especificamente, eu escreveria duas funções separadas.
Vamos ver a quantidade contando os ramos completos primeiro. Isso significa contar os nós que têm um filho esquerdo e um filho direito. Então você precisa incrementar o counter ( count = count + 1) quando ambos T.lefte T.rightnão são nulos (não T.left.datae T.right.data: os dados não importam para esta tarefa).
Além disso, você precisa explorar a subárvore esquerda, mesmo que a subárvore direita esteja vazia, e você deve explorar a subárvore direita, mesmo que a subárvore esquerda esteja vazia. Portanto, observe onde você faz as chamadas recursivas.
Para testar se a árvore é uma árvore de pesquisa, é necessário inspecionar os valores dos dados. Você já tem algo próximo à comparação certa; não muito certo. Escreva alguns exemplos de árvores com várias formas (não muito grandes, de 2 a 5 nós) e execute seu algoritmo nelas para ver o que acontece.
Você ainda precisa encontrar algum lugar para colocar o resultado da verificação de validade. Novamente, observe onde você faz as chamadas recursivas (se você fizer apenas essa parte, existem várias soluções, mas, nesse estágio, não se preocupe se você vir apenas uma).
Por fim, depois de conseguir escrever as duas funções separadamente e testá-las em alguns exemplos, junte-as com cuidado (se exigido pela tarefa).
obrigado, reli a pergunta e ela deveria ser métodos separados.
Em coisas como essa, geralmente é mais fácil pensar de trás para a frente, então primeiro considere o que você precisa. Na sua descrição, vamos listá-los:
Contagem de nós completos
OK, é uma lista bastante curta, deve ser gerenciável. Vamos começar com um método vazio e adicionarei uma descrição do que deveria estar acontecendo.
Agora validade. Como você verifica a validade? No bate-papo, você disse que uma árvore é válida "se ... todos os filhos esquerdos forem menores que os pais e os filhos direitos forem maiores que os pais". Tenho certeza que você pretendia permitir a igualdade também. Isso seria t.left.value <= t.value <= t.right.value.
Mas e se uma das crianças estiver desaparecida? Pelo que você disse, acredito que você sabe que o nó ainda é válido se estiver faltando um (ou ambos). Vamos adicionar isso, reestruturando um pouco:
OK, agora sabemos se este nó é válido. Como verificamos se a árvore inteira é válida? Como não está em um array, provavelmente não podemos / não queremos fazer um loop linear sobre ele. Sua tarefa fornece a resposta: recursão. Mas como acumulamos uma resposta usando recursão? Temos acesso a três informações, se esse nó é válido, e o resultado de chamadas perguntando se os nós esquerdo e direito são válidos. Obviamente, a árvore só é válida se todas as três forem verdadeiras.
Se você está prestando atenção, isso nos diz até o que nossa função precisa retornar.
Agora, como integramos a contagem? Você diz o que conta ("um nó pai com nós filhos esquerdo e direito"), e isso não deve ser difícil de traduzir em código real. Verifique se essa condição é satisfeita e aumente o contador adequadamente. Lembre-se de que isso deve estar em algum lugar onde será alcançado toda vez que for verdade.
E, é claro, deixei de fora alguns detalhes, como a condição de parada da recursão e verifica se há nulo.
Meus três comentários acima são três dicas para problemas com seu código.
A menos que você já tenha definido especificamente como um operador de comparação deve lidar com o tipo de dados do nó, provavelmente comparar dois nós diretamente não fará o que você deseja. O que você provavelmente quis dizer foi comparar os campos armazenados nos nós, por exemplonode1.value < node2.value
No momento, você só está adicionando à contagem se a terceira iffor verdadeira. Tem certeza de que é isso que você pretende fazer? A propósito, você pode querer checar se essa instrução if faz o que você deseja.
Suponho que você queira retornar true se a árvore for um BST válido e false caso contrário. O que significa que você sempre deve retornar verdadeiro ou falso em um caso base e também retornar os resultados de suas chamadas recursivas.
Em relação ao ponto um: este é pseudo-código, certo? Portanto, desde que a intenção seja transmitida ao leitor, não há razão para definir coisas assim.
— sepp2k # 03
@ sepp2k isso é verdade, e meu comentário provavelmente é um pouco exigente demais para pseudo-código. Acho que meu argumento é que precisamos entender o que significa comparar dois nós. O seu ponto é que já devemos entender isso implicitamente.