In questo tutorial imparerai a conoscere l'albero binario e i suoi diversi tipi. Inoltre, troverai esempi funzionanti di albero binario in C, C ++, Java e Python.
Un albero binario è una struttura dati ad albero in cui ogni nodo padre può avere al massimo due figli. Per esempio,
Albero binario
Tipi di albero binario
Albero binario completo
Un albero binario completo è un tipo speciale di albero binario in cui ogni nodo padre / nodo interno ha due o nessun figlio.
Albero binario completo
Per saperne di più, visita l'albero binario completo.
Albero binario perfetto
Un albero binario perfetto è un tipo di albero binario in cui ogni nodo interno ha esattamente due nodi figli e tutti i nodi foglia sono allo stesso livello.
Albero binario perfetto
Per saperne di più, visita l'albero binario perfetto.
Albero binario completo
Un albero binario completo è proprio come un albero binario completo, ma con due differenze principali
- Ogni livello deve essere completamente riempito
- Tutti gli elementi dell'anta devono essere inclinati verso sinistra.
- L'ultimo elemento foglia potrebbe non avere un fratello destro, cioè un albero binario completo non deve essere un albero binario completo.
Albero binario completo
Per saperne di più, visita l'albero binario completo.
Albero degenerato o patologico
Un albero degenerato o patologico è l'albero che ha un solo figlio a sinistra oa destra.
Albero binario degenerato
Albero binario inclinato
Un albero binario inclinato è un albero patologico / degenere in cui l'albero è dominato dai nodi di sinistra o dai nodi di destra. Pertanto, ci sono due tipi di albero binario inclinato: albero binario inclinato a sinistra e albero binario inclinato a destra .
Albero binario inclinato
Albero binario bilanciato
È un tipo di albero binario in cui la differenza tra la sottostruttura sinistra e destra per ogni nodo è 0 o 1.
Albero binario bilanciato
Per saperne di più, visita il sito binario bilanciato.
Rappresentazione dell'albero binario
Un nodo di un albero binario è rappresentato da una struttura contenente una parte dati e due puntatori ad altre strutture dello stesso tipo.
struct node ( int data; struct node *left; struct node *right; ); 
Rappresentazione dell'albero binario
Esempi di 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); )
Applicazioni ad albero binario
- Per un accesso facile e veloce ai dati
- Negli algoritmi del router
- Per implementare la struttura dei dati dell'heap
- Albero della sintassi
