Binaarne puu

Selles õpetuses saate teada binaarpuust ja selle erinevatest tüüpidest. Samuti leiate C, C ++, Java ja Pythoni binaarpuu toimivaid näiteid.

Binaarne puu on puu andmestruktuur, milles igal vanemsõlmel võib olla kuni kaks last. Näiteks,

Binaarne puu

Binaarse puu tüübid

Täielik binaarne puu

Täisbinaarne puu on spetsiaalne kahendpuu tüüp, milles igal vanemsõlmel / sisesõlmel on kas kaks last või mitte ühtegi last.

Täielik binaarne puu

Lisateabe saamiseks külastage palun täielikku kahendpuud.

Ideaalne kahendpuu

Täiuslik binaarne puu on kahendpuu tüüp, milles igal sisesõlmel on täpselt kaks lapsesõlme ja kõik lehesõlmed on samal tasemel.

Ideaalne kahendpuu

Lisateabe saamiseks külastage täiuslikku kahendpuud.

Täielik binaarne puu

Täielik binaarne puu on täpselt nagu täielik binaarne puu, kuid sellel on kaks suurt erinevust

  1. Iga tase peab olema täielikult täidetud
  2. Kõik leheelemendid peavad kalduma vasakule.
  3. Viimasel leheelemendil ei pruugi olla õiget õde-venda, st täielik kahendpuu ei pea olema täielik kahendpuu.
Täielik binaarne puu

Lisateabe saamiseks külastage palun täielikku binaarpuud.

Taandarenenud ehk patoloogiline puu

Taandarenenud või patoloogiline puu on puu, millel on üks laps kas vasakul või paremal.

Degenereerunud kahendpuu

Viltune binaarne puu

Viltune binaarne puu on patoloogiline / taandarenenud puu, milles puust domineerivad kas vasak- või parempoolsed sõlmed. Seega on viltust kahendpuud kahte tüüpi: vasak- ja parempoolne kahepoolne puu .

Viltune binaarne puu

Tasakaalus binaarne puu

See on kahendpuu tüüp, milles iga sõlme vasaku ja parema alampuu vahe on kas 0 või 1.

Tasakaalus binaarne puu

Lisateabe saamiseks külastage tasakaalustatud kahendpuud.

Binaarse puu esindus

Binaarse puu sõlme esindab struktuur, mis sisaldab andmeosa ja kahte viidet teistele sama tüüpi struktuuridele.

 struct node ( int data; struct node *left; struct node *right; );
Binaarse puu esindus

Pythoni, Java ja C / C ++ näited

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

Binaarpuu rakendused

  • Andmetele lihtsaks ja kiireks juurdepääsuks
  • Ruuteri algoritmides
  • Hunniku andmestruktuuri juurutamiseks
  • Süntaksipuu

Huvitavad Artiklid...