عُقد الشجرة وبنيتها

ما الشجرة الثنائية

بنية العقدة

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

لماذا نستخدم مؤشرات تشير إلى النوع نفسه

struct Node {
    int value;
    struct Node *left;   /* 8 bytes on 64-bit */
    struct Node *right;  /* 8 bytes on 64-bit */
};

typedef لتسهيل الاستخدام

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

تخصيص عقدة

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return NULL;
    n->value = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

بناء شجرة صغيرة يدويًا

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Node *create_node(int v) {
    Node *n = malloc(sizeof(Node));
    n->value = v; n->left = NULL; n->right = NULL;
    return n;
}

int main(void) {
    Node *root = create_node(10);
    root->left = create_node(5);
    root->right = create_node(15);
    printf("%d %d %d\n", root->left->value, root->value, root->right->value);
    return 0;
}

الوصول إلى الأحفاد

/* root
 *   \
 *    right (15)
 *        \
 *         right->right (20)
 */
if (root->right != NULL && root->right->right != NULL)
    printf("%d\n", root->right->right->value);

عدّ العقد تكراريًا

int count_nodes(Node *root) {
    if (root == NULL) return 0;
    return 1 + count_nodes(root->left)
             + count_nodes(root->right);
}

قياس الارتفاع

int height(Node *root) {
    if (root == NULL) return -1;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

التعرّف على الأوراق

int is_leaf(Node *n) {
    return n != NULL && n->left == NULL && n->right == NULL;
}

توظيف البنية

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }

int main(void){
    Node *root = nn(10);
    root->left = nn(5); root->right = nn(15);
    root->left->left = nn(2);
    printf("nodes=%d height=%d\n", count(root), height(root));
    return 0;
}

تحقّق سريع

مراجعة