Бинарное дерево на языке Си: простое объяснение с примером

Здравствуйте! Зовут Кирилл, студент школы 21 и вологодского государственного университета. В этой статье вы узнаете, что такое бинарное дерево, как реализовать.

Бинарное дерево — это структура данных, где каждый узел (элемент) может иметь не более двух потомков: левый и правый. Главная идея бинарного дерева — это иерархия, когда элементы связаны друг с другом через связи (указатели).

Каждое число — это узел, а линии между ними — это связи. В этом дереве, например:

Узел 0 — это корень дерева.
Узел 1 — это правый потомок узла 0.
Узел 2 — это левый потомок узла 0.

Определения на английском: узел - node; корень - root; дерево - tree; листик - leaf.

Бинарные деревья часто используются для поиска, сортировки и хранения данных. Например, если дерево правильно организовано (как бинарное дерево поиска), мы можем быстро находить элементы, проверять их наличие или упорядочивать данные.

Шаг 1: определение структуры узла

typedef struct binaryTree {(используйте не анонимную структуру, иначе компилятор не увидит определения структуры) int data; struct binaryTree *left; struct binaryTree *right; } binaryTree;

Для наглядности - визуализация структуры.

Шаг 2: инициализация нового узла

void createNode(binaryTree **root, int data) { *root = (binaryTree *)malloc(sizeof(binaryTree)); if (*root == NULL) { printf("error memorry"); return; } (*root)->data = data;//приоритет -> больше *, поэтому в скобки (*root)->left = NULL; (*root)->right = NULL; }

Шаг 3: инициализация узлов

#include <stdio.h> #include <stdlib.h> #include <stdlib.h> #include <time.h> #define COUNT_OF_NODES 15 void createNode(binaryTree **root, int data) { *root = (binaryTree *)malloc(sizeof(binaryTree)); if (*root == NULL) { fprintf(stderr, "Memory allocation failed\n"); exit(EXIT_FAILURE); } (*root)->data = data; (*root)->left = NULL; (*root)->right = NULL; } void insertNode(binaryTree ** root, int data) { if (*root == NULL) { createNode(root, data); return; } if (data < (*root)->data) { insertNode(&(*root)->left, data); } else { insertNode(&(*root)->right, data); } } int main() { int count_of_tabs = 0; srand(time(NULL)); char tabs_buf[MAX_TABS] = {0}; binaryTree * node = NULL; for (unsigned char i = 0; i < COUNT_OF_NODES; ++i) { insertNode(&node, rand()%100); return 0; } }

Бинарное дерево создано, но для наглядности можно реализовать обход дерева с выводом и нахождение звена(также реализую стек с выводом \t, это опционально, для красоты):

void pushTab(char tabs_buf[MAX_TABS], int *count_of_tabs) { if (*count_of_tabs >= MAX_TABS - 1) return; // -1 для терминального символа tabs_buf[(*count_of_tabs)++] = '\t'; tabs_buf[*count_of_tabs] = '\0'; } void popTab(char tabs_buf[MAX_TABS], int *count_of_tabs) { if (*count_of_tabs <= 0) return; tabs_buf[--(*count_of_tabs)] = '\0'; } void treeTraversal(binaryTree * node, char tabs_buf[MAX_TABS], int * count_of_tabs) { if (!node) return; pushTab(tabs_buf, count_of_tabs); treeTraversal(node->right, tabs_buf, count_of_tabs); printf("%s%d\n", tabs_buf, node->data); treeTraversal(node->left, tabs_buf, count_of_tabs); popTab(tabs_buf, count_of_tabs); } binaryTree * nodeFind(binaryTree * root, int data) { int flag = 0; if (!root || root->data == data) flag = 1; binaryTree * elem; if (!flag && (elem = nodeFind(root->left, data))) flag = 2; if (!flag && (elem = nodeFind(root->right, data))) flag = 2; return flag == 1 || flag == 0? root : elem; }

Полный код:

#include <stdio.h> #include <stdlib.h> #include <stdlib.h> #include <time.h> #define COUNT_OF_NODES 15 #define MAX_TABS 10 typedef struct binaryTree { int data; struct binaryTree *left; struct binaryTree *right; } binaryTree; void freeTree(binaryTree *node) { if (!node) return; freeTree(node->left); freeTree(node->right); free(node); } void createNode(binaryTree **root, int data) { *root = (binaryTree *)malloc(sizeof(binaryTree)); if (*root == NULL) { fprintf(stderr, "Memory allocation failed\n"); exit(EXIT_FAILURE); } (*root)->data = data; (*root)->left = NULL; (*root)->right = NULL; } void pushTab(char tabs_buf[MAX_TABS], int *count_of_tabs) { if (*count_of_tabs >= MAX_TABS - 1) return; // -1 для терминального символа tabs_buf[(*count_of_tabs)++] = '\t'; tabs_buf[*count_of_tabs] = '\0'; } void popTab(char tabs_buf[MAX_TABS], int *count_of_tabs) { if (*count_of_tabs <= 0) return; tabs_buf[--(*count_of_tabs)] = '\0'; } void treeTraversal(binaryTree * node, char tabs_buf[MAX_TABS], int * count_of_tabs) { if (!node) return; pushTab(tabs_buf, count_of_tabs); treeTraversal(node->right, tabs_buf, count_of_tabs); printf("%s%d\n", tabs_buf, node->data); treeTraversal(node->left, tabs_buf, count_of_tabs); popTab(tabs_buf, count_of_tabs); } binaryTree * nodeFind(binaryTree * root, int data) { int flag = 0; if (!root || root->data == data) flag = 1; binaryTree * elem; if (!flag && (elem = nodeFind(root->left, data))) flag = 2; if (!flag && (elem = nodeFind(root->right, data))) flag = 2; return flag == 1 || flag == 0? root : elem; } void insertNode(binaryTree ** root, int data) { if (*root == NULL) { createNode(root, data); return; } if (data < (*root)->data) { insertNode(&(*root)->left, data); } else { insertNode(&(*root)->right, data); } } int main() { int count_of_tabs = 0; srand(time(NULL)); char tabs_buf[MAX_TABS] = {0}; binaryTree * node = NULL; for (unsigned char i = 0; i < COUNT_OF_NODES; ++i) { insertNode(&node, rand()%100); } treeTraversal(node, tabs_buf, &count_of_tabs); binaryTree * node10 = nodeFind(node, 10); if (!node10) printf("%d", node10->data); else printf("The value is not found"); freeTree(node); }

В этой статье я привел базовую реализацию бинарного дерева. Она включает создание нового узла, сортировку, нахождение узла и обход дерева. Понимание такого бинарного дерева (фундаментального) - первый шаг к освоению более сложных структур данных.

Бинарное дерево на языке Си: простое объяснение с примером

Что такое бинарное дерево?

Реализация бинарного дерева

Заключение