Binarno stablo

U ovom uputstvu naučit ćete o binarnom stablu i njegovim različitim vrstama. Također ćete naći radne primjere binarnog stabla u C, C ++, Java i Python.

Binarno stablo je struktura podataka stabla u kojoj svaki roditeljski čvor može imati najviše dvoje djece. Na primjer,

Binarno stablo

Vrste binarnog stabla

Puno binarno stablo

Potpuno Binarno stablo posebna je vrsta binarnog stabla u kojem svaki roditeljski čvor / unutarnji čvor ima ili dvoje ili nikakvo podređeno dijete.

Puno binarno stablo

Da biste saznali više, posjetite cijelo binarno stablo.

Savršeno binarno stablo

Savršeno binarno stablo je vrsta binarnog stabla u kojem svaki unutarnji čvor ima točno dva podređena čvora i svi su čvorovi lista na istoj razini.

Savršeno binarno stablo

Da biste saznali više, posjetite savršeno binarno stablo.

Kompletno binarno stablo

Kompletno binarno stablo je poput punog binarnog stabla, ali s dvije glavne razlike

  1. Svaka razina mora biti potpuno ispunjena
  2. Svi elementi lista moraju se naginjati lijevo.
  3. Posljednji element lista možda nema pravog brata ili sestru, tj. Cjelovito binarno stablo ne mora biti potpuno binarno stablo.
Kompletno binarno stablo

Da biste saznali više, posjetite kompletno binarno stablo.

Izrođeno ili patološko stablo

Izrođeno ili patološko stablo je stablo koje ima jedno dijete lijevo ili desno.

Izrođeno binarno stablo

Iskošeno binarno stablo

Iskošeno binarno stablo je patološko / izrođeno stablo u kojem stablom dominiraju lijevi ili desni čvorovi. Dakle, postoje dvije vrste iskrivljenom binarnom stablu: lijevo-iskrivljen binarno stablo i desna iskrivljena binarno stablo .

Iskošeno binarno stablo

Uravnoteženo binarno stablo

To je vrsta binarnog stabla u kojoj je razlika između lijevog i desnog podstabla za svaki čvor 0 ili 1.

Uravnoteženo binarno stablo

Da biste saznali više, posjetite uravnoteženo binarno stablo.

Prikaz binarnog stabla

Čvor binarnog stabla predstavljen je strukturom koja sadrži dio podataka i dva pokazivača na druge strukture istog tipa.

 struct node ( int data; struct node *left; struct node *right; );
Prikaz binarnog stabla

Primjeri Pythona, Java i 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); )

Primjene binarnog stabla

  • Za jednostavan i brz pristup podacima
  • U algoritmima usmjerivača
  • Provesti strukturu podataka hrpe
  • Stablo sintakse

Zanimljivi članci...