0 / 0 / 0
Регистрация: 20.05.2013
Сообщений: 202
1

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

26.11.2013, 21:35. Показов 2375. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.11.2013, 21:35
Ответы с готовыми решениями:

Найти сумму значений узлов бинарного дерева, находящихся на нечетных уровнях
Помогите, пожалуйста с задачкой. :sorry: Найти сумму значений узлов бинарного дерева, находящихся...

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

Найти среднее геометрическое положительных вершин дерева
Найти среднее геометрическое положительных вершин дерева.

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

6
871 / 769 / 173
Регистрация: 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
1179 / 892 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
27.11.2013, 06:23 3
Цитата Сообщение от MrCold Посмотреть сообщение
if(! root->left *&& ! root->right )
Цитата Сообщение от wsa Посмотреть сообщение
Найти сумму значений нелистовых вершин дерева.
У Вас все наоборот
0
871 / 769 / 173
Регистрация: 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
1179 / 892 / 94
Регистрация: 03.08.2011
Сообщений: 2,461
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
0 / 0 / 0
Регистрация: 20.05.2013
Сообщений: 202
27.11.2013, 12:15  [ТС] 6
правильно высчитывает, но элементы в дереве могут быть любыми, а не так что в левом поддереве маленькие числа числа, а в правом -большие. И Элементы надо вводить с клавиатуры. Как я начинала писать, но к сожалению не получилось( но у меня тоже там как и вас дерево было.
0
3658 / 2995 / 828
Регистрация: 25.03.2012
Сообщений: 11,036
Записей в блоге: 1
27.11.2013, 12:53 7
C++
1
2
3
void MakeTree(Node** top){
  *top=new node;
  ...
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.11.2013, 12:53
Помогаю со студенческими работами здесь

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

Turbo Prolog: подсчитать сумму всех вершин данного дерева, значения которых принадлежат заданному диапазону
Помогите,пожалуйста,кто в этом разбирается. Нужно создать предикат,подсчитывающий сумму всех вершин...

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru