Cây nhị phân đầy đủ

Trong hướng dẫn này, bạn sẽ tìm hiểu về cây nhị phân đầy đủ và các định lý khác nhau của nó. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc để kiểm tra cây nhị phân đầy đủ trong C, C ++, Java và Python.

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.

Nó còn được gọi là cây nhị phân thích hợp .

Cây nhị phân đầy đủ

Định lý cây nhị phân đầy đủ

 Let, i = the number of internal nodes n = be the total number of nodes l = number of leaves λ = number of levels
  1. Số lượng lá là i + 1.
  2. Tổng số nút là 2i + 1.
  3. Số nút bên trong là (n - 1) / 2.
  4. Số lượng lá là (n + 1) / 2.
  5. Tổng số nút là 2l - 1.
  6. Số nút bên trong là l - 1.
  7. Số lượng lá nhiều nhất .2λ - 1

Ví dụ về Python, Java và C / C ++

Đoạn mã sau dùng để kiểm tra xem một cây có phải là một cây nhị phân đầy đủ hay không.

Python Java C C + 
 # Checking if a binary tree is a full binary tree in Python # Creating a node class Node: def __init__(self, item): self.item = item self.leftChild = None self.rightChild = None # Checking full binary tree def isFullTree(root): # Tree empty case if root is None: return True # Checking whether child is present if root.leftChild is None and root.rightChild is None: return True if root.leftChild is not None and root.rightChild is not None: return (isFullTree(root.leftChild) and isFullTree(root.rightChild)) return False root = Node(1) root.rightChild = Node(3) root.leftChild = Node(2) root.leftChild.leftChild = Node(4) root.leftChild.rightChild = Node(5) root.rightChild.leftChild.leftChild = Node(6) root.rightChild.leftChild.rightChild = Node(7) if isFullTree(root): print("The tree is a full binary tree") else: print("The tree is not a full binary full") 
 // Checking if a binary tree is a full binary tree in Java class Node ( int data; Node leftChild, rightChild; Node(int item) ( data = item; leftChild = rightChild = null; ) ) class BinaryTree ( Node root; // Check for Full Binary Tree boolean isFullBinaryTree(Node node) ( // Checking tree emptiness if (node == null) return true; // Checking the children if (node.leftChild == null && node.rightChild == null) return true; if ((node.leftChild != null) && (node.rightChild != null)) return (isFullBinaryTree(node.leftChild) && isFullBinaryTree(node.rightChild)); return false; ) public static void main(String args()) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.leftChild = new Node(2); tree.root.rightChild = new Node(3); tree.root.leftChild.leftChild = new Node(4); tree.root.leftChild.rightChild = new Node(5); tree.root.rightChild.leftChild = new Node(6); tree.root.rightChild.rightChild = new Node(7); if (tree.isFullBinaryTree(tree.root)) System.out.print("The tree is a full binary tree"); else System.out.print("The tree is not a full binary tree"); ) )
 // Checking if a binary tree is a full binary tree in C #include #include #include struct Node ( int item; struct Node *left, *right; ); // Creation of new Node struct Node *createNewNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->item = k; node->right = node->left = NULL; return node; ) bool isFullBinaryTree(struct Node *root) ( // Checking tree emptiness if (root == NULL) return true; // Checking the presence of children if (root->left == NULL && root->right == NULL) return true; if ((root->left) && (root->right)) return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right)); return false; ) int main() ( struct Node *root = NULL; root = createNewNode(1); root->left = createNewNode(2); root->right = createNewNode(3); root->left->left = createNewNode(4); root->left->right = createNewNode(5); root->left->right->left = createNewNode(6); root->left->right->right = createNewNode(7); if (isFullBinaryTree(root)) printf("The tree is a full binary tree"); else printf("The tree is not a full binary full"); )
 // Checking if a binary tree is a full binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); // New node creation struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) bool isFullBinaryTree(struct Node *root) ( // Checking for emptiness if (root == NULL) return true; // Checking for the presence of children if (root->left == NULL && root->right == NULL) return true; if ((root->left) && (root->right)) return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right)); return false; ) int main() ( struct Node *root = NULL; root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->right->left = newNode(6); root->left->right->right = newNode(7); if (isFullBinaryTree(root)) cout << "The tree is a full binary tree"; else cout << "The tree is not a full binary full"; )

thú vị bài viết...