Bu eğitimde, mükemmel ikili ağaç hakkında bilgi edineceksiniz. Ayrıca, C, C ++, Java ve Python'da mükemmel bir ikili ağacı kontrol etmek için çalışma örnekleri bulacaksınız.
Mükemmel bir ikili ağaç, her iç düğümün tam olarak iki çocuk düğüme sahip olduğu ve tüm yaprak düğümlerinin aynı seviyede olduğu bir tür ikili ağaçtır.
Mükemmel İkili Ağaç
Tüm dahili düğümlerin derecesi 2'dir.
Yinelemeli olarak, mükemmel bir ikili ağaç şu şekilde tanımlanabilir:
- Tek bir düğümün çocuğu yoksa, mükemmel bir ikili yükseklik ağacıdır
h = 0, - Bir düğüm varsa
h> 0, her iki alt ağacı da yüksekse ve çakışmıyorsa, bu mükemmel bir ikili ağaçtırh - 1.
Mükemmel İkili Ağaç (Özyinelemeli Temsil)
Python, Java ve C / C ++ Örnekleri
Aşağıdaki kod, bir ağacın mükemmel bir ikili ağaç olup olmadığını kontrol etmek içindir.
Python Java C C ++ # Checking if a binary tree is a perfect binary tree in Python class newNode: def __init__(self, k): self.key = k self.right = self.left = None # Calculate the depth def calculateDepth(node): d = 0 while (node is not None): d += 1 node = node.left return d # Check if the tree is perfect binary tree def is_perfect(root, d, level=0): # Check if the tree is empty if (root is None): return True # Check the presence of trees if (root.left is None and root.right is None): return (d == level + 1) if (root.left is None or root.right is None): return False return (is_perfect(root.left, d, level + 1) and is_perfect(root.right, d, level + 1)) root = None root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) if (is_perfect(root, calculateDepth(root))): print("The tree is a perfect binary tree") else: print("The tree is not a perfect binary tree")
// Checking if a binary tree is a perfect binary tree in Java class PerfectBinaryTree ( static class Node ( int key; Node left, right; ) // Calculate the depth static int depth(Node node) ( int d = 0; while (node != null) ( d++; node = node.left; ) return d; ) // Check if the tree is perfect binary tree static boolean is_perfect(Node root, int d, int level) ( // Check if the tree is empty if (root == null) return true; // If for children if (root.left == null && root.right == null) return (d == level + 1); if (root.left == null || root.right == null) return false; return is_perfect(root.left, d, level + 1) && is_perfect(root.right, d, level + 1); ) // Wrapper function static boolean is_Perfect(Node root) ( int d = depth(root); return is_perfect(root, d, 0); ) // Create a new node static Node newNode(int k) ( Node node = new Node(); node.key = k; node.right = null; node.left = null; return node; ) public static void main(String args()) ( Node root = null; root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); if (is_Perfect(root) == true) System.out.println("The tree is a perfect binary tree"); else System.out.println("The tree is not a perfect binary tree"); ) )
// Checking if a binary tree is a perfect binary tree in C #include #include #include struct node ( int data; struct node *left; struct node *right; ); // Creating a new node 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); ) // Calculate the depth int depth(struct node *node) ( int d = 0; while (node != NULL) ( d++; node = node->left; ) return d; ) // Check if the tree is perfect bool is_perfect(struct node *root, int d, int level) ( // Check if the tree is empty if (root == NULL) return true; // Check the presence of children if (root->left == NULL && root->right == NULL) return (d == level + 1); if (root->left == NULL || root->right == NULL) return false; return is_perfect(root->left, d, level + 1) && is_perfect(root->right, d, level + 1); ) // Wrapper function bool is_Perfect(struct node *root) ( int d = depth(root); return is_perfect(root, d, 0); ) 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->right->left = newnode(6); if (is_Perfect(root)) printf("The tree is a perfect binary tree"); else printf("The tree is not a perfect binary tree"); )
// Checking if a binary tree is a perfect binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); int depth(Node *node) ( int d = 0; while (node != NULL) ( d++; node = node->left; ) return d; ) bool isPerfectR(struct Node *root, int d, int level = 0) ( if (root == NULL) return true; if (root->left == NULL && root->right == NULL) return (d == level + 1); if (root->left == NULL || root->right == NULL) return false; return isPerfectR(root->left, d, level + 1) && isPerfectR(root->right, d, level + 1); ) bool isPerfect(Node *root) ( int d = depth(root); return isPerfectR(root, d); ) struct Node *newNode(int k) ( struct Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; ) 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->right->left = newNode(6); if (isPerfect(root)) cout << "The tree is a perfect binary tree"; else cout << "The tree is not a perfect binary tree"; )
Mükemmel İkili Ağaç Teoremleri
- Mükemmel bir ikili ağaç yüksekliğinde h düğümü vardır.
2h + 1 - 1 - Düğümlü mükemmel bir ikili ağacın yüksekliği vardır
log(n + 1) - 1 = Θ(ln(n)). - Mükemmel bir ikili ağaç yüksekliğinde h yaprak düğümlerine sahiptir.
2h - Mükemmel bir ikili ağaçtaki bir düğümün ortalama derinliği
Θ(ln(n)).
