Двоичное дерево

1from collections import deque2
3
4class Node:5    def __init__(self, value):6        self.value = value7        self.left = None8        self.right = None9
10
11def insert(root, value):12    # Level-order insert: fill the first empty child slot found13    if root is None:14        return Node(value)15    queue = deque([root])16    while queue:17        node = queue.popleft()18        if node.left is None:19            node.left = Node(value)20            return root21        queue.append(node.left)22        if node.right is None:23            node.right = Node(value)24            return root25        queue.append(node.right)26
27
28def inorder(node):29    if node is None:30        return []31    return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36    root = insert(root, value)37
38print("Root:   ", root.value)39print("Inorder:", inorder(root))

1class Node {2    constructor(value) {3        this.value = value;4        this.left = null;5        this.right = null;6    }7}8
9class BinaryTree {10    constructor() {11        this.root = null;12    }13
14    // Insert at the first free spot, top to bottom (level order)15    insert(value) {16        const node = new Node(value);17        if (!this.root) {18            this.root = node;19            return;20        }21        const queue = [this.root];22        while (queue.length > 0) {23            const current = queue.shift();24            if (!current.left) {25                current.left = node;26                return;27            }28            if (!current.right) {29                current.right = node;30                return;31            }32            queue.push(current.left, current.right);33        }34    }35
36    inorder(node = this.root, out = []) {37        if (!node) return out;38        this.inorder(node.left, out);39        out.push(node.value);40        this.inorder(node.right, out);41        return out;42    }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));

1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5    static class Node {6        int value;7        Node left, right;8        Node(int value) { this.value = value; }9    }10
11    static Node root;12
13    // Insert at the first free slot in level order (keeps the tree complete)14    static void insert(int value) {15        Node node = new Node(value);16        if (root == null) { root = node; return; }17        Queue<Node> queue = new ArrayDeque<>();18        queue.add(root);19        while (!queue.isEmpty()) {20            Node cur = queue.poll();21            if (cur.left == null) { cur.left = node; return; }22            if (cur.right == null) { cur.right = node; return; }23            queue.add(cur.left);24            queue.add(cur.right);25        }26    }27
28    // Inorder: left subtree, node, right subtree29    static void inorder(Node node, StringBuilder sb) {30        if (node == null) return;31        inorder(node.left, sb);32        sb.append(node.value).append(" ");33        inorder(node.right, sb);34    }35
36    public static void main(String[] args) {37        for (int v = 1; v <= 7; v++) insert(v);38        StringBuilder sb = new StringBuilder();39        inorder(root, sb);40        System.out.println("Root: " + root.value);41        System.out.println("Inorder: " + sb.toString().trim());42    }43}

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 root->right = insert(root->right, value);14    return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19    if (node == nullptr) return;20    inorder(node->left);21    std::cout << node->value << " ";22    inorder(node->right);23}24
25int countNodes(const Node* node) {26    if (node == nullptr) return 0;27    return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31    Node* root = nullptr;32    for (int value : {8, 3, 10, 1, 6, 14, 4}) {33        root = insert(root, value);34    }35    std::cout << "In-order: ";36    inorder(root);37    std::cout << "\n";38    std::cout << "Node count: " << countNodes(root) << "\n";39    return 0;40}

1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* left;7    struct Node* right;8} Node;9
10Node* newNode(int value) {11    Node* n = malloc(sizeof(Node));12    n->value = value;13    n->left = n->right = NULL;14    return n;15}16
17Node* insert(Node* root, int value) {18    if (root == NULL) return newNode(value);19    if (value < root->value) root->left = insert(root->left, value);20    else root->right = insert(root->right, value);21    return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26    if (node == NULL) return;27    inorder(node->left);28    printf("%d ", node->value);29    inorder(node->right);30}31
32int countNodes(const Node* node) {33    if (node == NULL) return 0;34    return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38    int values[] = {8, 3, 10, 1, 6, 14, 4};39    Node* root = NULL;40    for (int i = 0; i < 7; i++) root = insert(root, values[i]);41    printf("In-order: ");42    inorder(root);43    printf("\n");44    printf("Node count: %d\n", countNodes(root));45    return 0;46}