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

Бинарные деревья с обратной связью - C++

Восстановить пароль Регистрация
 
Grif1992
0 / 0 / 0
Регистрация: 06.10.2011
Сообщений: 50
27.09.2012, 17:51     Бинарные деревья с обратной связью #1
Дан адрес P1 вершины дерева — записи типа TNode, содержащей поля Data (целого типа), Left, Right и Parent (типа PNode — указателя на TNode). Поля Left и Right указывают на дочерние вершины, а поле Parent — на родительскую вершину данной вершины (если вершина является корнем дерева, то ее поле Parent равно nil). Для данной вершины вывести указатели PL, PR и P0 на ее левую и правую дочерние вершины и родительскую вершину, а также указатель P2 на ее сестру, т. е. другую вершину дерева, имеющую в качестве родительской вершину с адресом P0. Если некоторые из перечисленных вершин не существуют, то вывести для них значение nil. Помогите пожайлуста! Вот пример программы
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
#include <iostream>
#include <fstream>
using namespace std;
struct Node
{
int info;
Node *left;
Node *right;
};
Node * addNode(int key)
{
Node * tmp;
tmp = new Node;
tmp->info = key;
tmp->left = NULL;
tmp->right = NULL;
return tmp;
}
bool add(Node * first, int key)
{
Node * tmp = first;
if(tmp->info == key) return false;
if(tmp->info > key)
{
if(tmp->left) return add(tmp->left,key);
else
{
tmp->left = addNode(key);
return true;
}
}
else
{
if(tmp->right) return add(tmp->right,key);
else
{
tmp->right = addNode(key);
return true;
}
}
}
bool add_not_recursiv(Node *first,int key)
{
Node * tmp = first;
 
while(tmp!= NULL)
{
if(tmp->info == key) return false;
if(tmp->info > key)
{
if(tmp->left)tmp = tmp->left;
else break;
}
else
{
if(tmp->right)tmp = tmp->right;
else break;
}
}
if(tmp->info > key)tmp->left = addNode(key);
else tmp->right = addNode(key);
return true;
}
 
int min(Node *first)
{
Node *tmp = first;
while(tmp->left) tmp = tmp->left;
return tmp->info;
}
 
void print_Tree(Node * p,int level)
{
if(p)
{
print_Tree(p->left,level + 1);
for(int i = 0;i< level;i++) cout«" ";
cout « p->info « endl;
print_Tree(p->right,level + 1);
}
}
void print(Node *p)
{
if(p)
{
print(p->left);
 
cout « p->info «" ";
 
print(p->right);
}
 
}
int main()
{
Node *first;
ifstream f;
f.open("input.txt",ios::in);
int key;
f»key;
first = addNode(key);
/*while(!f.eof())
{
f » key;
if(!add(first,key)) cout«"Repeat "«key«endl;
}*/
 
while(!f.eof())
{
f » key;
if(!add_not_recursiv(first,key)) cout«"Repeat "«key«endl;
}
print_Tree(first,0);
cout«" Min = "«min(first)«endl;
cout «"Sort"«endl;
print(first);
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.09.2012, 17:51     Бинарные деревья с обратной связью
Посмотрите здесь:

Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
Бинарные деревья C++
C++ Бинарные деревья
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
27.09.2012, 18:09     Бинарные деревья с обратной связью #2
слишком запутано и условие, и "пример".
упрости. будет достаточно создать трехуровневое дерево, и в качестве "данной вершины" использовать какую-нибудь из среднего уровня?
обязательно ли заполнять дерево из файла? если да - файл покажи.
Grif1992
0 / 0 / 0
Регистрация: 06.10.2011
Сообщений: 50
27.09.2012, 18:21  [ТС]     Бинарные деревья с обратной связью #3
Да, будет достаточно...можно не из файла
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
27.09.2012, 19:06     Бинарные деревья с обратной связью #4
некрасиво, но должно работать:

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
class Node {
protected:
    int m_Value;
    Node *m_pParent;
    Node *m_pLeft;
    Node *m_pRight;
public:
    Node (int value) : m_Value (value), m_pParent (NULL), m_pLeft (NULL), m_pRight (NULL){};
    ~Node () { delete m_pLeft; delete m_pRight; }
 
    void setChildren (Node *pLeft, Node *pRight){ m_pLeft = pLeft;
            m_pRight = pRight;
            m_pLeft->m_pParent = this;
            m_pRight->m_pParent = this;
    }
    const Node* getParent () { return m_pParent; };
    const Node* getLeft () { return m_pLeft; };
    const Node* getRight () { return m_pRight; };
    const Node* getSibling () {
        if ( m_pParent != NULL){
            if (m_pParent->m_pLeft == this){
                return m_pParent->m_pRight;
            } else {
                return m_pParent->m_pLeft;
            }
        } else {
            return NULL;
        }
    }
    int getValue () { return m_Value; }
};
 
void populate (Node *pRoot){
    // level 1 (4 nodes)
    Node *pNodeL10 = new Node (5);
    Node *pNodeR10 = new Node (7);
    Node *pNodeL11 = new Node (2);
    Node *pNodeR11 = new Node (76);
 
    // level 0 (two nodes)
    Node *pNodeL00 = new Node (3);
    Node *pNodeR00 = new Node (13);
 
    pRoot->setChildren (pNodeL00, pNodeR00);
    pNodeL00->setChildren (pNodeL10, pNodeR10);
    pNodeR00->setChildren (pNodeL11, pNodeR11);
}
 
void test(){
    Node root (111);
    populate (&root);
    const Node *pTestNode = root.getLeft();
    if (pTestNode != NULL){
        // выведи родителя и детей этого узла можешь получить "брата" с помощью getSibling();
        ...
        //ну, и т.д.
    }
}
Yandex
Объявления
27.09.2012, 19:06     Бинарные деревья с обратной связью
Ответ Создать тему
Опции темы

Текущее время: 16:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru