Нахождение следующего и предыдущего элемента в бинарном дереве поиска - C (СИ)
Формулировка задачи:
Нужны 2 ф-ции: нахождение следующего и предыдущего элемента в дереве.
Вот мой код. Помогите пожалуйста.
#include <stdlib.h> #include <stdio.h> #include <malloc.h> #include <conio.h> #include <locale.h> struct Ttree { int inf; Ttree *left,*right; }; struct Ttree *z,*q; FILE *f=fopen("c:\\file1.txt","r+"); FILE *h=fopen("c:\\file1.txt","r+"); //функция построения дерева void add(int x, Ttree *&tr)//х-информация, которая записывается в новый узел, tr- указатель на текущий узел дерева (вначале – на корень исходного дерева) { if (!tr)//если дерево пусто или найдено место для нового узла { tr =(Ttree*)malloc(sizeof(Ttree)); tr->inf=x; tr->left=tr->right=NULL;// сыновей нет, поэтому ссылки пустые } else if (x < tr->inf) add(x,tr->left);//если значение меньше узла, то в левое поддерево else if (x > tr->inf) add(x,tr->right);//если больше, то в правое } //функция удаления дерева void del_tree(Ttree *&tr) { if (tr) //если узел дерева не пуст { del_tree(tr->left);//обходим левое del_tree(tr->right); // обходим правое поддерево free(tr);//удаляем узел tr=NULL; } } //ф-ция печатающая дерево void print_Tree(Ttree *p,int level) { if(p) { print_Tree(p->right,level + 1); for(int i = 0;i< level;i++) printf(" "); printf("%d\n",p->inf); print_Tree(p->left,level + 1); } } //ф-ция поиска по файлу void search(int x, Ttree *tr)//x-значение которое нужно найти,tr-указатель на узел { if (!tr) printf ("NOT FOUND");//если дерево пусто else if (x < tr->inf) search(x,tr->left);//если значение меньше узла, то идём в левое поддерево else if (x > tr->inf) search(x,tr->right);//если значение больше узла, то идём в правое поддерево else printf("FOUND");//выводим на экран } //ф-ция поиска минимума void minimum(Ttree *p) { while (p->left!=NULL) p=p->left; printf("%d\n",*p); } //ф-ция поиска максимума void maximum(Ttree *p) { while (p->right!=NULL) p=p->right; printf("%d\n",*p); } //главная ф-ция int main(void) { setlocale(LC_ALL,"Russian"); int a; int x,z,*y; Ttree *tree=NULL; //инициализируем дерево while (!feof(f))//пока не конец файла { fscanf(f,"%d",&a); //считываем значения узлов add(a,tree);//добавляем его в дерево } print_Tree(tree,0);//выводим дерево на экран printf("\n\n\n\n"); printf("Введите число, которое хотите найти\n"); scanf("%d",&x); search(x, tree); printf("\n"); printf("Maximum:");maximum(tree); printf("Minimum:");minimum(tree); del_tree(tree); //удаляем дерево fcloseall(); system("pause"); return 0; }
Решение задачи: «Нахождение следующего и предыдущего элемента в бинарном дереве поиска»
textual
Листинг программы
Tree-Successor(x) { if (x.right!= NULL) return Tree-Minimum(x.right); y=x.p; while (y!=NULL&&x==y.right) { x=y; y=y.p; } return y }
Объяснение кода листинга программы
Tree-Successor(x)
- это функция, которая находит следующего элемента в бинарном дереве поиска, связанного с узломx
.- Функция проверяет, есть ли у узла
x
потомк по правой ветви. Если есть, то возвращает минимальный элемент в правой поддереве. - Если у узла
x
нет потомка по правой ветви, то функция начинает искать родителяy
узлаx
. - Пока
y
не будет равноNULL
и узелx
является правым потомком узлаy
, функция продолжает обходить родительский узелy
. - Когда
y
станетNULL
или узелx
перестанет быть правым потомком узлаy
, функция возвращает узелy
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д