Trong hướng dẫn này, bạn sẽ tìm hiểu về cây nhị phân và các loại khác nhau của nó. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của cây nhị phân trong C, C ++, Java và Python.
Cây nhị phân là một cấu trúc dữ liệu dạng cây trong đó mỗi nút cha có thể có nhiều nhất hai nút con. Ví dụ,
Cây nhị phân
Các loại cây nhị phân
Cây nhị phân đầy đủ
Cây nhị phân đầy đủ là một loại cây nhị phân đặc biệt trong đó mọi nút cha / nút nội bộ đều có hai hoặc không có nút con.
Cây nhị phân đầy đủ
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân đầy đủ.
Cây nhị phân hoàn hảo
Cây nhị phân hoàn hảo là một loại cây nhị phân trong đó mỗi nút bên trong có đúng hai nút con và tất cả các nút lá đều ở cùng một mức.
Cây nhị phân hoàn hảo
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân hoàn hảo.
Cây nhị phân hoàn chỉnh
Một cây nhị phân hoàn chỉnh cũng giống như một cây nhị phân đầy đủ, nhưng có hai điểm khác biệt chính
- Mọi cấp độ phải được lấp đầy hoàn toàn
- Tất cả các phần tử lá phải nghiêng về bên trái.
- Phần tử lá cuối cùng có thể không có anh chị em bên phải, tức là một cây nhị phân hoàn chỉnh không phải là một cây nhị phân đầy đủ.
Cây nhị phân hoàn chỉnh
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân hoàn chỉnh.
Cây thoái hóa hoặc bệnh lý
Cây thoái hóa hoặc cây bệnh là cây có một con hoặc trái hoặc phải.
Tạo cây nhị phân
Cây nhị phân xiên
Cây nhị phân lệch là cây bệnh lý / thoái hóa trong đó cây bị chi phối bởi các nút bên trái hoặc các nút bên phải. Như vậy, có hai loại cây nhị phân lệch: cây nhị phân lệch trái và cây nhị phân lệch phải .
Cây nhị phân xiên
Cây nhị phân cân bằng
Nó là một loại cây nhị phân trong đó sự khác biệt giữa cây con bên trái và bên phải cho mỗi nút là 0 hoặc 1.
Cây nhị phân cân bằng
Để tìm hiểu thêm, vui lòng truy cập cây nhị phân cân bằng.
Biểu diễn cây nhị phân
Một nút của cây nhị phân được biểu diễn bằng cấu trúc chứa một phần dữ liệu và hai con trỏ đến các cấu trúc khác cùng kiểu.
struct node ( int data; struct node *left; struct node *right; ); 
Biểu diễn cây nhị phân
Ví dụ về Python, Java và 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); )
Ứng dụng cây nhị phân
- Để truy cập dữ liệu dễ dàng và nhanh chóng
- Trong thuật toán bộ định tuyến
- Để triển khai cấu trúc dữ liệu heap
- Cây cú pháp
