Двоичные деревья на примере языка Си
Привет, сегодня поговорим про двоичные деревья на е языка си, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое двоичные деревья на е языка си , настоятельно рекомендую прочитать все из категории Структуры данных.
Двоичные деревья
корень ↙ +-------+ |данные | +---+---+ левое | | | правое поддерево +---+---+ поддерево ↘ ↙ ↘ ↙ +-------+ +-------+ |данные | |данные | +---+---+ +---+---+ | | | | 0 | | +---+---+ +---+---+ ↙ ↘ ↘ +-------+ +-------+ +-------+ |данные | |данные | |данные | +---+---+ +---+---+ +---+---+ | 0 | 0 | | 0 | 0 | | 0 | 0 | +---+---+ +---+---+ +---+---+ ↑ ↑ ↑ '----------------листья-----------------'
Существует три порядка обхода дерева: обход симметричным способом, или симметричный обход (inorder), обход в прямом порядке, прямой обход, упорядоченный обход, обход сверху, или обход в ширину (preorder) и обход в обратном порядке, обход в глубину, обратный обход, обход снизу (postorder). При симметричном обходе обрабатывается сначала левое поддерево, затем корень, а затем правое поддерево. При прямом обходе обрабатывается сначала корень, затем левое поддерево, а потом правое. При обходе снизу сначала обрабатывается левое поддерево, затем правое и, наконец корень . Об этом говорит сайт https://intellect.icu . Последовательность доступа при каждом методе обхода показана ниже:
Симметричный обход a b c d e f g Прямой обход d b a c f e g Обход снизу a c b e g f d
Несмотря на то, что дерево не должно быть обязательно упорядоченным, в большинстве задач используются именно такие деревья. Конечно, структура упорядоченного дерева зависит от способа его обхода. В оставшейся части данной главы предполагается симметричный обход. Поэтому упорядоченным двоичным деревом будет считаться такое дерево, в котором левое поддерево содержит вершины, меньшие или равные корню, а правое содержит вершины, большие корня. Приведенная ниже функция stree() создает упорядоченное двоичное дерево:
struct tree < char info; struct tree *left; struct tree *right; >; struct tree *stree( struct tree *root, struct tree *r, char info) < if(!r) < r = (struct tree *) malloc(sizeof(struct tree)); if(!r) < printf("Не хватает памяти\n"); exit(0); >r->left = NULL; r->right = NULL; r->info = info; if(!root) return r; /* первый вход */ if(info < root->info) root->left = r; else root->right = r; return r; > if(info < r->info) stree(r,r->left,info); else stree(r,r->right,info); return root; > Приведенный выше алгоритм просто следует по ссылкам дерева, переходя к левой или правой ветви очередной вершины на основании содержимого поля info до достижения места вставки нового элемента. Чтобы использовать эту функцию, необходимо иметь глобальную переменную-указатель на корень дерева. Этот указатель изначально должен иметь значение нуль ( NULL ). При первом вызове функция stree() возвращает указатель на корень дерева, который нужно присвоить глобальной переменной. При последующих вызовах функция продолжает возвращать указатель на корень. Допустим, что глобальная переменная, содержащая корень дерева, называется rt . Тогда функция stree() вызывается следующим образом:
/* вызов функции street() */ rt = street(rt, rt, info);
Функция stree() использует рекурсивный алгоритм, как и большинство процедур работы с деревьями. Точно такая же функция, основанная на итеративных методах, была бы в несколько раз длиннее. Функцию stree() необходимо вызывать со следующими параметрами (слева направо): указатель на корень всего дерева, указатель на корень следующего поддерева, в котором осуществляется поиск, и сохраняемые данные. При первом вызове оба первых параметрах указывают на корень всего дерева. Для простоты в вершинах дерева хранятся одиночные символы. Тем не менее, вместо них можно использовать любой тип данных. Чтобы обойти созданное функцией stree() дерево в симметричном порядке и распечатать поле info в каждой вершине, можно применить приведенную ниже функцию inorder() :
void inorder(struct tree *root) < if(!root) return; inorder(root->left); if(root->info) printf("%c ", root->info); inorder(root->right); > Данная рекурсивная функция завершает работу тогда, когда находит заключительный узел (нулевой указатель). В следующем листинге показаны функции, выполняющие обход дерева в ширину и в глубину.
void preorder(struct tree *root) < if(!root) return; if(root->info) printf("%c ", root->info); preorder(root->left); preorder(root->right); > void postorder(struct tree *root) < if(!root) return; postorder(root->left); postorder(root->right); if(root->info) printf("%c ", root->info); > Теперь давайте рассмотрим короткую, но интересную программу, которая строит упорядоченное двоичное дерево, а затем, обходя его симметричным образом, отображает его на экране боком. Для отображения дерева требуется лишь слегка модифицировать функцию inorder() . Поскольку на экране дерево распечатывается боком, для корректного отображения правое поддерево необходимо печатать прежде левого. (Технически это противоположность симметричного обхода.) Новая функция называется printtree() , а ее код показан ниже:
void print_tree(struct tree *r, int l) < int i; if(r == NULL) return; print_tree(r->right, l+1); for(i=0; iinfo); print_tree(r->left, l+1); >
Далее следует текст всей программы печати дерева. Попробуйте вводить различные деревья, чтобы увидеть, как они строятся.
/* Эта программа выводит на экран двоичное дерево. */ #include #include struct tree < char info; struct tree *left; struct tree *right; >; struct tree *root; /* начальная вершина дерева */ struct tree *stree(struct tree *root, struct tree *r, char info); void print_tree(struct tree *root, int l); int main(void) < char s[80]; root = NULL; /* инициализация корня дерева */ do < printf("Введите букву: "); gets(s); root = stree(root, root, *s); >while(*s); print_tree(root, 0); return 0; > struct tree *stree( struct tree *root, struct tree *r, char info) < if(!r) < r = (struct tree *) malloc(sizeof(struct tree)); if(!r) < printf("Не хватает памяти\n"); exit(0); >r->left = NULL; r->right = NULL; r->info = info; if(!root) return r; /* первый вход */ if(info < root->info) root->left = r; else root->right = r; return r; > if(info < r->info) stree(r, r->left, info); else stree(r, r->right, info); return root; > void print_tree(struct tree *r, int l) < int i; if(!r) return; print_tree(r->right, l+1); for(i=0; iinfo); print_tree(r->left, l+1); > По существу, данная программа сортирует вводимую информацию. Метод сортировки является одной из разновидностей сортировки методом вставок, которая была рассмотрена в предыдущей главе. В среднем случае производительность может быть вполне хорошей. Если вы запускали программу печати дерева, вы, вероятно, заметили, что некоторые деревья являются сбалансированными (balanced), т.е. каждое поддерево имеет примерно такую же высоту, как и остальные, а некоторые деревья очень далеки от этого состояния. Например, дерево a⇒b⇒c⇒d выглядит следующим образом:
В этом дереве нет левых поддеревьев. Такое дерево называется вырожденным, поскольку фактически оно выродилось в линейный список. В общем случае, если при построении дерева вводимые данные являются случайными, то получаемое дерево оказывается близким к сбалансированному. Если же информация предварительно отсортирована, создается вырожденное дерево. (Поэтому иногда при каждой вставке дерево корректируют так, чтобы оно было сбалансированным, но этот процесс довольно сложен и выходит за рамки данной главы.) В двоичных деревьях легко реализовываются функции поиска. Приведенная ниже функция возвращает указатель на вершину дерева, в которой информация совпадает с ключом поиска, либо нуль ( NULL ), если такой вершины нет.
struct tree *search_tree(struct tree *root, char key) < if(!root) return root; /* пустое дерево */ while(root->info != key) < if(keyinfo) root = root->left; else root = root->right; if(root == NULL) break; > return root; >
К сожалению, удалить вершину дерева не так просто, как отыскать. Удаляемая вершина может быть либо корнем, либо левой, либо правой вершиной. Помимо того, к вершине могут быть присоединены поддеревья (количество присоединенных поддеревьев может равняться 0, 1 или 2). Процесс переустановки указателей подсказывает рекурсивный алгоритм, приведенный ниже:
struct tree *dtree(struct tree *root, char key) < struct tree *p,*p2; if(!root) return root; /* вершина не найдена */ if(root->info == key) < /* удаление корня */ /* это означает пустое дерево */ if(root->left == root->right) < free(root); return NULL; >/* или если одно из поддеревьев пустое */ else if(root->left == NULL) < p = root->right; free(root); return p; > else if(root->right == NULL) < p = root->left; free(root); return p; > /* или есть оба поддерева */ else < p2 = root->right; p = root->right; while(p->left) p = p->left; p->left = root->left; free(root); return p2; > > if(root->info < key) root->right = dtree(root->right, key); else root->left = dtree(root->left, key); return root; >
Необходимо также следить за правильным обновлением указателя на корень дерева, описанного вне данной функции, поскольку удаляемая вершина может быть корнем. Лучше всего с этой целью указателю на корень присваивать значение, возвращаемое функцией dtree() :
Двоичные деревья — исключительно мощное, гибкое и эффективное средство. Поскольку при поиске в сбалансированном дереве выполняется в худшем случае log2n сравнений, оно намного лучше, чем связанный список, в котором возможен лишь последовательный поиск. Я хотел бы услышать твое мнение про двоичные деревья на е языка си Надеюсь, что теперь ты понял что такое двоичные деревья на е языка си и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Источник
Обычное двоичное дерево для тестового задания
Как-то раз я делал задание для приёма на работу после собеседования, что-то вроде тестового задания только не на дом. Был интернет и я гуглил код на языке Си и нашел какой-то код который содержал ошибки, из-за этого я не смог сделать задание на которое выделили час. Почему так случилось скажу лишь то, что по программированию у меня было все плохо по минимуму и своего кода для деревьев у меня не было и для графов тоже.
Двои́чное де́рево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Двоичное дерево не является упорядоченным ориентированным деревом. [1]
//Листинг #1 Бинарное дерево, представление #include #include using namespace std; //Наша структура struct node < int info; //Информационное поле node *l, *r; //Левая и Правая часть дерева >; node *tree = NULL; //Объявляем переменную, тип которой структура Дерево /*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/ void push(int a, node **t) < if ((*t) == NULL) //Если дерева не существует < (*t) = new node; //Выделяем память (*t)->info = a; //Кладем в выделенное место аргумент a (*t)->l = (*t)->r = NULL; //Очищаем память для следующего роста return; //Заложили семечко, выходим > //Дерево есть if (a > (*t)->info) push(a, &(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо else push(a, &(*t)->l); //Иначе кладем его влево > /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/ void print(node *t, int u) < if (t == NULL) return; //Если дерево пустое, то отображать нечего, выходим else //Иначе < print(t->l, ++u); //С помощью рекурсивного посещаем левое поддерево for (int i = 0; i < u; ++i) cout info print(t->r, ++u); //С помощью рекурсии посещаем правое поддерево > int sum(node *node_) < if (node_ == 0) return 0; return node_->info + sum(node_->l) + sum(node_->r); > int main() < int n = 16; //Количество элементов int s; //Число, передаваемое в дерево for (int i = 0; i < n; ++i) < s = -5 + rand() % 10; //Считываем элемент за элементом push(s, &tree); //И каждый кладем в дерево >cout
Данный код задает дерево и считает рекурсивно сумму его вершин. Дерево неупорядочено и не отсортировано.
Может быть мне или кому-нибудь еще пригодится данный код для устройства на работу, просто сейчас очень многие постят код который с ошибками в глуповатых статьях и сайтах.
Источник