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

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

Войти
Регистрация
Восстановить пароль
 
wsa
0 / 0 / 0
Регистрация: 20.05.2013
Сообщений: 202
#1

Найти сумму значений нелистовых вершин дерева - C++

26.11.2013, 21:35. Просмотров 714. Ответов 6
Метки нет (Все метки)

Дано целочисленное бинарное дерево. Найти сумму значений нелистовых вершин дерева.
C++ (Qt)
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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <iomanip>
#include <math.h>
 
using namespace std;
 
struct Node
{
    int d; // элементы дерева
    Node *l,*r;//левай и правая части дерева
};
 
//создание дерева
void MakeSubTrees(Node *leaf)
{
    Node *Top;
    int Key; 
    cout << "Введите текущий узел:" <<endl;
    cin >> leaf -> d;
    cout << leaf -> d << "Имеет левое поддерево?" <<endl;
    cin >> Key;
    if (Key == 1)
    {
        (Top) = new Node;
        leaf -> l = Top;
        MakeSubTrees(Top);
    }
    else
    {
        leaf -> l = NULL;
        cout << leaf -> d << "Имеет правое поддерево?" <<endl;
        cin >> Key;
    }
    if (Key == 1)
    {
        (Top) = new Node;
        leaf -> l = Top;
        MakeSubTrees(Top);
    }
    else 
    {
        leaf -> r = NULL;
    }
 
void MakeTree(Node *Top)
    {
        (Top) = new Node;
        MakeSubTrees(Top);
    }
 
void ViewTree(Node *Top)
{
    int level;
    if (Top)
    {
        ViewTree(Top->l, level+1);
        for (int i=0; i<level;i++)
            cout<<"   ";
        cout<< Top->d <<endl;
        ViewTree(Top->r,level+1);
    }
}
 
 
 
void main()
{
    setlocale(LC_CTYPE, "Russian");
    Node *Top;
    MakeTree(&Top);
    ViewTree(Top,0);
    getch();
    return;
}
создание не работает( что я делаю не так? и как найти сумму значений нелистовых вершин?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2013, 21:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти сумму значений нелистовых вершин дерева (C++):

Найти и удалить среднюю по значению из вершин дерева - C++
Здравствуйте, Я студент 1-ого курса, нужно помощь с написанием кода к этой программе. Задача 25 Условие Найти и удалить...

Обмен информации правых вершин одного бинарного дерева на информацию левых вершин другого - C++
Помогите пожалуйста с задачей Написать программу обмена информации правых вершин одного бинарного дерева на информацию левых вершин...

Найти количество вершин дерева, значения которых равны значению корня - C++
Дано целочисленное бинарное дерево. Найти: 1) количество вершин дерева, значения которых равны значению корня. С комментариями в коде,...

Удаление вершин дерева - C++
Здравствуйте! Помогите в решении задачи. Записи вершин 2-3–дерева – вещественные числа. Описать процедуру, которая удаляет все вершины со...

Найти максимальную сумму элементов на ярусе дерева - C++
Найти максимальную сумму элементов на ярусе дерева

Подсчет количества вершин дерева - C++
Добрый вечер. Возникла проблема в коде, не знаю как &quot;соединить код&quot; всей программы + самого подсчета количества вершин дерева, чтобы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MrCold
855 / 753 / 71
Регистрация: 11.01.2012
Сообщений: 1,942
27.11.2013, 06:17 #2
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
#include <iostream>
 
struct Node
{
    int data;
    Node* left;
    Node* right;
};
 
void Add(int newData,  Node *& root)
{
    if(! root )
    {
        root = new Node();
        root->data = newData;
        
        root->left = NULL;    
        root->right = NULL;  
    }
    else if(newData < root->data)
    {
        Add( newData, root->left );
    }
    else if(newData > root->data)
    {
        Add( newData, root->right );
    }
}
// в симметричном порядке
void Inorder(const Node  * root)
{
  if(root)   
  {  
      Inorder(root->left);
         std::cout << root->data << std::endl;
      Inorder(root->right);
  }
}
 
void GetSum (const Node * root, int &sum)
{
  if(root != NULL)   
  {   
      GetSum(root->left,sum);
      if(! root->left  && ! root->right )
      {
          sum += root->data;
      }
      GetSum(root->right,sum);
  }
}
 
int main()
{
    Node* Root = NULL;
    int sum = 0;
 
        Add( 5, Root);
        Add( 8, Root);
        Add( 6, Root);
        Add( 11, Root);
        Add( 18, Root);
        Add( 14, Root);
        Add( 10, Root);
 
        Inorder(Root);  
        GetSum (Root,sum);
        std::cout << "\nSum : " << sum << std::endl;
 
    std::cin.get();
    std::cin.get();
}
0
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
27.11.2013, 06:23 #3
Цитата Сообщение от MrCold Посмотреть сообщение
if(! root->left *&& ! root->right )
Цитата Сообщение от wsa Посмотреть сообщение
Найти сумму значений нелистовых вершин дерева.
У Вас все наоборот
0
MrCold
855 / 753 / 71
Регистрация: 11.01.2012
Сообщений: 1,942
27.11.2013, 06:30 #4
Цитата Сообщение от Toshkarik Посмотреть сообщение
У Вас все наоборот
Посчитайте по картинке . По моему все верно

В функцию вывод нелистовых вершин добавил
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void GetSum (const Node * root, int &sum)
{
  if(root != NULL)   
  {   
      GetSum(root->left,sum);
      if(! root->left  && ! root->right )
      {
          std::cout << root->data << std::endl;
          sum += root->data;
      }
      GetSum(root->right,sum);
  }
}
0
Изображения
 
Toshkarik
1141 / 858 / 51
Регистрация: 03.08.2011
Сообщений: 2,384
Завершенные тесты: 1
27.11.2013, 06:34 #5
MrCold, лист это узел, который не имеет ни правого ни левого потомков. Вы их и скалдываете. А по заданию нужно же делать наоборот, складывать НЕлистовые элементы, то есть условие должно быть вроде такого:
C++
1
2
3
4
5
if ( root && ( root->left || root->right )) {
   sum += root->data;
   GetSum( root->left, sum );
   GetSum( root->right, sum );
}
0
wsa
0 / 0 / 0
Регистрация: 20.05.2013
Сообщений: 202
27.11.2013, 12:15  [ТС] #6
правильно высчитывает, но элементы в дереве могут быть любыми, а не так что в левом поддереве маленькие числа числа, а в правом -большие. И Элементы надо вводить с клавиатуры. Как я начинала писать, но к сожалению не получилось( но у меня тоже там как и вас дерево было.
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
27.11.2013, 12:53 #7
C++
1
2
3
void MakeTree(Node** top){
  *top=new node;
  ...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2013, 12:53
Привет! Вот еще темы с ответами:

Подсчет количества вершин дерева на заданном уровне - C++
Напишите пожалуйста Проги для нахождения количества вершин для дерева на заданном уровне, и кто сможет помогите посчитать сложность...

Вывести количество вершин дерева, являющихся левыми дочерними вершинами - C++
Дан указатель P на корень непустого дерева. Вывести количество вершин дерева, являющихся левыми дочерними вершинами(корень дерева не...

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

Написать рекурсивную процедуру, которая печатает ключи всех вершин двоичного дерева - C++
Необходимо написать рекурсивную процедуру, которая печатает ключи всех вершин двоичного дерева. Двоичное дерево задастся в файле в...


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

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

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