Dalam tutorial ini, anda akan belajar mengenai pokok binari dan pelbagai jenisnya. Anda juga akan mendapat contoh pokok binari yang berfungsi di C, C ++, Java dan Python.
Pokok binari adalah struktur data pokok di mana setiap nod ibu bapa boleh mempunyai paling banyak dua anak. Sebagai contoh,
Pokok Perduaan
Jenis Pokok Perduaan
Pokok Perduaan Penuh
Pokok binari penuh adalah jenis pokok binari khas di mana setiap nod ibu bapa / nod dalaman mempunyai dua atau tidak ada anak.
Pokok Perduaan Penuh
Untuk mengetahui lebih lanjut, sila lawati pokok binari penuh.
Pokok Perduaan Sempurna
Pokok binari yang sempurna adalah sejenis pokok binari di mana setiap simpul dalaman mempunyai dua simpul anak dan semua simpul daun berada pada tahap yang sama.
Pokok Perduaan Sempurna
Untuk mengetahui lebih lanjut, sila lawati pokok binari yang sempurna.
Pokok Perduaan Lengkap
Pokok binari lengkap sama seperti pokok binari penuh, tetapi dengan dua perbezaan utama
- Setiap tahap mesti dipenuhi sepenuhnya
- Semua elemen daun mesti condong ke kiri.
- Unsur daun terakhir mungkin tidak mempunyai saudara yang betul iaitu pokok binari yang lengkap tidak harus menjadi pokok binari yang lengkap.
Pokok Perduaan Lengkap
Untuk mengetahui lebih lanjut, sila lawati pokok binari lengkap.
Pokok Degenerasi atau Patologi
Pokok yang merosot atau patologi adalah pokok yang mempunyai anak tunggal sama ada kiri atau kanan.
Pokok Binari yang merosot
Pokok Perduaan Skewed
Pokok binari condong adalah pokok patologi / degenerasi di mana pokok itu dikuasai oleh simpul kiri atau simpul kanan. Oleh itu, terdapat dua jenis pokok binari miring: pokok binari miring kiri dan pokok binari miring kanan .
Pokok Perduaan Skewed
Pokok Perduaan Seimbang
Ini adalah sejenis pokok binari di mana perbezaan antara subtree kiri dan kanan untuk setiap nod sama ada 0 atau 1.
Pokok Perduaan Seimbang
Untuk mengetahui lebih lanjut, sila lawati pokok binari seimbang.
Perwakilan Pokok Perduaan
Node pokok binari diwakili oleh struktur yang mengandungi bahagian data dan dua petunjuk ke struktur lain dengan jenis yang sama.
struct node ( int data; struct node *left; struct node *right; ); 
Perwakilan Pokok Perduaan
Contoh Python, Java dan 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); )
Aplikasi Pokok Perduaan
- Untuk akses data yang mudah dan cepat
- Dalam algoritma penghala
- Untuk melaksanakan struktur data timbunan
- Pokok sintaks
