Нахождение следующего и предыдущего элемента в бинарном дереве поиска - 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.