Neste tutorial, você aprenderá sobre a árvore binária e seus diferentes tipos. Além disso, você encontrará exemplos funcionais de árvore binária em C, C ++, Java e Python.
Uma árvore binária é uma estrutura de dados em árvore na qual cada nó pai pode ter no máximo dois filhos. Por exemplo,
Árvore Binária
Tipos de árvore binária
Árvore Binária Completa
Uma árvore binária completa é um tipo especial de árvore binária em que cada nó pai / nó interno tem dois ou nenhum filho.
Árvore Binária Completa
Para saber mais, visite a árvore binária completa.
Árvore Binária Perfeita
Uma árvore binária perfeita é um tipo de árvore binária em que cada nó interno tem exatamente dois nós filhos e todos os nós folha estão no mesmo nível.
Árvore Binária Perfeita
Para saber mais, visite a árvore binária perfeita.
Árvore Binária Completa
Uma árvore binária completa é como uma árvore binária completa, mas com duas diferenças principais
- Cada nível deve ser completamente preenchido
- Todos os elementos da folha devem se inclinar para a esquerda.
- O último elemento folha pode não ter um irmão certo, ou seja, uma árvore binária completa não precisa ser uma árvore binária completa.
Árvore Binária Completa
Para saber mais, visite a árvore binária completa.
Árvore Degenerada ou Patológica
Uma árvore degenerada ou patológica é a árvore que tem um único filho à esquerda ou à direita.
Árvore Binária Degenerada
Árvore Binária Inclinada
Uma árvore binária inclinada é uma árvore patológica / degenerada na qual a árvore é dominada pelos nós esquerdos ou pelos nós direitos. Assim, existem dois tipos de árvore binária enviesada: árvore binária esquerda distorcida e árvore binária direito do enviesada .
Árvore Binária Inclinada
Árvore Binária Balanceada
É um tipo de árvore binária em que a diferença entre a subárvore esquerda e direita de cada nó é 0 ou 1.
Árvore Binária Balanceada
Para saber mais, visite a árvore binária balanceada.
Representação de árvore binária
Um nó de uma árvore binária é representado por uma estrutura que contém uma parte de dados e dois ponteiros para outras estruturas do mesmo tipo.
struct node ( int data; struct node *left; struct node *right; ); 
Representação de árvore binária
Exemplos de Python, Java e C / C ++
Python Java C C + # Binary Tree in Python class Node: def __init__(self, key): self.left = None self.right = None self.val = key # Traverse preorder def traversePreOrder(self): print(self.val, end=' ') if self.left: self.left.traversePreOrder() if self.right: self.right.traversePreOrder() # Traverse inorder def traverseInOrder(self): if self.left: self.left.traverseInOrder() print(self.val, end=' ') if self.right: self.right.traverseInOrder() # Traverse postorder def traversePostOrder(self): if self.left: self.left.traversePostOrder() if self.right: self.right.traversePostOrder() print(self.val, end=' ') root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) print("Pre order Traversal: ", end="") root.traversePreOrder() print("In order Traversal: ", end="") root.traverseInOrder() print("Post order Traversal: ", end="") root.traversePostOrder()
// Binary Tree in Java // Node creation class Node ( int key; Node left, right; public Node(int item) ( key = item; left = right = null; ) ) class BinaryTree ( Node root; BinaryTree(int key) ( root = new Node(key); ) BinaryTree() ( root = null; ) // Traverse Inorder public void traverseInOrder(Node node) ( if (node != null) ( traverseInOrder(node.left); System.out.print(" " + node.key); traverseInOrder(node.right); ) ) // Traverse Postorder public void traversePostOrder(Node node) ( if (node != null) ( traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.key); ) ) // Traverse Preorder public void traversePreOrder(Node node) ( if (node != null) ( System.out.print(" " + node.key); traversePreOrder(node.left); traversePreOrder(node.right); ) ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); System.out.print("Pre order Traversal: "); tree.traversePreOrder(tree.root); System.out.print("In order Traversal: "); tree.traverseInOrder(tree.root); System.out.print("Post order Traversal: "); tree.traversePostOrder(tree.root); ) )
// Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // Preorder traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // Postorder traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 2); insertRight(root, 3); insertLeft(root->left, 4); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
// Binary Tree in C++ #include #include using namespace std; struct node ( int data; struct node *left; struct node *right; ); // New node creation struct node *newNode(int data) ( struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); ) // Traverse Preorder void traversePreOrder(struct node *temp) ( if (temp != NULL) ( cout << " " left); traversePreOrder(temp->right); ) ) // Traverse Inorder void traverseInOrder(struct node *temp) ( if (temp != NULL) ( traverseInOrder(temp->left); cout << " " right); ) ) // Traverse Postorder void traversePostOrder(struct node *temp) ( if (temp != NULL) ( traversePostOrder(temp->left); traversePostOrder(temp->right); cout << " " left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); cout << "preorder traversal: "; traversePreOrder(root); cout << "Inorder traversal: "; traverseInOrder(root); cout << "Postorder traversal: "; traversePostOrder(root); )
Aplicativos de árvore binária
- Para acesso fácil e rápido aos dados
- Em algoritmos de roteador
- Para implementar a estrutura de dados heap
- Árvore de sintaxe
