Binärer Baum

In diesem Tutorial lernen Sie den Binärbaum und seine verschiedenen Typen kennen. Außerdem finden Sie Arbeitsbeispiele für Binärbäume in C, C ++, Java und Python.

Ein Binärbaum ist eine Baumdatenstruktur, in der jeder übergeordnete Knoten höchstens zwei untergeordnete Knoten haben kann. Beispielsweise,

Binärer Baum

Arten von Binärbäumen

Voller Binärbaum

Ein vollständiger Binärbaum ist ein spezieller Typ eines Binärbaums, in dem jeder übergeordnete Knoten / interne Knoten entweder zwei oder keine untergeordneten Knoten hat.

Voller Binärbaum

Um mehr zu erfahren, besuchen Sie bitte den vollständigen Binärbaum.

Perfekter binärer Baum

Ein perfekter Binärbaum ist eine Art Binärbaum, in dem jeder interne Knoten genau zwei untergeordnete Knoten hat und alle Blattknoten auf derselben Ebene liegen.

Perfekter binärer Baum

Um mehr zu erfahren, besuchen Sie bitte den perfekten Binärbaum.

Kompletter Binärbaum

Ein vollständiger Binärbaum ist wie ein vollständiger Binärbaum, jedoch mit zwei Hauptunterschieden

  1. Jedes Level muss vollständig ausgefüllt sein
  2. Alle Blattelemente müssen sich nach links neigen.
  3. Das letzte Blattelement hat möglicherweise kein richtiges Geschwister, dh ein vollständiger Binärbaum muss kein vollständiger Binärbaum sein.
Kompletter Binärbaum

Um mehr zu erfahren, besuchen Sie bitte den vollständigen Binärbaum.

Entarteter oder pathologischer Baum

Ein entarteter oder pathologischer Baum ist der Baum, der links oder rechts ein einzelnes Kind hat.

Entarteter Binärbaum

Schräger Binärbaum

Ein verzerrter Binärbaum ist ein pathologischer / entarteter Baum, in dem der Baum entweder von den linken oder den rechten Knoten dominiert wird. Somit gibt es zwei Arten von verzerrten Binärbäumen: linksverzerrten Binärbaum und rechtsverzerrten Binärbaum .

Schräger Binärbaum

Ausgeglichener Binärbaum

Es ist eine Art Binärbaum, bei dem die Differenz zwischen dem linken und dem rechten Teilbaum für jeden Knoten entweder 0 oder 1 beträgt.

Ausgeglichener Binärbaum

Um mehr zu erfahren, besuchen Sie bitte den ausgeglichenen Binärbaum.

Binäre Baumdarstellung

Ein Knoten eines Binärbaums wird durch eine Struktur dargestellt, die einen Datenteil und zwei Zeiger auf andere Strukturen desselben Typs enthält.

 struct node ( int data; struct node *left; struct node *right; );
Binäre Baumdarstellung

Beispiele für Python, Java und 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); )

Binärbaumanwendungen

  • Für einen einfachen und schnellen Zugriff auf Daten
  • In Router-Algorithmen
  • So implementieren Sie eine Heap-Datenstruktur
  • Syntaxbaum

Interessante Beiträge...