Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Toda
10 / 10 / 0
Регистрация: 16.11.2012
Сообщений: 320
#1

Дерево. Готовая программа на 95% - C++

16.11.2013, 03:00. Просмотров 645. Ответов 7
Метки нет (Все метки)

Вот само дерево.
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <conio.h>
using namespace std;
int todor=0;
struct Node 
{
   int x; //То, что записываем в дерево
   Node *l,*r;
};
void show(Node *&Tree) //Функция обхода
{
    if (Tree!=NULL)
    {
       show(Tree->l); //Рекурсивная функция для вывода левого поддерева
       cout<<Tree->x;//Отображаем корень дерева
       cout << "  ";
       show(Tree->r); //Рекурсивная функци для вывода правого поддерева
    }
}
 
Node* add_node(int x,Node *&MyTree) //Фукция добавления звена в дерево
{
    if (!MyTree)
    {
        MyTree= new Node;
        MyTree->x=x;
        MyTree->l=0;MyTree->r=0;
    }
    else
        if(x<MyTree->x)
            MyTree->l=add_node(x,MyTree->l);
        else
            MyTree->r=add_node(x,MyTree->r);
    return MyTree;
 
}
int DeleteTree(Node *Tree)
{
     if (Tree==NULL)
         return 0;
     else
     {
           DeleteTree(Tree->l);
           DeleteTree(Tree->r);
           delete Tree;
           Tree = NULL;
     }
}
int main()
{
  Node *Tree=NULL;  
  int k,e,z;
  cout << "Vvedite kolichestvo elementov v dereve\n";
  cin >> z;
  cout << "Vvedite elementi dereva\n";
      for (int i=0;i<z;i++) 
      {
          cin >> k;
          add_node(k,Tree);
      }
      cout << "Vvedite kluch\n";
      cin >> e;
      cout << "Derevo:\n";
      show(Tree);
      DeleteTree(Tree);
      getch();
   return 0;
}
Нужно дописать функцию, которая определяет количество узлов в дереве, у которых есть только один потомок. Не знаю как(
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.11.2013, 03:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дерево. Готовая программа на 95% (C++):

Готовая программа переделайте на Указатели - C++
Помогите пожалуйста!!! Через указатели #include &lt;stdio.h&gt; #include &lt;conio.h&gt; int main( ) { int n = 3; int** f1=new int*; ...

Нужна готовая программа на Си++ с уклоном на физику - C++
=) дорогие программисты помогите студенту ) нужна готовая программа на Си++ ) очень хорошо если в ней был уклон на физику ( например...

Готовая программа для любой работы с массивом - C++
Вот я решил помочь всем кому надо! Вот. Оцените работу! И вот код!

Готовая программа, нужно переделать ее чтобы она работала с УКАЗАТЕЛЯМИ - C++
Вычислить значение выражения тут Вычислить значение выражения (3a+4)/(a-в квадрате-5a-9) для а= 1,2,…100. Результат выполнения занести в...

Готовая программа, но надо подгрузить через функция( открыв файл) - C++
Добрый вечер!) Подскажите, есть программа с оператором case, вот при выборе case 1: выполняется определенное решение. Нужно изменить, чтобы...

Почти готовая программа с матрицами, не могу загрузить матрицу из файла - C++
Косяк в функции на 32 строке. Собственно мне нужно узнать сколько символов записано в файл, чтобы затем загрузить одномерную матрицу и...

7
Peregrin
33 / 33 / 1
Регистрация: 16.11.2012
Сообщений: 59
16.11.2013, 04:58 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isLeaf(Node* root) {
 return (root->l == null && root->r == null);
}
 
int countOfNodesWithOneChild(Node* root) {
 if (root != null)
  if ((root->l != null && root->r == null && isLeaf(root->l)           //если справа нет потомков, а слева потомок-лист
     || (root->r != null && root->l == null && isLeaf(root->r))       //или слева нет потомков, а справа потомок-лист
   return 1;
  else
   return countOfNodesWithOneChild(root->l) + countOfNodesWithOneChild(root->r);
 else
  return 0;
}
0
Toda
10 / 10 / 0
Регистрация: 16.11.2012
Сообщений: 320
16.11.2013, 14:35  [ТС] #3
Peregrin, а можете, пожалуйста, весь код программы скинуть, а не только функции?)
0
Peregrin
33 / 33 / 1
Регистрация: 16.11.2012
Сообщений: 59
16.11.2013, 20:05 #4
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <conio.h>
using namespace std;
int todor=0;
struct Node 
{
   int x; //То, что записываем в дерево
   Node *l,*r;
};
void show(Node *&Tree) //Функция обхода
{
    if (Tree!=NULL)
    {
       show(Tree->l); //Рекурсивная функция для вывода левого поддерева
       cout<<Tree->x;//Отображаем корень дерева
       cout << "  ";
       show(Tree->r); //Рекурсивная функци для вывода правого поддерева
    }
}
 
Node* add_node(int x,Node *&MyTree) //Фукция добавления звена в дерево
{
    if (!MyTree)
    {
        MyTree= new Node;
        MyTree->x=x;
        MyTree->l=0;MyTree->r=0;
    }
    else
        if(x<MyTree->x)
            MyTree->l=add_node(x,MyTree->l);
        else
            MyTree->r=add_node(x,MyTree->r);
    return MyTree;
 
}
int DeleteTree(Node *Tree)
{
     if (Tree==NULL)
         return 0;
     else
     {
           DeleteTree(Tree->l);
           DeleteTree(Tree->r);
           delete Tree;
           Tree = NULL;
     }
}
 
bool isLeaf(Node* root) {
 return (root->l == null && root->r == null);
}
 
int countOfNodesWithOneChild(Node* root) {
 if (root != null)
  if ((root->l != null && root->r == null && isLeaf(root->l)           //если справа нет потомков, а слева потомок-лист
     || (root->r != null && root->l == null && isLeaf(root->r))       //или слева нет потомков, а справа потомок-лист
   return 1;
  else
   return countOfNodesWithOneChild(root->l) + countOfNodesWithOneChild(root->r);
 else
  return 0;
}
 
int main()
{
  Node *Tree=NULL;  
  int k,e,z;
  cout << "Vvedite kolichestvo elementov v dereve\n";
  cin >> z;
  cout << "Vvedite elementi dereva\n";
      for (int i=0;i<z;i++) 
      {
          cin >> k;
          add_node(k,Tree);
      }
      cout << "Vvedite kluch\n";
      cin >> e;
      cout << "Derevo:\n";
      show(Tree);
      cout << "Kolichestvo elementov s odnim potomkom: " << countOfNodesWithOneChild(Tree) << '\n';
      DeleteTree(Tree);
      getch();
   return 0;
}
я не тестил, но вроде должно работать)
1
Toda
10 / 10 / 0
Регистрация: 16.11.2012
Сообщений: 320
17.11.2013, 22:58  [ТС] #5
Peregrin, работает, спасибо. А как ее можно протестить?) Не особо понимаю принцип работы проги и не уверен, что она правильно работает.
0
Миниатюры
Дерево. Готовая программа на 95%  
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
17.11.2013, 23:06 #6
Toda, так она работает также как твоя прога! Такой же рекурсивный обход с немного другим условием! Ты ж обход дерева только что сам написал!
0
Toda
10 / 10 / 0
Регистрация: 16.11.2012
Сообщений: 320
18.11.2013, 01:13  [ТС] #7
Kuzia domovenok, всмысле только что? Я ничего только что не писал. Скинул код дерева в первом посте и все. А почему она сортирует числа?

Добавлено через 1 час 51 минуту
Хелп

Добавлено через 15 секунд
Хелп
0
Peregrin
33 / 33 / 1
Регистрация: 16.11.2012
Сообщений: 59
18.11.2013, 02:31 #8
Toda, у тебя обычное дерево поиска, ты при вставке элемента встаешь на корень и смотришь - если элемент меньше корня, то кидаешь его налево, иначе кидаешь направо. Нарисуй на бумажке лучше, так намного понятнее будет. И сортировка у тебя происходит из-за обхода LCR. Почитай вики, там всё понятно описано: http://ru.wikipedia.org/wiki/%D0%94%...81%D0%BA%D0%B0
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.11.2013, 02:31
Привет! Вот еще темы с ответами:

Программа на Бинарное дерево - C++
Есть несколько задачек на данную тему, вот что-то пока, что никак не могу разобраться. У кого есть возможность напишите, чтоб по реальному...

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Дано дерево. Распечатать дерево по уровням - C++
Дано дерево. Распечатать дерево по уровням.

Готовая программа - C#
Здравствуйте!Как в ms visual studio 2010 сделать свой проект (написан на winforms) окончательной готовой программой, чтобы программа на...


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
18.11.2013, 02:31
Ответ Создать тему
Опции темы

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