In deze tutorial leer je over de binaire boom en zijn verschillende typen. Ook vindt u werkende voorbeelden van binaire boom in C, C ++, Java en Python.
Een binaire boom is een boom datastructuur waarin elk bovenliggend knooppunt maximaal twee kinderen kan hebben. Bijvoorbeeld,
Binaire boom
Soorten binaire boom
Volledige binaire boom
Een volledige binaire boom is een speciaal type binaire boom waarin elk bovenliggend knooppunt / intern knooppunt twee of geen kinderen heeft.
Volledige binaire boom
Ga voor meer informatie naar de volledige binaire structuur.
Perfecte binaire boom
Een perfecte binaire boom is een type binaire boom waarin elk intern knooppunt precies twee onderliggende knooppunten heeft en alle bladknooppunten zich op hetzelfde niveau bevinden.
Perfecte binaire boom
Ga voor meer informatie naar perfect binary tree.
Voltooi binaire structuur
Een complete binaire boom is net als een volledige binaire boom, maar met twee grote verschillen
- Elk niveau moet volledig worden gevuld
- Alle bladelementen moeten naar links leunen.
- Het laatste leaf-element heeft misschien geen goede broer of zus, dwz een complete binaire boom hoeft geen volledige binaire boom te zijn.
Voltooi binaire structuur
Ga voor meer informatie naar de volledige binaire structuur.
Gedegenereerde of pathologische boom
Een gedegenereerde of pathologische boom is de boom met een enkel kind, links of rechts.
Gedegenereerde binaire boom
Scheve binaire boom
Een scheefstaande binaire boom is een pathologische / gedegenereerde boom waarin de boom ofwel wordt gedomineerd door de linkerknooppunten of de rechterknooppunten. Er zijn dus twee soorten scheve binaire boom: links scheve binaire boom en rechts scheve binaire boom .
Scheve binaire boom
Evenwichtige binaire boom
Het is een soort binaire boom waarin het verschil tussen de linker en rechter substructuur voor elk knooppunt 0 of 1 is.
Evenwichtige binaire boom
Ga voor meer informatie naar balanced binary tree.
Binaire boomweergave
Een knooppunt van een binaire boom wordt weergegeven door een structuur die een datagedeelte bevat en twee verwijzingen naar andere structuren van hetzelfde type.
struct node ( int data; struct node *left; struct node *right; ); 
Binaire boomweergave
Python, Java en C / C ++ voorbeelden
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); )
Binaire boomtoepassingen
- Voor gemakkelijke en snelle toegang tot gegevens
- In routeralgoritmen
- Heap-gegevensstructuur implementeren
- Syntaxisboom
