Cây tìm kiếm nhị phân (BST)

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7
8def insert(node, key):9    if node is None:10        return Node(key)11    if key < node.key:12        node.left = insert(node.left, key)13    elif key > node.key:14        node.right = insert(node.right, key)15    return node  # duplicates are ignored16
17
18def search(node, key):19    if node is None:20        return False21    if key == node.key:22        return True23    if key < node.key:24        return search(node.left, key)25    return search(node.right, key)26
27
28def inorder(node):29    if node is None:30        return []31    return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36    root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))

1class Node {2    constructor(value) {3        this.value = value;4        this.left = null;5        this.right = null;6    }7}8
9class BinarySearchTree {10    constructor() {11        this.root = null;12    }13
14    insert(value) {15        const attach = (node) => {16            if (!node) return new Node(value);17            if (value < node.value) node.left = attach(node.left);18            else node.right = attach(node.right);19            return node;20        };21        this.root = attach(this.root);22    }23
24    search(value) {25        let current = this.root;26        while (current) {27            if (value === current.value) return true;28            current = value < current.value ? current.left : current.right;29        }30        return false;31    }32
33    // Inorder traversal of a BST visits values in sorted order34    inorder(node = this.root, out = []) {35        if (!node) return out;36        this.inorder(node.left, out);37        out.push(node.value);38        this.inorder(node.right, out);39        return out;40    }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));

1public class Main {2    static class Node {3        int key;4        Node left, right;5        Node(int key) { this.key = key; }6    }7
8    static Node insert(Node node, int key) {9        if (node == null) return new Node(key);10        // Smaller keys go left, larger keys go right11        if (key < node.key) node.left = insert(node.left, key);12        else if (key > node.key) node.right = insert(node.right, key);13        return node;14    }15
16    static boolean search(Node node, int key) {17        if (node == null) return false;18        if (key == node.key) return true;19        return key < node.key ? search(node.left, key) : search(node.right, key);20    }21
22    static void inorder(Node node, StringBuilder sb) {23        if (node == null) return;24        inorder(node.left, sb);25        sb.append(node.key).append(" ");26        inorder(node.right, sb);27    }28
29    public static void main(String[] args) {30        Node root = null;31        int[] keys = {8, 3, 10, 1, 6, 14, 4};32        for (int k : keys) root = insert(root, k);33
34        StringBuilder sb = new StringBuilder();35        inorder(root, sb);36        System.out.println("Inorder (sorted): " + sb.toString().trim());37        System.out.println("search 6: " + search(root, 6));38        System.out.println("search 7: " + search(root, 7));39    }40}

1#include <iostream>2
3struct Node {4    int value;5    Node* left = nullptr;6    Node* right = nullptr;7    explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11    if (root == nullptr) return new Node(value);12    if (value < root->value) root->left = insert(root->left, value);13    else if (value > root->value) root->right = insert(root->right, value);14    return root;  // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18    // Walk down: smaller goes left, larger goes right19    while (root != nullptr) {20        if (value == root->value) return true;21        root = value < root->value ? root->left : root->right;22    }23    return false;24}25
26void inorder(const Node* node) {27    if (node == nullptr) return;28    inorder(node->left);29    std::cout << node->value << " ";30    inorder(node->right);31}32
33int main() {34    Node* root = nullptr;35    for (int value : {50, 30, 70, 20, 40, 60, 80}) {36        root = insert(root, value);37    }38    std::cout << "Sorted: ";39    inorder(root);40    std::cout << "\n" << std::boolalpha;41    std::cout << "contains(40): " << contains(root, 40) << "\n";42    std::cout << "contains(45): " << contains(root, 45) << "\n";43    return 0;44}

1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6    int value;7    struct Node* left;8    struct Node* right;9} Node;10
11Node* newNode(int value) {12    Node* n = malloc(sizeof(Node));13    n->value = value;14    n->left = n->right = NULL;15    return n;16}17
18Node* insert(Node* root, int value) {19    if (root == NULL) return newNode(value);20    if (value < root->value) root->left = insert(root->left, value);21    else if (value > root->value) root->right = insert(root->right, value);22    return root;  // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26    // Walk down: smaller goes left, larger goes right27    while (root != NULL) {28        if (value == root->value) return true;29        root = value < root->value ? root->left : root->right;30    }31    return false;32}33
34void inorder(const Node* node) {35    if (node == NULL) return;36    inorder(node->left);37    printf("%d ", node->value);38    inorder(node->right);39}40
41int main(void) {42    int values[] = {50, 30, 70, 20, 40, 60, 80};43    Node* root = NULL;44    for (int i = 0; i < 7; i++) root = insert(root, values[i]);45    printf("Sorted: ");46    inorder(root);47    printf("\n");48    printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49    printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50    return 0;51}