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

@wsa · Регистрация: 20.05.2013

Студворк — интернет-сервис помощи студентам

Дано целочисленное бинарное дерево. Найти сумму значений нелистовых вершин дерева.

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;
}

создание не работает( что я делаю не так? и как найти сумму значений нелистовых вершин?

@MrCold · 27.11.2013, 06:17

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 · 27.11.2013, 06:23

Сообщение от MrCold

if(! root->left *&& ! root->right )

Сообщение от wsa

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

У Вас все наоборот

@MrCold · 27.11.2013, 06:30

Сообщение от 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 · 27.11.2013, 06:34

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 · 27.11.2013, 12:15 **[ТС]**

правильно высчитывает, но элементы в дереве могут быть любыми, а не так что в левом поддереве маленькие числа числа, а в правом -большие. И Элементы надо вводить с клавиатуры. Как я начинала писать, но к сожалению не получилось( но у меня тоже там как и вас дерево было.

@Kuzia domovenok · 27.11.2013, 12:53

C++
1
2
3
void MakeTree(Node** top){
  *top=new node;
  ...

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@wsa 0 / 0 / 0 Регистрация: 20.05.2013 Сообщений: 202
	27.11.2013, 12:15 [ТС]
	правильно высчитывает, но элементы в дереве могут быть любыми, а не так что в левом поддереве маленькие числа числа, а в правом -большие. И Элементы надо вводить с клавиатуры. Как я начинала писать, но к сожалению не получилось( но у меня тоже там как и вас дерево было. 0