Не получается удалить узел дерева.

[frmSm]

после удаления всё равно выводятся некоторые элементы узла.

#include <iostream>
#include <stdio.h>
using namespace std;

#define sz 10

struct Item{
       int release;
       char *string;
       Item *next;
       };

struct Node{
       int key;
       Item *info;
       Node *left, *right;
       };
       
char * Messages[] = {
     "\n2) View	\n",	
	"3) Input	\n",		
	"1) Delete	\n",		
			
	//"5) Exit	\n"			
};

int MessagesCount = sizeof(Messages) / sizeof(Messages[0]);		

int Menu() {		
	int answer = 1;
	do {
		for (int i = 0; i < MessagesCount; i++)
			cout << Messages[i];
		cout << "Please, select menu item: ";
		cin >> answer;
	} 
    while (answer < 1 || answer > MessagesCount);
	return answer % MessagesCount;
} 



void Insert(Node*&);							
void Delete(Node*&);			
void View(Node*&);				
//void Quit(Node*);				

Item *CreateItem(int , char *);

void (*func[])(Node*&) = {		
//	Quit,
	Insert,
    Delete,
	View
};

    
//Ñîçäàíèå ýëåìåíòà     
Item *CreateItem(int release, char *str)
{
	Item *item = new Item;
	item->release = release;
	item->string = new char[strlen(str) + 1];
	strcpy(item->string, str);
	item->next = NULL;
	return item;
}

//Ñîçäàíèå óçëà
void input(Node** tree,Item *itm,int key) {
     if (*tree==NULL) {
        *tree=new Node;
        (*tree)->key=key;    
        (*tree)->info=itm;
        (*tree)->left=NULL;
        (*tree)->right=NULL;
        }
     else
         if(key < (*tree)->key) 
                              input(&((*tree)->left), itm, key);
                              else
         if(key > (*tree)->key) 
                              input(&((*tree)->right), itm, key);
                              }

Item *appItem(Item *itm,int release, char *str) {
     if ((itm->next))
     appItem(itm->next,release,str);
     else 
     itm->next=CreateItem(release,str);
     }
     
//Ïîèñê óçëà ïî êëþ÷ó    
int findkey(Node *tree,int key,int release, char *str) {
    if(tree!=NULL) {
	       if((tree)->key==key) {
                              appItem(tree->info,release,str); 
/*                    while(tree->info) {
                            if((tree->info->next)) {
                             tree->info=tree->info->next; }
                            else {    
                   (tree)->info->next=CreateItem(release,str);} }  
                   //(tree)->info=(tree)->info->next;*/
		           return 1;
                   } 
	            
    if (tree->key!=key) {
     findkey(((tree)->left),key,release,str);
     findkey(((tree)->right),key,release,str);
     } }
     return 0;
} 

int findkeyThenDel(Node *tree,int key) {
    if(tree!=NULL) {
	       if((tree)->key==key) {
                          Node *tmp=new Node;
                          //Item *itm=new Item;
                          //itm=*&(tree->info);
                          tmp->right=tree->right;
                          tmp->left=tree->left;
                          //delete ((*tree)->info);
                           delete *&tree;
                           tree=NULL;
                          // free(itm);
//                          delete tmp;      
		           return 1;
                   } 
	            
    if ((tree)->key!=key) {
     findkeyThenDel(((tree)->left),key);
     findkeyThenDel(((tree)->right),key);
     } }
     return 0;
}


Item *viewItem(Item *itm) {
     for(;;) {
                      cout<<"\t" << itm->release << "\t" << itm->string 
                      << endl;
                      itm=itm->next;
                      if(!(itm)) break;
                      } }                      
     

void treeView(Node*& tree) {

     if (tree != NULL) {
     cout<<tree->key ;
     viewItem(tree->info);
     // endl ;
     treeView(tree->left);
     treeView(tree->right);
		 } 
         else return; }      
                       
void View(Node*& tree) {
     cout << "key\t" << "Release\t" << "String" << endl;   
     treeView(tree);
     }




void Insert(Node *&tree) 
{
   	Item *itm=NULL;
	int key;
	int release;
	int aa;
	char string[80];
	cout << "\nVvedite key    : "; cin >> key;
    cout << "\nVvedite release: "; cin >> release;
	cout << "\nVvedite string : "; cin >> string;
	itm=CreateItem(release,string);
	if (findkey(tree,key,release,string)) return;
    input((&tree),itm,key); 
}

void Delete(Node *&tree) {
     int key;
     cout << "\nInser key for del : ";
     cin >> key; cout <<endl;
     if(findkeyThenDel(tree,key))
     
     cout << "node deleted" << endl;
     else
     cout << "No key in tree" << endl;
     }
     
int main()
{
	setlocale(LC_ALL, "Russian");
			
	Node *tree=NULL;
  				
	for(;;) {
	int answer = 1;
	do {							
		answer = Menu();
		func[answer](tree);	
	} while (answer);
}
    return 0;
}

[Syuf]

А некоторую присказку лень написать? Что делаете, где удаляете, как удаляете, что выводится, что должно выводиться и т.д.?

[frmSm]

Хм, да , что то я....

[frmSm]

))). вот сама функция удаления
Удаление узла должно происходить в том случае , если найден его ключ. Но так выходит что при использовании функции удаляется только ключ, а элемент (release и string) не удаляется и выводится с 0 ключём. Удаляю я рекурсивно пробегаясь по дереву в поиске ключа.

int findkeyThenDel(Node *tree,int key) {
    if(tree!=NULL) {
	       if((tree)->key==key) {
                          Node *tmp=new Node;
                          tmp->right=tree->right;
                          tmp->left=tree->left;
                           delete *&tree;
                           tree=NULL;     
		           return 1;
                   } 
	            
    if ((tree)->key!=key) {
     findkeyThenDel(((tree)->left),key);
     findkeyThenDel(((tree)->right),key);
     } }
     return 0;
}

tmp->right и tmp->left я планирую использовать для связи оторванных узлов

[Syuf]

В вашем коде разобраться трудно - начиная с объявления переменной в теле цикла, кончая парой компиляционных ошибок.
Каким образом "при использовании функции удаляется только ключ, а элемент (release и string) не удаляется и выводится с 0 ключём", если код вообще не запускается?

[Ozerich]

Если дерево должно поддерживать удаление, то кроме левого и правого сына должен еще и указатель на предка храниться. И в дереве всегда правый сын больше чем его предок, соответственно левый сын всегда меньше чем его предок. Это значит что не надо обоих сыновей просматривать.

[Syuf]

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

[frmSm]

Сообщение от Ozerich

Если дерево должно поддерживать удаление, то кроме левого и правого сына должен еще и указатель на предка храниться. И в дереве всегда правый сын больше чем его предок, соответственно левый сын всегда меньше чем его предок. Это значит что не надо обоих сыновей просматривать.

Насчёт предка я думал, но как то не стал реализовывать.
Ну насчёт просмотра сыновей.. в принципе это вопрос оптимизации, но всё равно спасибо.

Сообщение от Syuf

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

А если нужно будет удалять корневой узел?
Насчёт доработки согласен))), но это потом.
И кстати я на dev c++ пишу так что в вижл цпп может хреново запускаться.

[Syuf]

И кстати я на dev c++ пишу так что в вижл цпп может хреново запускаться.

Хреново - это одно дело, а когда appItem и viewItem вообще не возвращают значения - это плохо.

А если нужно будет удалять корневой узел?

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

[frmSm]

да с appItem и viewItem всё в порядке вроде.
appItem нужен для добавления в info (элемент-список узла или листа)
viewItem я использую для того чтобы пробежаться по info и вывести значения. Просто в info идёт добавление ещё одного элемента, если уже существует узел/лист с введённым ключём.