Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/27: Рейтинг темы: голосов - 27, средняя оценка - 4.67
1 / 1 / 0
Регистрация: 21.04.2012
Сообщений: 38
1

Бинарное дерево: как происходит добавления элемента в дерево с двумя параметрами

07.05.2012, 09:37. Просмотров 5613. Ответов 7
Метки нет (Все метки)

Здравствуйте! Прошу помощи у опытных программистов...))))
Есть класс дерево:

C#
1
2
3
4
5
6
7
8
9
10
11
12
 class class1
    {
        public class Tree
        {
            public int dkod;
            public char dcim;
            public Tree left;
            public Tree right;
 
        }
     
    }
Как происходит добавления элемента в дерево с двумя параметрами?
Как читать из дерева?

Заранее спасибо!)))

Добавлено через 17 часов 45 минут
И как создать его обход?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.05.2012, 09:37
Ответы с готовыми решениями:

Добавления элемента в бинарное дерево
Уже создавал подобную тему , но так и не получилось разобраться до конца . Есть такая задача :...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при...

Принцип добавления слов в бинарное дерево
Доброго времени суток! Я хотел бы узнать по какому принципу добавлять слова в бинарное дерево. Если...

Бинарное дерево. Реализация добавления элементов в цикле
Всем привет! Подскажите, пожалуйста, хочу написать программку для создания дерева так, чтобы...

7
Злой няш
1523 / 1187 / 407
Регистрация: 05.04.2010
Сообщений: 2,081
07.05.2012, 10:24 2
Цитата Сообщение от DarkOFF Посмотреть сообщение
в дерево с двумя параметрами
Это кто такой?
Есть здесь у меня некоторая реализация
двоичного дерева
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
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
public class BinaryTree<T> : IEnumerable<T> where T : IComparable<T>
{
        class Node<TValue>
        {
                public TValue Value { get; set; }
                public Node<TValue> Left { get; set; }
                public Node<TValue> Right { get; set; }
 
                public Node(TValue value)
                {
                        Value = value;
                }
        }
 
        private Node<T> root;
 
        public BinaryTree() { }
        public BinaryTree(IEnumerable<T> collection)
        {
                AddRange(collection);
        }
 
        public int Count { get; private set; }
        public T Min
        {
                get
                {
                        if (root == null) throw new InvalidOperationException("Tree is empty");
                        var current = root;
                        while (current.Left != null)
                                current = current.Left;
                        return current.Value;
                }
        }
        public T Max
        {
                get
                {
                        if (root == null) throw new InvalidOperationException("Tree is empty");
                        var current = root;
                        while (current.Right != null)
                                current = current.Right;
                        return current.Value;
                }
        }
 
        public void Add(T value)
        {
                if (value == null) throw new ArgumentNullException("value");
 
                var node = new Node<T>(value);
 
                if (root == null)
                        root = node;
                else {
                        Node<T> current = root, parent = null;
 
                        while (current != null) {
                                parent = current;
                                if (value.CompareTo(current.Value) < 0) current = current.Left;
                                else current = current.Right;
                        }
 
                        if (value.CompareTo(parent.Value) < 0) parent.Left = node;
                        else parent.Right = node;
                }
                ++Count;
        }
        public void AddRange(IEnumerable<T> collection)
        {
                foreach (var value in collection)
                        Add(value);
        }
        public void Remove(T value)
        {
                if (value == null) throw new ArgumentNullException("value");
                if (root == null) return;
 
                Node<T> current = root, parent = null;
 
                int result;
                do {
                        result = value.CompareTo(current.Value);
                        if (result < 0) { parent = current; current = current.Left; }
                        else if (result > 0) { parent = current; current = current.Right; }
                        if (current == null) return;
                }
                while (result != 0);
 
                if (current.Right == null) {
                        if (current == root) root = current.Left;
                        else {
                                result = current.Value.CompareTo(parent.Value);
                                if (result < 0) parent.Left = current.Left;
                                else parent.Right = current.Left;
                        }
                }
                else if (current.Right.Left == null) {
                        current.Right.Left = current.Left;
                        if (current == root) root = current.Right;
                        else {
                                result = current.Value.CompareTo(parent.Value);
                                if (result < 0) parent.Left = current.Right;
                                else parent.Right = current.Right;
                        }
                }
                else {
                        Node<T> min = current.Right.Left, prev = current.Right;
                        while (min.Left != null) {
                                prev = min;
                                min = min.Left;
                        }
                        prev.Left = min.Right;
                        min.Left = current.Left;
                        min.Right = current.Right;
 
                        if (current == root) root = min;
                        else {
                                result = current.Value.CompareTo(parent.Value);
                                if (result < 0) parent.Left = min;
                                else parent.Right = min;
                        }
                }
                --Count;
        }
        public void Clear()
        {
                root = null;
                Count = 0;
        }
        public bool Contains(T value)
        {
                var current = root;
                while (current != null) {
                        var result = value.CompareTo(current.Value);
                        if (result == 0) return true;
                        if (result < 0) current = current.Left;
                        else current = current.Right;
                }
                return false;
        }
 
        public IEnumerable<T> Inorder()
        {
                if (root == null) yield break;
 
                var stack = new Stack<Node<T>>();
                var node = root;
 
                while (stack.Count > 0 || node != null) {
                        if (node == null) {
                                node = stack.Pop();
                                yield return node.Value;
                                node = node.Right;
                        }
                        else {
                                stack.Push(node);
                                node = node.Left;
                        }
                }
        }
        public IEnumerable<T> Preorder()
        {
                if (root == null) yield break;
 
                var stack = new Stack<Node<T>>();
                stack.Push(root);
 
                while (stack.Count > 0) {
                        var node = stack.Pop();
                        yield return node.Value;
                        if (node.Right != null) stack.Push(node.Right);
                        if (node.Left != null) stack.Push(node.Left);
                }
        }
        public IEnumerable<T> Postorder()
        {
                if (root == null) yield break;
 
                var stack = new Stack<Node<T>>();
                var node = root;
 
                while (stack.Count > 0 || node != null) {
                        if (node == null) {
                                node = stack.Pop();
                                if (stack.Count > 0 && node.Right == stack.Peek()) {
                                        stack.Pop();
                                        stack.Push(node);
                                        node = node.Right;
                                }
                                else { yield return node.Value; node = null; }
                        }
                        else {
                                if (node.Right != null) stack.Push(node.Right);
                                stack.Push(node);
                                node = node.Left;
                        }
                }
        }
        public IEnumerable<T> Levelorder()
        {
                if (root == null) yield break;
 
                var queue = new Queue<Node<T>>();
                queue.Enqueue(root);
 
                while (queue.Count > 0) {
                        var node = queue.Dequeue();
                        yield return node.Value;
                        if (node.Left != null) queue.Enqueue(node.Left);
                        if (node.Right != null) queue.Enqueue(node.Right);
                }
        }
 
        public IEnumerator<T> GetEnumerator()
        {
                return Inorder().GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
                return GetEnumerator();
        }
}
.
2
15 / 21 / 8
Регистрация: 05.04.2013
Сообщений: 204
09.07.2013, 14:25 3
Цитата Сообщение от I2um1 Посмотреть сообщение
Это кто такой?
Есть здесь у меня некоторая реализация
двоичного дерева
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
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
public class BinaryTree<T> : IEnumerable<T> where T : IComparable<T>
{
        class Node<TValue>
        {
                public TValue Value { get; set; }
                public Node<TValue> Left { get; set; }
                public Node<TValue> Right { get; set; }
 
                public Node(TValue value)
                {
                        Value = value;
                }
        }
 
        private Node<T> root;
 
        public BinaryTree() { }
        public BinaryTree(IEnumerable<T> collection)
        {
                AddRange(collection);
        }
 
        public int Count { get; private set; }
        public T Min
        {
                get
                {
                        if (root == null) throw new InvalidOperationException("Tree is empty");
                        var current = root;
                        while (current.Left != null)
                                current = current.Left;
                        return current.Value;
                }
        }
        public T Max
        {
                get
                {
                        if (root == null) throw new InvalidOperationException("Tree is empty");
                        var current = root;
                        while (current.Right != null)
                                current = current.Right;
                        return current.Value;
                }
        }
 
        public void Add(T value)
        {
                if (value == null) throw new ArgumentNullException("value");
 
                var node = new Node<T>(value);
 
                if (root == null)
                        root = node;
                else {
                        Node<T> current = root, parent = null;
 
                        while (current != null) {
                                parent = current;
                                if (value.CompareTo(current.Value) < 0) current = current.Left;
                                else current = current.Right;
                        }
 
                        if (value.CompareTo(parent.Value) < 0) parent.Left = node;
                        else parent.Right = node;
                }
                ++Count;
        }
        public void AddRange(IEnumerable<T> collection)
        {
                foreach (var value in collection)
                        Add(value);
        }
        public void Remove(T value)
        {
                if (value == null) throw new ArgumentNullException("value");
                if (root == null) return;
 
                Node<T> current = root, parent = null;
 
                int result;
                do {
                        result = value.CompareTo(current.Value);
                        if (result < 0) { parent = current; current = current.Left; }
                        else if (result > 0) { parent = current; current = current.Right; }
                        if (current == null) return;
                }
                while (result != 0);
 
                if (current.Right == null) {
                        if (current == root) root = current.Left;
                        else {
                                result = current.Value.CompareTo(parent.Value);
                                if (result < 0) parent.Left = current.Left;
                                else parent.Right = current.Left;
                        }
                }
                else if (current.Right.Left == null) {
                        current.Right.Left = current.Left;
                        if (current == root) root = current.Right;
                        else {
                                result = current.Value.CompareTo(parent.Value);
                                if (result < 0) parent.Left = current.Right;
                                else parent.Right = current.Right;
                        }
                }
                else {
                        Node<T> min = current.Right.Left, prev = current.Right;
                        while (min.Left != null) {
                                prev = min;
                                min = min.Left;
                        }
                        prev.Left = min.Right;
                        min.Left = current.Left;
                        min.Right = current.Right;
 
                        if (current == root) root = min;
                        else {
                                result = current.Value.CompareTo(parent.Value);
                                if (result < 0) parent.Left = min;
                                else parent.Right = min;
                        }
                }
                --Count;
        }
        public void Clear()
        {
                root = null;
                Count = 0;
        }
        public bool Contains(T value)
        {
                var current = root;
                while (current != null) {
                        var result = value.CompareTo(current.Value);
                        if (result == 0) return true;
                        if (result < 0) current = current.Left;
                        else current = current.Right;
                }
                return false;
        }
 
        public IEnumerable<T> Inorder()
        {
                if (root == null) yield break;
 
                var stack = new Stack<Node<T>>();
                var node = root;
 
                while (stack.Count > 0 || node != null) {
                        if (node == null) {
                                node = stack.Pop();
                                yield return node.Value;
                                node = node.Right;
                        }
                        else {
                                stack.Push(node);
                                node = node.Left;
                        }
                }
        }
        public IEnumerable<T> Preorder()
        {
                if (root == null) yield break;
 
                var stack = new Stack<Node<T>>();
                stack.Push(root);
 
                while (stack.Count > 0) {
                        var node = stack.Pop();
                        yield return node.Value;
                        if (node.Right != null) stack.Push(node.Right);
                        if (node.Left != null) stack.Push(node.Left);
                }
        }
        public IEnumerable<T> Postorder()
        {
                if (root == null) yield break;
 
                var stack = new Stack<Node<T>>();
                var node = root;
 
                while (stack.Count > 0 || node != null) {
                        if (node == null) {
                                node = stack.Pop();
                                if (stack.Count > 0 && node.Right == stack.Peek()) {
                                        stack.Pop();
                                        stack.Push(node);
                                        node = node.Right;
                                }
                                else { yield return node.Value; node = null; }
                        }
                        else {
                                if (node.Right != null) stack.Push(node.Right);
                                stack.Push(node);
                                node = node.Left;
                        }
                }
        }
        public IEnumerable<T> Levelorder()
        {
                if (root == null) yield break;
 
                var queue = new Queue<Node<T>>();
                queue.Enqueue(root);
 
                while (queue.Count > 0) {
                        var node = queue.Dequeue();
                        yield return node.Value;
                        if (node.Left != null) queue.Enqueue(node.Left);
                        if (node.Right != null) queue.Enqueue(node.Right);
                }
        }
 
        public IEnumerator<T> GetEnumerator()
        {
                return Inorder().GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator()
        {
                return GetEnumerator();
        }
}
.
а почему происходит наследование? На С# разве нельзя написать дерево с нуля как на С++?
0
Эксперт Java
4062 / 3796 / 745
Регистрация: 18.05.2010
Сообщений: 9,331
Записей в блоге: 11
09.07.2013, 15:02 4
okman, про какое наследование речь? Оно и так написано с нуля.
0
15 / 21 / 8
Регистрация: 05.04.2013
Сообщений: 204
09.07.2013, 15:06 5
Цитата Сообщение от turbanoff Посмотреть сообщение
okman, про какое наследование речь? Оно и так написано с нуля.
Это что такое, я просто шарпом несколько дней занимаюсь))) спасибо.
C#
1
public class BinaryTree<T> : IEnumerable<T> where T : IComparable<T>
0
Эксперт Java
4062 / 3796 / 745
Регистрация: 18.05.2010
Сообщений: 9,331
Записей в блоге: 11
09.07.2013, 15:19 6
Цитата Сообщение от okman Посмотреть сообщение
Это что такое, я просто шарпом несколько дней занимаюсь))) спасибо.
Это имплементация интерфейса IEnumerable, чтобы было удобнее дерево использовать.
1
Эксперт .NET
14421 / 10875 / 2873
Регистрация: 17.09.2011
Сообщений: 18,396
11.07.2013, 12:09 7
Цитата Сообщение от I2um1 Посмотреть сообщение
Есть здесь у меня некоторая реализация
Знакомая реализация

Вот тут обновленная версия, по-лучше в некоторых аспектах: Необходимо реализовать дерево и его обход в симметричном, прямом и обратном порядке
Кстати, есть там один глупый косячок. Не баг, а невнимательность. Любители смотреть код с лупой могут попытаться найти (может и баги какие всплывут )
0
Злой няш
1523 / 1187 / 407
Регистрация: 05.04.2010
Сообщений: 2,081
11.07.2013, 13:47 8
kolorotur, не знаю, так и не довелось протестировать. Валялся файлик на винте, пока не стерся - вот так часто используется это дерево.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.07.2013, 13:47

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

Преобразовать идеальное бинарное дерево в бинарное дерево поиска
Всем привет, я создал идельное бинарное дерево и написал к нему функции. Как мне теперь можно...

Написать функцию добавления элементов в бинарное дерево и поиска по ключу
Всем доброго времени суток! Немогу никак найти нормальною теорию или пример, поэтому уже пришлось...

Описать класс, реализующий бинарное дерево c возможностью добавления и удаления элементов
Описать класс, реализующий бинарное дерево, обладающее возможностью добав- ления новых элементов,...

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.


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

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

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