Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Polina B
2 / 2 / 0
Регистрация: 08.02.2015
Сообщений: 146
1

Бинарное дерево поиска

21.06.2018, 12:23. Просмотров 1206. Ответов 1
Метки нет (Все метки)

Здравствуйте! Дали такое задание. И нужно вместо троеточий вставить несколько строчек. Как я поняла после public List<int> leftRoad () я должна написать код левосторонний обход дерева, а вот что писать после while (oN != null) не могу понять.
Спроектировать класс BinTree.
Описание алгоритмов.
Метод insert(int V).
Условия добавления листа дерева.
Начиная с корня дерева для каждого узла дерева:
• Если значения R узла равно значению V входной величины, то ничего не делать, выход;
• Если R>V, то добавить V в левое поддерево, выход;
• Если R<V, то добавить V в правое поддерево, выход;
Метод левостороннего обхода дерева List<int> leftRoad().
• Обработать левое поддерево.
• Записать значение корня дерева в список
• Обработать правое поддерево;

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Program{
    interface IBT
    {
        void insert(int t);
        List<int> leftRoad ();
    }
    class BinTree:IBT
    {
      bool Root;
      BinTree left, right;
      int item;
      //public int? Pitem { get{return item;} private set{item=(int)value;} }
      public BinTree() { left = right = null; Root = false;  }
      public BinTree(int Item)
      {
        left = right = null;
        Root = true;
        item = Item;
      }
public void insert(int t)
      {
        if (!Root) { Root = true; item=t; return; }
        BinTree oN = this;
        while (oN != null)
 . . .  }
 static List<int> oL = new List<int>();
      public List<int> leftRoad ()
      {
          . . .
        return oL;
      }
}
static void Main(string[] args)
    {
        StreamReader R = new StreamReader("in.txt");
        StreamWriter W = new StreamWriter("out.txt");
      BinTree bt=new BinTree();    
      int[] A;// ={ 31, 17, 12, 22, 18, 21 };
        string [] As;
        As=R.ReadLine().Split(',');
        A=new int[As.Length];
        for (int i = 0; i < As.Length; i++)
            A[i] = Convert.ToInt32(As[i]);
            foreach (int t in A)
                bt.insert(t);
      List<int> L;
      L = bt.leftRoad ();
      foreach (int t in L)
          W.Write(" " + t);
      W.WriteLine();
      R.Close();
      W.Close();
    }
  }
Пример исполнения программы.
in.txt
31, 17, 12, 22, 18, 21
out.txt
12 17 18 21 22 31
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2018, 12:23
Ответы с готовыми решениями:

Бинарное дерево поиска. Разработать функцию удаления
Здравствуйте! Помогите пожалуйста! Имеется связной список, который содержит целые числа. Нужно...

Функция поиска с включением узла в бинарное дерево
Здравствуйте! Помогите, пожалуйста, написать функцию поиска с включением узла в бинарное дерево....

Построить бинарное дерево поиска из букв строки, вводимой пользователем
Не совсем понимаю как сделать данное задание, так и в плане реализации, помогите: &quot;Построить...

Бинарное дерево поиска. Как осуществить запись в файл и чтение из файла
Добрый день! Если кому не жаль своего времени окажите помощь! Необходимо осуществить запись в...

Как заполнить бинарное дерево чтобы оно не было деревом поиска?
Здесь я хочу сделать так чтобы число в зависимости от случайного temp отправлялось налево или...

1
Dkomik
1 / 1 / 2
Регистрация: 19.06.2018
Сообщений: 29
21.06.2018, 14:23 2
Лучший ответ Сообщение было отмечено Polina B как решение

Решение

Тут для Сишников а не для Сишарпников раздел.
Если это с CodeForces то возьмите GNU GCC.
Но вот код(на си):
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <stdio.h>
#include <stdlib.h>
 
void quick(int *num,int left,int right){
int truey;
int l1=left;
int r1=right;
truey=num[left];
 
while(left<right)
{
 while((num[right]>=truey)&&(left<right))
right--;
if(left !=right)
{
    num[left]=num[right];
    left++;
}
while((num[left]<=truey)&&(left<right))
    left++;
if(left!=right){
    num[right]=num[left];
    right--;
}
 
}
num[left]=truey;
truey=left;
left=l1;
right=r1;
if(left<truey)
    quick(num,left,truey-1);
if(right>truey)
    quick(num,truey+1,right);
}
int main()
{
int a[6];
a[0]=31;
a[1]=17;
a[2]=12;
a[3]=22;
a[4]=18;
a[5]=21;
 
quick(a,0,5);
for(int i=0;i<6;i++){
    printf("%d ",a[i]);
 
}
    return 0;
}
Добавлено через 2 минуты
Цитата Сообщение от Polina B Посмотреть сообщение

Пример исполнения программы.
in.txt
31, 17, 12, 22, 18, 21
out.txt
12 17 18 21 22 31
Можно и без in.txt и out.txt
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2018, 14:23

Построить идеально сбалансированное бинарное дерево поиска и обеспечить поиск указанных записей
Вообщем написал программу и не уверен, что правильно работает балансировка( При нечетном...

Бинарное дерево
Здравствуйте.Учусь в техникуме,начали изучать СИ(Обычный СИ.Со следующей недели начнем учить...

Бинарное дерево не создается
здраствуйте я написал функцию создания и записи в дерево но она не работает. ptree Form() {...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.