Šioje pamokoje sužinosite apie visą dvejetainį medį ir jo skirtingus tipus. Taip pat rasite veikiančius viso dvejetainio medžio pavyzdžius C, C ++, Java ir Python.
Pilnas dvejetainis medis yra dvejetainis medis, kuriame visi lygiai yra visiškai užpildyti, išskyrus žemiausią, kuris užpildytas iš kairės.
Visiškas dvejetainis medis yra toks pat kaip visas dvejetainis medis, tačiau turi du pagrindinius skirtumus
- Visi lapų elementai turi pasvirti į kairę.
- Paskutinis lapo elementas gali neturėti tinkamo brolio ar sesers, ty visas dvejetainis medis nebūtinai turi būti visas dvejetainis medis.
Visiškas dvejetainis medis
Visas dvejetainis medis vs pilnas dvejetainis medis
Pilno dvejetainio medžio ir viso dvejetainio medžio 
palyginimas Viso dvejetainio medžio ir pilno dvejetainio medžio palyginimas Viso dvejetainio medžio ir pilno dvejetainio medžio 
palyginimas Viso dvejetainio medžio ir pilno dvejetainio medžio 
palyginimas
Kaip sukuriamas pilnas dvejetainis medis?
- Pasirinkite pirmąjį sąrašo elementą, kuris bus šaknies mazgas. (I lygio elementų skaičius: 1)
Pasirinkite pirmąjį elementą kaip šaknį - Antrąjį elementą įdėkite kaip kairįjį šaknies mazgo vaiką, o trečiąjį - kaip dešinįjį. (II lygio elementų skaičius: 2)
12 kaip kairysis vaikas ir 9 kaip dešinysis - Įdėkite kitus du elementus kaip kairiojo antrojo lygio mazgo vaikus. Vėlgi, įdėkite du kitus elementus kaip antrojo lygio dešiniojo mazgo vaikus (elementų skaičius III lygio elementuose: 4).
- Kartokite tol, kol pasieksite paskutinį elementą.
5 kaip kairysis vaikas ir 6 kaip dešinysis vaikas
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
„Python Java C C ++“ # Checking if a binary tree is a complete binary tree in C class Node: def __init__(self, item): self.item = item self.left = None self.right = None # Count the number of nodes def count_nodes(root): if root is None: return 0 return (1 + count_nodes(root.left) + count_nodes(root.right)) # Check if the tree is complete binary tree def is_complete(root, index, numberNodes): # Check if the tree is empty if root is None: return True if index>= numberNodes: return False return (is_complete(root.left, 2 * index + 1, numberNodes) and is_complete(root.right, 2 * index + 2, numberNodes)) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) node_count = count_nodes(root) index = 0 if is_complete(root, index, node_count): print("The tree is a complete binary tree") else: print("The tree is not a complete binary tree")
// Checking if a binary tree is a complete binary tree in Java // Node creation class Node ( int data; Node left, right; Node(int item) ( data = item; left = right = null; ) ) class BinaryTree ( Node root; // Count the number of nodes int countNumNodes(Node root) ( if (root == null) return (0); return (1 + countNumNodes(root.left) + countNumNodes(root.right)); ) // Check for complete binary tree boolean checkComplete(Node root, int index, int numberNodes) ( // Check if the tree is empty if (root == null) return true; if (index>= numberNodes) return false; return (checkComplete(root.left, 2 * index + 1, numberNodes) && checkComplete(root.right, 2 * index + 2, numberNodes)); ) 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.right = new Node(5); tree.root.left.left = new Node(4); tree.root.right.left = new Node(6); int node_count = tree.countNumNodes(tree.root); int index = 0; if (tree.checkComplete(tree.root, index, node_count)) System.out.println("The tree is a complete binary tree"); else System.out.println("The tree is not a complete binary tree"); ) )
// Checking if a binary tree is a complete binary tree in C #include #include #include struct Node ( int key; struct Node *left, *right; ); // 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; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is complete if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) 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); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) printf("The tree is a complete binary tree"); else printf("The tree is not a complete binary tree"); )
// Checking if a binary tree is a complete binary tree in C++ #include using namespace std; struct Node ( int key; struct Node *left, *right; ); // Create node struct Node *newNode(char k) ( struct Node *node = (struct Node *)malloc(sizeof(struct Node)); node->key = k; node->right = node->left = NULL; return node; ) // Count the number of nodes int countNumNodes(struct Node *root) ( if (root == NULL) return (0); return (1 + countNumNodes(root->left) + countNumNodes(root->right)); ) // Check if the tree is a complete binary tree bool checkComplete(struct Node *root, int index, int numberNodes) ( // Check if the tree is empty if (root == NULL) return true; if (index>= numberNodes) return false; return (checkComplete(root->left, 2 * index + 1, numberNodes) && checkComplete(root->right, 2 * index + 2, numberNodes)); ) 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); int node_count = countNumNodes(root); int index = 0; if (checkComplete(root, index, node_count)) cout << "The tree is a complete binary tree"; else cout << "The tree is not a complete binary tree"; )
Masyvo indeksų ir medžio elemento ryšys
Visas dvejetainis medis turi įdomią savybę, kurią galime naudoti norėdami surasti bet kurio mazgo vaikus ir tėvus.
Jei kurio nors masyvo elemento indeksas yra i, indekso elementas 2i+1taps kairiuoju, o 2i+2indekso elementas - dešiniuoju. Be to, bet kurio indekso i elemento tėvą nurodo apatinė riba (i-1)/2.
Išbandykime,
Kairysis vaikas iš 1 (indeksas 0) = elementas (2 * 0 + 1) rodyklėje = elementas 1 rodyklėje = 12 dešinysis 1 vaikas = elementas (2 * 0 + 2) rodyklėje = elementas 2 rodyklėje = 9 Panašiai, Kairysis 12 vaikų vaikas (1 indeksas) = elementas (2 * 1 + 1) rodyklėje = elementas 3 rodyklėje = 5 Dešinysis 12 vaikų vaikas = elementas (2 * 1 + 2) rodyklėje = elementas 4 rodyklėje = 6
Taip pat patvirtinkime, kad taisyklės galioja norint rasti bet kurio mazgo tėvą
9 tėvai (2 pozicija) = (2-1) / 2 = ½ = 0,5 ~ 0 indeksas = 1 12 tėvų (1 pozicija) = (1-1) / 2 = 0 indeksas = 1
Suprasti šį masyvo indeksų susiejimą su medžių pozicijomis yra labai svarbu norint suprasti, kaip veikia kaupo duomenų struktūra ir kaip ji naudojama įgyvendinant „Heap Sort“.
Užbaigti dvejetainių medžių programas
- Krūva pagrįstos duomenų struktūros
- Krūvos rūšis
