Форум программистов, компьютерный форум, киберфорум
Java для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 29
1

Рекурсия: подсчитать сумму элементов бинарного дерева

24.03.2019, 16:51. Просмотров 1675. Ответов 7
Метки нет (Все метки)

Написать программу, которая создает сбалансированное бинарное дерево. Написать рекурсивную функцию, подсчитывает сумму элементов дерева.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
24.03.2019, 16:51
Ответы с готовыми решениями:

Рекурсия: подсчет суммы элементов бинарного дерева
Создать бинарное дерево. Написать рекурсивную числовую функцию, которая подсчитывает суму элементов...

Подсчитать количество элементов на n-м уровне бинарного дерева
Помогите пожалуйста написать рекурсивную функцию или процедуру, которая подсчитывает количество...

Рекурсия и обход бинарного дерева
Уже есть бинарное дерево. Надо вывести в консоль ключи в порядке возрастания. Методом тыка...

Рекурсия при заполнении бинарного дерева
Есть список с элементами, которые заносятся в дерево по прямому ходу. struct tree...

7
742 / 489 / 285
Регистрация: 10.09.2015
Сообщений: 1,530
24.03.2019, 19:46 2
Java
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
 
public class BinaryTree implements Iterable<Integer> {
    private Node root;
    private int size;
 
    public BinaryTree(int... values) {
        addAll(values);
    }
 
    public BinaryTree() {
    }
 
    public int size() {
        return this.size;
    }
 
    public boolean isEmpty() {
        return this.size == 0;
    }
 
    public boolean add(int value) {
        boolean result;
        if (result = size == 0) {
            root = new Node(value);
            this.size++;
        } else {
            Node node = getLinkPlaceWrite(value);
            if (result = node != null) {
                node.value = value;
                this.size++;
            }
        }
        return result;
    }
 
    public void addAll(int... values) {
        if (values != null && values.length > 0) {
            for (int value : values) {
                add(value);
            }
        }
    }
 
    private Node getLinkPlaceWrite(int value) {
        Node result = root;
        while (result != null && result.value != null) {
            int intRes = result.value.compareTo(value);
            if (intRes > 0) {
                result = result.left = result.left == null ? new Node(null) : result.left;
            } else if (intRes < 0) {
                result = result.right = result.right == null ? new Node(null) : result.right;
            } else {
                result = null;
            }
        }
        return result;
    }
 
    public int getSumElements() {
        return getSumElementsRecurse(this.root, 0);
    }
 
    private int getSumElementsRecurse(Node head, int result) {
        if (head != null) {
            result = getSumElementsRecurse(head.left, result) + head.value + getSumElementsRecurse(head.right, result);
        }
        return result;
    }
 
    private List<Integer> getListElements(Node head, List<Integer> list) {
        if (head != null) {
            list = getListElements(head.left, list);
            list.add(head.value);
            list = getListElements(head.right, list);
        }
        return list;
    }
 
    public int[] toArray() {
        List<Integer> list = getListElements(root, new ArrayList<>());
        int[] array = new int[list.size()];
        int index = 0;
        for (int number : list) {
            array[index] = number;
        }
        return array;
    }
 
    @Override
    public String toString() {
        return getListElements(root, new ArrayList<>()).toString();
    }
 
    @Override
    public Iterator<Integer> iterator() {
        return getListElements(root, new ArrayList<>()).iterator();
    }
 
    private class Node {
        private Integer value;
        private Node left;
        private Node right;
 
        Node(Integer value) {
            this.value = value;
        }
    }
}
 
class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree(1, 2, 3, 4, 5);
        System.out.println(tree);
        tree.addAll(1, 3, 5, 7, 0);
        System.out.println(tree);
        System.out.println("Sum tree: " + tree.getSumElements());
    }
}
0
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 29
07.04.2019, 13:03  [ТС] 3
хочу сдеать ввод с клавиатуры, но при вводе "1,2,3", оно сразу дает следующую строку как "49,50,51"
Java
1
2
3
4
5
6
7
8
9
10
11
class BinaryTreeTest {
public static void main(String[] args) {
    System.out.println("Input: ");
    Scanner scan = new Scanner (System.in);
    String string = new String();
    string = scan.nextLine();
    BinaryTree tree = new BinaryTree ();
    for(int i=0;i<string.length();i++) {
        tree.addAll(string.charAt(i)); }
    System.out.println(tree);
    System.out.println("Sum tree: " + tree.getSumElements()); }}
не подскажите где ошибка?
0
742 / 489 / 285
Регистрация: 10.09.2015
Сообщений: 1,530
07.04.2019, 13:20 4
зачем ты в бинарное дерево, которое типа Integer, добавляешь char?

Java
1
2
3
4
5
6
7
8
9
System.out.println("Input: ");
    Scanner scan = new Scanner (System.in);
    BinaryTree tree = new BinaryTree ();
    for(int i = 0; i < 10; i++) {
        System.out.print("Введите число #" + (i + 1) + ": ");
        tree.add(scan.nextInt()); 
    }
    System.out.println(tree);
    System.out.println("Sum tree: " + tree.getSumElements()); }}
0
Модератор
Эксперт Python
27023 / 14188 / 2738
Регистрация: 12.02.2012
Сообщений: 23,274
Записей в блоге: 3
09.04.2019, 08:23 5
ArtemFM, код мне кажется великоват для простого дерева и маловат для сбалансированного... Ваше дерево балансируется?
0
Aviz__
09.04.2019, 09:02
  #6

Не по теме:

Цитата Сообщение от Catstail Посмотреть сообщение
великоват для простого дерева и маловат для сбалансированного
это он скрыто "учит" студентов жизни...

0
742 / 489 / 285
Регистрация: 10.09.2015
Сообщений: 1,530
09.04.2019, 11:15 7
Catstail, дерево, как Вы и сами видите, совсем не сбалансированное, но не думаю, что много кода для обычного. В пределах нормы )
0
Модератор
Эксперт Python
27023 / 14188 / 2738
Регистрация: 12.02.2012
Сообщений: 23,274
Записей в блоге: 3
10.04.2019, 13:03 8
Как вариант:

Java
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
class Node {
    public int Value;
    public Node Left;
    public Node Right;
    public Node(int v)
    {
        Value=v;
    }
}
class Tree {
    
    public Node root;
 
    public void add(Node r,int val)
    {   Node n;
        
        if (r.Value < val) 
        {
            if (r.Right==null)
            {
               n=new Node(val);
               r.Right=n;
            }
            else
            {
                add(r.Right,val);
            }
        }
        else
        {
            if (r.Left==null)
            {
               n=new Node(val);
               r.Left=n;
            }
            else
            {
                add(r.Left,val);
            }
        }
        
    }
    
    public void arrToTree(int[] Arr)
    {
        int i;
        root=new Node(Arr[0]);
        for (i=1; i<Arr.length; i++)
        {
            add(root,Arr[i]);
        }
    }
    
    public void printTree(Node r)
    {
        if (r==null) return;
        printTree(r.Left);
        System.out.print(r.Value+" ");
        printTree(r.Right);
    }
 
    public int sumTree(Node r)
    {
        if (r==null) return 0;
        return sumTree(r.Left)+r.Value+sumTree(r.Right);
    }
    
}
 
public class Main
{
    public static void main(String[] args) {
        Tree t1=new Tree();
        int X[] = {1,4,-6,9,1,3,7,4,12,-8};
        t1.arrToTree(X);
        t1.printTree(t1.root);
        System.out.println();
        System.out.println("sum="+t1.sumTree(t1.root));
    }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.04.2019, 13:03

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Подсчитать средний вес ветвей заданного бинарного дерева
Будем называть весом ветви сумму значений всех вершин этой ветви. Требуется подсчитать средний вес...

Homelisp: подсчитать количество вершин бинарного дерева, значение которых меньше заданного N
Дано бинарное дерево содержащее целые числа. Подсчитать количество вершин дерева, значение которого...

Удаление элементов из бинарного дерева
Доброго времени суток! Реализую обычное бинарное дерево (НЕ поиска) на базе массива (то еще...

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


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

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

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