Escreva um algoritmo para calcular a altura de uma árvore binária com nós folha formando uma lista duplamente ligada circular onde os ponteiros esquerdo e direito do nó folha atuarão como um ponteiro anterior e seguinte da lista duplamente ligada circular, respectivamente.
Por exemplo, considere a seguinte árvore binária. Os nós folha são 7, 5 e 6, conectados usando os ponteiros esquerdo e direito e formam uma lista circular duplamente ligada.
Sabemos que o altura de uma árvore binária é o número total de nós presentes no caminho mais longo da raiz até um nó folha. A ideia é atravessar a árvore em um moda pós-venda e calcule a altura da subárvore esquerda e direita. A altura de uma subárvore enraizada em qualquer nó será um a mais que a altura máxima de sua subárvore esquerda e direita. Aplique recursivamentemente esta propriedade a todos os nós da árvore de forma baixo para cima (modo pós-ordem) e retorne a altura máxima da subárvore enraizada naquele nó.
Para árvores binárias típicas, os filhos esquerdo e direito de um nó folha são ponteiros nulos. Mas aqui, o filho esquerdo e direito dos nós folha agem como o ponteiro anterior e seguinte da lista circular duplamente vinculada. Para que um nodo seja um nodo folha, verifique se a esquerda direita e a esquerda direita estão apontando para o próprio nodo.
Essa abordagem é demonstrada abaixo em C, Java e Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <stdio.h> #include <stdlib.h> // Função de utilidade para encontrar o máximo de dois inteiros int max(int x, int y) { return (x > y) ? x : y; } // Estrutura de dados para armazenar um nó de árvore binária struct Node { int data; struct Node *left, *right; }; // Função de utilidade para alocar memória para um nó de árvore binária struct Node* allocateNode(int data) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; node->left = node->right = NULL; return node; } // Função recursivo para calcular a altura de uma árvore binária com // nós folha formando uma lista circular duplamente encadeada int height(struct Node* node) { // caso base: se o nó for NULL if (node == NULL) { return 0; } // o nó é uma folha se a esquerda for direita e a direita for esquerda // estão apontando para o próprio nó if ((node->left && node->left->right == node) && (node->right && node->right->left == node)) { return 1; } // recorre para a subárvore esquerda e direita e considera a profundidade máxima return 1 + max(height(node->left), height(node->right)); } int main(void) { struct Node* root = NULL; // constrói a árvore root = allocateNode(1); root->left = allocateNode(2); root->right = allocateNode(3); root->left->left = allocateNode(4); root->left->right = allocateNode(5); // Nó da folha root->right->right = allocateNode(6); // Nó da folha root->left->left->left = allocateNode(7); // Nó da folha // constrói uma lista circular duplamente encadeada a partir de folhas struct Node* first = root->left->left->left; struct Node* second = root->left->right; struct Node* third = root->right->right; // define ponteiros anteriores e próximos da lista encadeada // (ponteiro esquerdo e direito de um nó de árvore binária, respectivamente) first->left = third; first->right = second; second->left = first; second->right = third; third->left = second; third->right = first; printf("The height of the binary tree is %d", height(root)); return 0; } |
Resultado:
The height of the binary tree is 4
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
// Uma classe para armazenar um nó de árvore binária class Node { int key; Node left = null, right = null; Node(int key) { this.key = key; } } class Main { // Função recursivo para calcular a altura de uma árvore binária com // nós folha formando uma lista circular duplamente encadeada public static int height(Node node) { // caso base: se o nó for nulo if (node == null) { return 0; } // o nó é uma folha se a esquerda for direita e a direita for esquerda // estão apontando para o próprio nó if ((node.left != null && node.left.right == node) && (node.right != null && node.right.left == node)) { return 1; } // recorre para a subárvore esquerda e direita e considera a profundidade máxima return 1 + Math.max(height(node.left), height(node.right)); } public static void main(String[] args) { // constrói a árvore Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); // Nó da folha root.right.right = new Node(6); // Nó da folha root.left.left.left = new Node(7); // Nó da folha // constrói uma lista circular duplamente encadeada a partir de folhas Node first = root.left.left.left; Node second = root.left.right; Node third = root.right.right; // define ponteiros anteriores e próximos da lista encadeada // (filho esquerdo e direito de um nó de árvore binária, respectivamente) first.left = third; first.right = second; second.left = first; second.right = third; third.left = second; third.right = first; System.out.println("The height of the binary tree is " + height(root)); } } |
Resultado:
The height of the binary tree is 4
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
# Uma classe para armazenar um nó de árvore binário class Node: def __init__(self, key=None, left=None, right=None): self.key = key self.left = left self.right = right # Função recursivo para calcular a altura de uma árvore binária com # Nós folha # formando uma lista circular duplamente ligada def height(node): # Caso base: se o nó for Nenhum if node is None: return 0 # O nó # é uma folha se a esquerda for direita e a direita for esquerda # estão apontando para o próprio nó if ((node.left and node.left.right == node) and (node.right and node.right.left == node)): return 1 # se repete para a subárvore esquerda e direita e considera a profundidade máxima return 1 + max(height(node.left), height(node.right)) if __name__ == '__main__': # constrói a árvore root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) # nó folha root.right.right = Node(6) # nó folha root.left.left.left = Node(7) # nó folha # constrói uma lista circular duplamente ligada a partir de folhas first = root.left.left.left second = root.left.right third = root.right.right # define ponteiros anteriores e próximos da lista vinculada # (filho esquerdo e direito de um nó de árvore binária, respectivamente) first.left = third first.right = second second.left = first second.right = third third.left = second third.right = first print('The height of the binary tree is', height(root)) |
Resultado:
The height of the binary tree is 4
A complexidade de tempo da solução acima é O(n), Onde n é o número total de nós na árvore binária. O espaço auxiliar requerido pelo programa é O(h) para a ligue para Stack, onde h é a altura da árvore.
Autor: Aditya Goel