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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
#1

Вставка листа в дерево - C++

23.07.2013, 20:07. Просмотров 466. Ответов 9
Метки нет (Все метки)

Я тут изучал реализацию двоичного дерева поиска и застопорился на одном моменте: не могу понять зачем при вставке листа( узла ) в дерево используется указатель на указатель на узел. Пробовал сделать через указатель на узел, но ничего не получилось. Подскажите, для чего здесь нужен указатель на указатель?

Кусок кода из Tree.h
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
template< typename NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE& value )
{
    insertNodeHelper( &rootPtr, value );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE >** ptr, const NODETYPE& value )
{
    if( *ptr == 0 )
        *ptr = new TreeNode< NODETYPE >( value );
    else // поддерево не пусто
    {
        if( value < ( *ptr )->data )
            insertNodeHelper( &( ( *ptr )->leftPtr), value );
        else
        {
            if( value > ( *ptr )->data )
                insertNodeHelper( &( ( *ptr )->rightPtr), value );
            else 
                cout << value << " - duplicate" << endl;
        }
    }
}
TreeNode.h
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
#pragma once
 
template< typename NODETYPE > class Tree; // опережающее объявление шаблона класса
 
template< typename NODETYPE >
class TreeNode
{
    friend class Tree< NODETYPE >;
 
public:
    TreeNode( const NODETYPE& d )
        : leftPtr( 0 ), rightPtr( 0 ), data( d )
    {
        
    }
 
    NODETYPE getData() const
    {
        return data;
    }
private:
    TreeNode< NODETYPE >* leftPtr;
    TreeNode< NODETYPE >* rightPtr;
    NODETYPE data;
};
Полный заголовочный файл Tree.h
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
#pragma once
 
#include "TreeNode.h"
 
#include <iostream>
using std::cout;
using std::endl;
 
#include <new>
 
template< typename NODETYPE >
class Tree
{
public:
    Tree();
    void insertNode( const NODETYPE& );
    void preOrderTraversal() const;
    void inOrderTraversal() const;
    void postOrderTraversal() const;
private:
    TreeNode< NODETYPE >* rootPtr; // корневой узел
 
    // сервисные функции:
    void insertNodeHelper( TreeNode< NODETYPE >*, const NODETYPE& ); // указатель на указатель, 
                                                                      // чтобы функция могла изменять значение указателя
    void preOrderHelper( TreeNode< NODETYPE >* ) const;
    void inOrderHelper( TreeNode< NODETYPE >* ) const;
    void postOrderHelper( TreeNode< NODETYPE >* ) const;
};
 
template< typename NODETYPE >
Tree< NODETYPE >::Tree()
{
    rootPtr = 0;
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE& value )
{
    insertNodeHelper( &rootPtr, value );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::insertNodeHelper( TreeNode< NODETYPE >** ptr, const NODETYPE& value )
{
    if( *ptr == 0 )
        *ptr = new TreeNode< NODETYPE >( value );
    else // поддерево не пусто
    {
        if( value < ( *ptr )->data )
            insertNodeHelper( &( ( *ptr )->leftPtr), value );
        else
        {
            if( value > ( *ptr )->data )
                insertNodeHelper( &( ( *ptr )->rightPtr), value );
            else 
                cout << value << " - duplicate" << endl;
        }
    }
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{
    preOrderHelper( rootPtr );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::preOrderHelper( TreeNode< NODETYPE >* ptr ) const
{
    if( ptr != 0 )
    {
        cout << ptr->data << ' ';
        preOrderHelper( ptr->leftPtr );
        preOrderHelper( ptr->rightPtr );
    }
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{
    inOrderHelper( rootPtr );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::inOrderHelper( TreeNode< NODETYPE >* ptr ) const
{
    if( ptr != 0 )
    {
        inOrderHelper( ptr->leftPtr );
        cout << ptr->data << ' ';
        inOrderHelper( ptr->rightPtr );
    }
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{
    postOrderHelper( rootPtr );
}
 
template< typename NODETYPE >
void Tree< NODETYPE >::postOrderHelper( TreeNode< NODETYPE >* ptr ) const
{
    if( ptr != 0 )
    {
        postOrderHelper( ptr->leftPtr );
        postOrderHelper( ptr->rightPtr );
        cout << ptr->data << ' ';
    }
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.07.2013, 20:07
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вставка листа в дерево (C++):

Вставка элемента в дерево - C++
Доброго времени суток.Такая проблема,есть задача: Написать программу,реализующую вставку в Trie дерево.С помощью этой программы создайте...

B-Дерево. Поиск. Вставка. Удаление. - C++
Доброго всем дня,есть задача: Написать программу реализующую следующие действия в B-Дереве: Поиск. Вставка. Удаление. Так же у меня...

Вставка узла в дерево Windows Explorer - C++
Хочу, чтобы моя прога добавляла в дерево Explorerа свой узел (типа как Панель управления или Сетевое окружение) и при обращении к ней...

Двоичное дерево (операции вставка, удаление, поиск) - C++
Вообщем пытаюсь научиться работать с двоичными деревьями. Информацию беру с википедии: ru.wikipedia.org. Пока пытаюсь реализовать...

из листа клетчатой бумаги N*N клеток вырезали М клеток . на сколько кусков распадается оставшаяся часть листа? - C++
условие:из листа клетчатой бумаги N*N клеток вырезали М клеток . на сколько кусков распадается оставшаяся часть листа? Первая строка...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.07.2013, 20:10 #2
этот вопрос говорит о том, что не полностью понимаете тему указателей. попробуйте передать указатель в функцию и в ней поменять значение указателя.
0
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
23.07.2013, 20:26  [ТС] #3
Thinker, попробовал. Все меняется.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using std::cout;
using std::endl;
 
void func( int* );
 
int main()
{
    int someInt = 5;
    int* intPtr = &someInt;
    func( intPtr );
 
    system("pause");
    return 0;
}
 
void func( int* ptr )
{
    int sInt = 55;
    ptr = &sInt;
 
    cout << *ptr << endl;
}
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.07.2013, 20:41 #4
да, вынесете cout за функцию и посмотрите

Не по теме:

p.s. что-то невнимательный сегодня

0
Discoverer
16 / 14 / 2
Регистрация: 05.07.2013
Сообщений: 27
23.07.2013, 20:43 #5
WindSlasher, в этой функции меняется значение копии указателя, а не самого указателя. Поместите вывод после вызова функции, а не в ее теле, и увидите.
1
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.07.2013, 21:12 #6
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using std::cout;
using std::endl;
 
void func( int* );
 
int main()
{
    int* intPtr;
 
    func( intPtr );
    cout<<"address of new int after func is Invalid:"<<intPtr  <<endl;
    system("pause");
    return 0;
}
 
void func( int* ptr )
{
    ptr = new int;
    cout<<"address of new int inside func is Valid:"<<    ptr  <<endl;
}
0
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
23.07.2013, 21:41  [ТС] #7
Для чего вы мне это все показываете? Я не могу понять, как это относится к использованию указателя на указатель на узел, в моих исходниках? Походу я слишком туп

P.S. в полном файле Tree.h ошибка в 25 строке. Там должно быть "void insertNodeHelper( TreeNode< NODETYPE >**, const NODETYPE& );"
0
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
23.07.2013, 21:44 #8
к тому, что каждая вершина дерева содержит информационные поля и ссылочные (указатели). чтобы вставить вершину в дерево, надо в некоторой вершине изменить значение этого самого указателя. а так как вы не понимаете как менять значение самого указателя, у вас и возникают трудности
1
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,925
Записей в блоге: 1
23.07.2013, 22:06 #9
Цитата Сообщение от WindSlasher Посмотреть сообщение
Для чего вы мне это все показываете?
Потому что был вопрос
Цитата Сообщение от WindSlasher Посмотреть сообщение
для чего здесь нужен указатель на указатель?
Ответ - запусти пример из поста 6, и ты увидишь, что адрес выделенной в функции памяти теряется после выхода из функции, если передавать в неё просто одинарный указатель.

Потому что в данном примере (в отличие от примеров, когда в функцию передаётся указатель на внешнюю переменную, которая будет изменяться внутри функции по указателю)
В отличие от этого случая нам нужно выудить из функции не значение переменной, а её корректный адрес, выделенный new. и в таком случае сам адрес будет играть роль переменной величины, интересующей нас.
А раз так, этот адрес нельзя передавать аргументом по значению - требуется передавать его через указатель.

А это и будет указатель на указатель! TreeNode< NODETYPE >** ptr
1
WindSlasher
0 / 0 / 0
Регистрация: 22.06.2013
Сообщений: 34
24.07.2013, 00:04  [ТС] #10
Thinker, кажется я понял, спасибо. Получается, если бы я использовал просто указатель, то присваивал бы адрес, возвращаемый операцией new, указателю ptr в функции insertNodeHelper, а не одному из элементов данных-указателей класса TreeNode.

Добавлено через 29 минут
Спасибо за уделенное время
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.07.2013, 00:04
Привет! Вот еще темы с ответами:

Дано дерево. Распечатать дерево по уровням - C++
Дано дерево. Распечатать дерево по уровням.

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

Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). - C++
Представление дерева: а) Д (Б (А, Ф (В,)), Е (,З (Ж, И))) б) Д Б А Ф ...

Дерево дерево, странное дерево - C++
Нужна помощь в построении дерева. Задание таково: Вершина дерева содержит N целых значений и два указателя на потомков. Запись значений...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.07.2013, 00:04
Ответ Создать тему
Опции темы

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