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

Неправильно удаляет узел из бинарного дерева - C++

Восстановить пароль Регистрация
 
litwisha101
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 5
13.04.2013, 18:07     Неправильно удаляет узел из бинарного дерева #1
Помогите подправить фунцию SearchDelete...Почему-то не работет.

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
//13.   Побудувати довільне бінарне дерево, зчитавши числові значення його вузлів з файла.
//Видалити з дерева усі вузли, значення яких є парними числами.
//Надрукувати  дерево, що утворено до та після видалення його вузлів. 
#include<iostream>
#include<string.h>
#include<conio.h>
using namespace std;
struct node {                               //тип вузла дерева
   int data;                    //інформаційне поле вузла
   node *left,                    //покажчик на ліве піддерево
        *right;                  //покажчик на праве піддерево
};
 int n;                              //кількість вершин дерева
 int value;                      //значення вузлів дерева
 node *root;     
 node *delNode;//покажчик на корінь дерева
 int M=0;
//================= зображення дерева ======================
void Printtree(node **RootTree, int L)
{                //RootTree — масив покажчиків на вузли дерева
                 //L — номер рівня дерева
 if((*RootTree!=NULL))                     //дерево не порожнє
 {
  Printtree(&((*RootTree)->left),L+1);//вивести ліве піддерево
  for(int i=0;i<L;i++)cout<<"    ";    //форматувати виведення
                                                      //дерева
     cout<<(*RootTree)->data<<endl;   //вивести значення вузла
  Printtree(&((*RootTree)->right),L+1);//вивести праве піддерево
   }
}
//============== створення бінарного дерева ==================
void Tree( node  **ptr, int str,int AmountNode )
{ 
           //**ptr - масив покажчиків на вузли дерева,
          //str[10]-рядок, що є значенням інформаційного поля,
                          //AmountNode-кількість вузлів дерева
  int LeftNodes,                    //кількість вузлів у лівому
      RightNodes;                        //і правому піддеревах
  if( AmountNode ==0)                     //якщо вузлів немає,
    *ptr=0;                                   //дерево порожнє
  else 
  {
   LeftNodes= AmountNode / 2;  //кількість вузлів у піддеревах
   RightNodes= AmountNode - LeftNodes -1;
   cout<<"Enter node data: ";
   cin>>str;                //ввести значення для вузла дерева
   *ptr= new node;                     //створити вузол дерева
   (*ptr)->data=str;        //занести значення у вузол
   (*ptr)->left=0;           //обнулити покажчики на піддерева
   (*ptr)->right=0;
        //створити ліве піддерево з кількістю LeftNodes вузлів 
    Tree (&((*ptr )->left ), str, LeftNodes );
      //створити праве піддерево з кількістю RightNodes вузлів 
    Tree(&((*ptr )->right ), str, RightNodes);
  }
}
 
void CaseTwoChild(node** ref)
{
    if((*ref)->right !=NULL)
        CaseTwoChild(&((*ref)->right));
    else
    {
        delNode->data= (*ref)-> data;
        delNode=*ref;
        *ref=(*ref)->left;
    }
}
//===========================================//
 
void SearchDelete(node** pNode, int key)
{
    if(*pNode==NULL)
        cout<<"node is not found"<<endl;
    else 
        if(key<(*pNode)->data)
            SearchDelete(&((*pNode)->left), key);
        else
            if(key>(*pNode)->data)
                SearchDelete(&((*pNode)->right), key);
            else {
                delNode=*pNode;
                if(delNode->right==NULL)
                    *pNode=delNode->left;
                else 
                    if(delNode->left==NULL)
                        *pNode=delNode->right;
                    else
                        CaseTwoChild(&(delNode->left));
                delete delNode;
            }
}
 
//=================== основна програма  ======================
int main()
{
  cout<<"Enter number of tree''s nodes"<<endl;
  cin>>n;                      //задати кількість вузлів дерева
  root=NULL;
  cout << "Enter "<<n<<" integer values:\n";
  Tree(&root,value,n);                        //створити дерево
                         //аргументи: покажчик на корінь дерева,
                          //значення у кореневому вузлі  дерева,
                                      //кількість вузлів дерева
  cout<<"Created tree"<<endl;
  Printtree(&root,0);                      //відобразити дерево
  char ch;
  do
  {
      system("cls");
      Printtree(&root,0);
      cout<<"Enter key to search and delete"<<endl;
      cin>>value;
      SearchDelete(&root, value);
      cout<<"Continue?"<<endl;
      cin>>ch;
      getch();
 
  }while(ch!='n');
  system("pause");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2013, 18:07     Неправильно удаляет узел из бинарного дерева
Посмотрите здесь:

Копирование бинарного дерева C++
C++ Обход бинарного дерева
C++ Построение бинарного дерева на основе не бинарного
Создать полную копию исходного дерева и проверить узел C++
C++ Обход бинарного дерева
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zer0mail
2184 / 1867 / 187
Регистрация: 03.07.2012
Сообщений: 6,635
Записей в блоге: 1
13.04.2013, 20:06     Неправильно удаляет узел из бинарного дерева #2
Можешь по-русски написать что надо сделать и как должен работать алгоритм удаления узлов (куда девать подузлы удаленного узла)?
litwisha101
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 5
13.04.2013, 20:31  [ТС]     Неправильно удаляет узел из бинарного дерева #3
Цитата Сообщение от zer0mail Посмотреть сообщение
Можешь по-русски написать что надо сделать и как должен работать алгоритм удаления узлов (куда девать подузлы удаленного узла)?
Вообще-то в задаче надо удалить все узлы, значения которых есть парные числа. Это бинорное дерево поиска. Все подузлы что остались нужно так сформировать чтобы это дерево оставалось бинарным деревом поиска.
zer0mail
2184 / 1867 / 187
Регистрация: 03.07.2012
Сообщений: 6,635
Записей в блоге: 1
14.04.2013, 09:03     Неправильно удаляет узел из бинарного дерева #4
1. Неясно, что такое парные числа.
2. Должно дли дерево обладать каким-то свойстовами. Если "Да", то где эти свойства описано. Если "Нет", то почему его называете "бинарным деревом поиска".
3. Первоначально дерево строится без учета значений в узлах, когда же оно становится "деревом поиска"?
4. Подузлы удаленного дерева могут прицепляться куда угодно или структура дерева должна перестраиваться так, чтобы свойства сохранились (что может потребовать сложного программирования и/или добавления ссылки на родителя).
5. Вот еще ссылка: Добавление элементов бинарное дерево
litwisha101
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 5
14.04.2013, 11:36  [ТС]     Неправильно удаляет узел из бинарного дерева #5
Цитата Сообщение от zer0mail Посмотреть сообщение
1. Неясно, что такое парные числа.
2. Должно дли дерево обладать каким-то свойстовами. Если "Да", то где эти свойства описано. Если "Нет", то почему его называете "бинарным деревом поиска".
3. Первоначально дерево строится без учета значений в узлах, когда же оно становится "деревом поиска"?
4. Подузлы удаленного дерева могут прицепляться куда угодно или структура дерева должна перестраиваться так, чтобы свойства сохранились (что может потребовать сложного программирования и/или добавления ссылки на родителя).
5. Вот еще ссылка: Добавление элементов бинарное дерево
Дословно задача звучит так:
Построить любое двоичное дерево и считать числовые значения его узлов с файла.
Удалить с дерева те узлы, значения которых есть четные числа. Вывести дерево до и после удаления узлов.
Yandex
Объявления
14.04.2013, 11:36     Неправильно удаляет узел из бинарного дерева
Ответ Создать тему
Опции темы

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