I denne opplæringen vil du lære om binært tre og dets forskjellige typer. Du finner også arbeidseksempler på binært tre i C, C ++, Java og Python.
Et binært tre er en tredatastruktur der hver foreldrenode maksimalt kan ha to barn. For eksempel,
Binært tre
Typer av binært tre
Fullt binært tre
Et fullstendig binært tre er en spesiell type binært tre der hver foreldrenode / intern node har to eller ingen barn.
Fullt binært tre
Hvis du vil vite mer, kan du gå til det komplette binære treet.
Perfekt binært tre
Et perfekt binært tre er en type binært tre der hver intern node har nøyaktig to underordnede noder, og alle bladnodene er på samme nivå.
Perfekt binært tre
Hvis du vil lære mer, kan du gå til det perfekte binære treet.
Komplett binært tre
Et komplett binært tre er akkurat som et fullt binært tre, men med to store forskjeller
- Hvert nivå må være fullstendig fylt
- Alle bladelementene må lene seg mot venstre.
- Det siste bladelementet har kanskje ikke riktig søsken, dvs. et komplett binært tre trenger ikke å være et fullstendig binært tre.
Komplett binært tre
Hvis du vil vite mer, kan du gå til det komplette binære treet.
Degenerert eller patologisk tre
Et degenerert eller patologisk tre er treet som har et enkelt barn, enten venstre eller høyre.
Degenerert binært tre
Skjevt binært tre
Et skjevt binært tre er et patologisk / degenerert tre der treet enten domineres av venstre noder eller høyre noder. Dermed er det to typer skjevt binært tre: venstre-skjevt binært tre og høyre-skjevt binært tre .
Skjevt binært tre
Balansert binært tre
Det er en type binært tre der forskjellen mellom venstre og høyre undertre for hver node er enten 0 eller 1.
Balansert binært tre
For å lære mer, vennligst besøk balansert binært tre.
Representasjon av binært tre
En node i et binært tre er representert av en struktur som inneholder en datadel og to pekere til andre strukturer av samme type.
struct node ( int data; struct node *left; struct node *right; ); 
Representasjon av binært tre
Python, Java og C / C ++ eksempler
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); )
Binary Tree Applications
- For enkel og rask tilgang til data
- I ruteren algoritmer
- Å implementere haugdatastruktur
- Syntaks tre
