Edisi pembelajaran bahasa Indonesia. Kode dan keluarannya tetap seperti aslinya.

Binary search tree dalam C

Sisipkan dan cari kunci menggunakan urutan nilai dalam subtree.

Dalam binary search tree, kunci lebih kecil berada di satu subtree dan kunci lebih besar di subtree lain. Tentukan aturan untuk kunci duplikat sejak awal. Penelusuran inorder mengunjungi nilai dalam urutan menaik.

Pencarian membandingkan target dengan node saat ini dan memilih satu anak saja. Biayanya ditentukan oleh tinggi pohon: O(log N) untuk pohon seimbang, tetapi O(N) jika berbentuk rantai. Pohon sederhana tidak menyeimbangkan dirinya otomatis.

Periksa alokasi dan bebaskan anak sebelum induknya. Coba kunci terurut, duplikat, dan tidak ditemukan, lalu amati bentuk pohonnya.

Kode C

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

typedef struct BSTNode {
    int val;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

/* Return 0 on allocation failure without changing existing nodes. */
int insert(BSTNode **root, int val) {
    if (*root == NULL) {
        BSTNode *node = malloc(sizeof *node);
        if (node == NULL) return 0;
        node->val = val;
        node->left = node->right = NULL;
        *root = node;
        return 1;
    }
    if (val < (*root)->val) return insert(&(*root)->left, val);
    if (val > (*root)->val) return insert(&(*root)->right, val);
    return 1; /* Ignore duplicate keys. */
}

void inorder(const BSTNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->val);
        inorder(root->right);
    }
}

void freeBST(BSTNode *root) {
    if (root != NULL) {
        freeBST(root->left);
        freeBST(root->right);
        free(root);
    }
}

int main(void) {
    BSTNode *root = NULL;
    const int keys[] = {50, 30, 20, 40, 70, 60, 80};
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; i++) {
        if (!insert(&root, keys[i])) {
            fputs("Unable to allocate a BST node.\n", stderr);
            freeBST(root);
            return EXIT_FAILURE;
        }
    }

    printf("BST In-Order Sorted Traversal: ");
    inorder(root);
    printf("\n");

    freeBST(root);
    return EXIT_SUCCESS;
}

Buka di kompiler

Keluaran yang diharapkan

BST In-Order Sorted Traversal: 20 30 40 50 60 70 80

Pertanyaan umum

Mengapa kode dan keluarannya tetap dalam bahasa Inggris?

Kata kunci, pengenal, dan teks yang diperiksa tes dipertahankan agar program tidak berubah. Penjelasan dan kontrol telah diterjemahkan.