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

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

Восстановить пароль Регистрация
 
wsa
0 / 0 / 0
Регистрация: 20.05.2013
Сообщений: 202
26.11.2013, 21:35     Найти сумму значений нелистовых вершин дерева #1
Дано целочисленное бинарное дерево. Найти сумму значений нелистовых вершин дерева.
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;
}
создание не работает( что я делаю не так? и как найти сумму значений нелистовых вершин?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2013, 21:35     Найти сумму значений нелистовых вершин дерева
Посмотрите здесь:

C++ Удаление вершин дерева
Найти сумму четных значений функции C++
C++ Найти сумму максимальных значений элементов её строк
C++ Найти и удалить среднюю по значению из вершин дерева
Два треугольника заданы координатами своих вершин. Найти сумму длин вписанных в них окружностей. Вычисления длины окружности, вписанной в треугольник C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrCold
851 / 749 / 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();
}
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
27.11.2013, 06:23     Найти сумму значений нелистовых вершин дерева #3
Цитата Сообщение от MrCold Посмотреть сообщение
if(! root->left *&& ! root->right )
Цитата Сообщение от wsa Посмотреть сообщение
Найти сумму значений нелистовых вершин дерева.
У Вас все наоборот
MrCold
851 / 749 / 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);
  }
}
Изображения
 
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 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 );
}
wsa
0 / 0 / 0
Регистрация: 20.05.2013
Сообщений: 202
27.11.2013, 12:15  [ТС]     Найти сумму значений нелистовых вершин дерева #6
правильно высчитывает, но элементы в дереве могут быть любыми, а не так что в левом поддереве маленькие числа числа, а в правом -большие. И Элементы надо вводить с клавиатуры. Как я начинала писать, но к сожалению не получилось( но у меня тоже там как и вас дерево было.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2013, 12:53     Найти сумму значений нелистовых вершин дерева
Еще ссылки по теме:

C++ Обмен информации правых вершин одного бинарного дерева на информацию левых вершин другого
Написать рекурсивную процедуру, которая печатает ключи всех вершин двоичного дерева C++
C++ Вершины дерева вещественные числа. Описать процедуру, которая вычисляет среднее арифметическое всех вершин

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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
27.11.2013, 12:53     Найти сумму значений нелистовых вершин дерева #7
C++
1
2
3
void MakeTree(Node** top){
  *top=new node;
  ...
Yandex
Объявления
27.11.2013, 12:53     Найти сумму значений нелистовых вершин дерева
Ответ Создать тему
Опции темы

Текущее время: 03:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru