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

Объяснение кода листинга программы

  1. Tree-Successor(x) - это функция, которая находит следующего элемента в бинарном дереве поиска, связанного с узлом x.
  2. Функция проверяет, есть ли у узла x потомк по правой ветви. Если есть, то возвращает минимальный элемент в правой поддереве.
  3. Если у узла x нет потомка по правой ветви, то функция начинает искать родителя y узла x.
  4. Пока y не будет равно NULL и узел x является правым потомком узла y, функция продолжает обходить родительский узел y.
  5. Когда y станет NULL или узел x перестанет быть правым потомком узла y, функция возвращает узел y.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 3.625 из 5
Похожие ответы