Binaarinen puu

Tässä opetusohjelmassa opit binääripuusta ja sen eri tyypeistä. Löydät myös toimivia esimerkkejä binääripuusta C, C ++, Java ja Python.

Binaarinen puu on puun tietorakenne, jossa jokaisella vanhemmalla solmulla voi olla enintään kaksi lasta. Esimerkiksi,

Binaarinen puu

Binaaripuun tyypit

Täysi binääripuu

Täysi binääripuu on erityinen binääripuu, jossa jokaisella vanhemmalla solmulla / sisäisellä solmulla on joko kaksi lasta tai ei yhtään lasta.

Täysi binääripuu

Jos haluat lisätietoja, käy koko binääripuussa.

Täydellinen binääripuu

Täydellinen binääripuu on binääripuun tyyppi, jossa jokaisessa sisäisessä solmussa on täsmälleen kaksi lapsisolmua ja kaikki lehtisolmut ovat samalla tasolla.

Täydellinen binääripuu

Jos haluat lisätietoja, käy täydellisessä binääripuussa.

Täydellinen binääripuu

Täydellinen binääripuu on aivan kuin täysi binääripuu, mutta sillä on kaksi suurta eroa

  1. Jokaisen tason on oltava täysin täytetty
  2. Kaikkien lehtielementtien on kallistettava vasemmalle.
  3. Viimeisellä lehtielementillä ei ehkä ole oikeaa sisarusta, ts. Täydellisen binääripuun ei tarvitse olla täysi binääripuu.
Täydellinen binääripuu

Jos haluat lisätietoja, käy täydellisessä binääripuussa.

Rappeutunut tai patologinen puu

Rappeutunut tai patologinen puu on puu, jolla on yksi lapsi joko vasemmalle tai oikealle.

Rappeutunut binääripuu

Vino binääripuu

Vino binääripuu on patologinen / rappeutunut puu, jossa puuta joko hallitsevat vasen tai oikea solmu. Siten vinoutuneita binääripuita on kahta tyyppiä: vasemmalle vinottu binääripuu ja oikealle vinottu binääripuu .

Vino binääripuu

Tasapainoinen binääripuu

Se on binääripuun tyyppi, jossa vasemman ja oikean alipuun ero kullekin solmulle on joko 0 tai 1.

Tasapainoinen binääripuu

Jos haluat lisätietoja, käy tasapainotetussa binääripuussa.

Binaaripuun esitys

Binaarisen puun solmua edustaa rakenne, joka sisältää tieto-osan ja kaksi osoittinta muihin samantyyppisiin rakenteisiin.

 struct node ( int data; struct node *left; struct node *right; );
Binaaripuun esitys

Python-, Java- ja C / C ++ -esimerkkejä

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); )

Binaaripuun sovellukset

  • Helppo ja nopea pääsy tietoihin
  • Reitittimen algoritmeissa
  • Kasan tietorakenteen toteuttamiseksi
  • Syntaksipuu

Mielenkiintoisia artikkeleita...