Нужна помощь с изучением бинарного дерева поиска псевдокода - PullRequest
Новая
       27

Нужна помощь с изучением бинарного дерева поиска псевдокода

0 голосов
/ 03 апреля 2011

Я учусь на среднесрочный период.Может ли кто-нибудь помочь мне начать этот вопрос из моего учебника?

Напишите функцию для распечатки всех элементов двоичного дерева поиска со значением v, чтобы min_val ≤ v ≤ max_val.

Youможет начинаться со следующего прототипа: template void BSTree :: PrintRange (const Comparable & min_val, const Comparable & max_val) const;

Анализ времени выполнения вашей функции с точки зрения количества узлов n и числаэлементов k в диапазоне, используя обозначение O (Big-Oh).

Большое спасибо.

1 Ответ

0 голосов
/ 03 апреля 2011

Вы можете сделать это с помощью простой двойной рекурсии. 

BSTree::PrintRange( const Comparable & min_val, const Comparable & max_val ) const
{
  if(min_val<=v && v<=max_value)
  {
     print(v);
     if(left!=NULL)
        left.PrintRange(min_val,max_val);
     if(right!=NULL)   
        right.PrintRange(min_val,max_val);
  }
  else if(v<min_val) //go to the right to find a bigger value 
  {
     if(right!=NULL)
       right.PrintRange(min_val,max_val);
  }
  else //v>max_val
  { //go to the left to find a smaller value
     if(left != NULL)
       left.PrintRange(min_val,max_val);
  }

}
...