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

[Syuf]

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

А зачем вы их определили так:

Item /*-> Это тип возвращаемого значения*/ *appItem(Item *itm,int release, char *str);
Item /*-> Это тип возвращаемого значения*/ *viewItem(Item *itm);

Должны возвращать указатель на Item (Item*).

[frmSm]

))))))), да уж, спасиб большое, что то я как то не придавал этому значения)))

В общем имею я корень(допустим). В корне имеется 2 потомка, я пытаюсь по ключу удалить потомка, в итоге мне выдаётся
дорустим введём
key: 22 release: 33 string:aaaa
key:33 release: 55 string:bbb
вывод:
key release string
22 33 aaa
33 55 bbb
после попытки удаления я получаю
key release string
22 33 aaa
0 55 bbb

[Syuf]

Я на минутку отключусь.

[frmSm]

Вроде вот эти 2 функции переписал, пошло вроде как , при удалении узла остальная часть дерева отрывается ))), последний элемент удаляется, 1й и единственный тоже. Буду дальше разбираться как реорганизовывать дерево после удаления. Я думаю взять сыновей и заново пропустить их по дереву. А вот если будет удаляться корневой узел, я присвою корневой узел левому поддереву, а правый пропущу заново по дереву. Но вот насчёт корня и его нахождения в дереве пока не совсем представляю как писать, эт тип аля дать всем родителей и если родителя нет то значит корневой, но мне не очень это нравится.

void delitem(Item *&itm) {
     while(!isItemEmpty(itm)) {
          Item *tmp=itm->next;
          free(itm);
          //free(itm->string);
          itm=tmp;
          } }

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

[Syuf]

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;
}

А кокава структура вашего дерева - объект Node является узлом и единицей дерева, данные об этом узле хранятся в *Item ключ в самом Node, так же как и *left и *right, но для чего *next в Item?

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

[frmSm]

Дерево то у меня имеет Item *info
Item это список,хранящий в себе release и string, и его продолжение формируется в том случае, если про введении в дерево нового листа с ключём, который уже имеет какой-то узел в дереве то то что мы ввели переносится в дерево с этим ключём.
По сути тут получается, что каждое дерево имеет уникальный ключ, и каждый узел по-сути является неким списком )))

О, ведь по-идее получается , что корневой каталог можно обозначить по ключу и дальше менять его в случае его удаления.

В принципе, если моя концепция проходит)))), то остаётся балансировка. может посоветуете ресурс , где можно посмотреть балансировку?

[Syuf]

Если я понял, что вы имеете ввиду, то можете посмотреть тут:

class binary_tree     //  class на данном этапе примерно то же, что и struct
{
protected:
	int length;
	class socket
	{
	public:
		double value;
		socket *left, *right;
		socket(double vl = 0) : value(vl), left(0), right(0) {}
		~socket(void)
		{
			if(left) delete left;
			left = 0;
			if(right) delete right;
			right = 0;
		}
	};
	socket *root;
	void copy_socket(socket*);
	void add_socket(socket*, double);
	socket** compare_socket(socket*, double);
	void _print(socket*);
public:
	binary_tree(size_t, double, ...);
	binary_tree(void) : root(0) {}
	binary_tree(const binary_tree&);
	~binary_tree(void);
	void add(double);
	void print(void);
};

binary_tree::binary_tree(size_t count, double vl, ...) : root(0)
{
	va_list elem;
	va_start(elem, count);
	for(size_t i=1; i<=count; add(va_arg(elem, double)), i++);
	va_end(elem);
}

binary_tree::binary_tree(const binary_tree &tree) : root(0)
{
	if(!tree.root) return;
	copy_socket(tree.root);
}

void binary_tree::copy_socket(socket *s)
{
	add(s->value);
	if(s->left) copy_socket(s->left);
	if(s->right) copy_socket(s->right);
}

void binary_tree::add(double vl)
{
	if(!root)
	{
		root = new socket(vl);
		return;
	}
	socket **temp = compare_socket(root, vl);
	*temp = new socket(vl);
}

binary_tree::socket** binary_tree::compare_socket(socket *now, double vl)
{
	if(now->value >= vl && now->left) return compare_socket(now->left, vl);
	else if(now->value >= vl) return &now->left;
	if(now->value < vl && now->right) return compare_socket(now->right, vl);
	else if(now->value < vl) return &now->right;
}

binary_tree::~binary_tree(void)
{
	if(root) delete root;
}

void binary_tree::print(void)
{
	if(!root) return;
	cout<<root->value<<endl;
	_print(root);
	cout<<endl;
}

void binary_tree::_print(socket *psock)
{
	if(psock->left) cout<<psock->left->value<<" ";
	if(psock->right) cout<<psock->right->value;
	cout<<endl;
	if(psock->left) _print(psock->left);
	if(psock->right) _print(psock->right);
}

Тут привидены все алгоритмы обращения с элементами. Тут вместо 'Item' 'double value'.

[frmSm]

Спасибо. разбрерусь в общем

удаление в случае находки нужного потомка заключается в создании нового дерева с корнем в предке удаленного и всеми ответвлениями удаляемого узла и присоединении его к этому предку

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

[frmSm]

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

функция записи writeinfo соответственно чтения- readinfo

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

#define sz 10
const int BUF_SIZE=80;

struct Item{
       int release;
       size_t InfoIndex;
	   size_t InfoLength;
       char *string;
       Item *next;
       };

struct Node{
       int key;
       bool root;
       Item *info;
       Node *left, *right, *parent;
       };

       
char * Messages[] = {
"\n1) Input	\n",
  "2) Delete	\n",	
  "3) View	\n",		
  "4) 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*&,char *);							
void Delete(Node*&, char*);			
void View(Node*&,char*);				
void Quit(Node*&,char*);				
Item *CreateItem(int , char *);



void WriteInfo(Node *&tree, char * fileName) {
     FILE * file = fopen(fileName,"wb+");
     size_t infoIndex = 0;
     Item *Data=tree->info;
     while(Data)
     {
 
            Data->InfoIndex = infoIndex;
			Data->InfoLength = strlen(Data->string);
			fwrite(Data->string, sizeof(char),Data->InfoLength, file);
			delete[] Data->string;
			infoIndex += Data->InfoLength;
			Data = Data->next;
		}
		//WriteInfo(tree->left,fileName);
     //WriteInfo(tree->right,fileName);
fclose(file);
}



void ReadInfo(Node *&tree, char * fileName)
{
	FILE * file = fopen(fileName,"rb");
	//treeFile(Node *&tree, char * fileName)
	//while(!tree) {
		Item *Data=tree->info;
        while(Data)
		{
			char buf[BUF_SIZE];
			Data->string = new char[Data->InfoLength];
			fseek(file, Data->InfoIndex, SEEK_SET);
			fread(buf, sizeof(char), Data->InfoLength, file);
			buf[Data->InfoLength] = 0;
			strcpy(Data->string, buf);

			Data = Data->next;
		//}
     //ReadInfo(tree->left,fileName);
     //ReadInfo(tree->right,fileName);
	}
	fclose(file);
}

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

bool isItemEmpty(Item*& itm) {
     return itm==0;
     }

void delitem(Item *&itm) {
     while(!isItemEmpty(itm)) {
          Item *tmp=itm->next;
          free(itm);
          itm=tmp;
          
          } }

     
     
//создание элемента  
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 inputRoot(Node** tree,Item *itm,int key) {
     if (*tree==NULL) {
        *tree=new Node;
        (*tree)->key=key;    
        (*tree)->info=itm;
        (*tree)->left=NULL;
        (*tree)->right=NULL;
        (*tree)->root=1;
        } }

//вставка нового листа
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;
        (*tree)->root=0;
        }
     else
         if(key < (*tree)->key) 
                              input(&((*tree)->left), itm, key);
                              else
         if(key > (*tree)->key) 
                              input(&((*tree)->right), itm, key);
                              }

void appItem(Item *itm,int release, char *str) {
     if ((itm->next))
     appItem(itm->next,release,str);
     else 
     itm->next=CreateItem(release,str);
     }

[frmSm]

продолжение

//поиск ключа, если такой есть , то добавляем в него новый элемент 
int findkey(Node *tree,int key,int release, char *str) {
    if(tree!=NULL) {
	       if((tree)->key==key) {
                              appItem(tree->info,release,str); 
		           return 1;
                   } 
	            
    if (tree->key!=key) {
                        if(key<tree->key)
     findkey(((tree)->left),key,release,str);
                        if(key<tree->key) 
     findkey(((tree)->right),key,release,str);
     } }
     return 0;
} 

void delRoot(Node *&tree) {
             Node *tmp=tree;
             Node *tmpl=tree->left; 
             Node *tmpr=tree->right;
             delitem(tree->info);
                           delete tmp;
                           if(tmpl) {
                           tree=tmpl;
                           tree->root=1; 
                           if(tmpr)
                           input(&tree,tmpr->info,tmpr->key); }
                           if(!tmpl && tmpr) 
                                    tree=tmpr;
                                    tree->root=1;
                           if (!tmpl && !tmpr)
                           tree=NULL;
                           }
                       

int findkeyThenDel(Node *&tree,int key) {
    if(tree!=NULL) {
           if(tree->key==key && tree->root==1) {
                             delRoot(tree);
                           return 1;
                           }
                           else
                                     
	       if((tree)->key==key) {
                          Node *tmp=tree;
                          Node *tmpl=tree->left; 
                          Node *tmpr=tree->right;
                          delitem(tree->info);
                           delete tmp;
                           tree=NULL;
                           if (tmpl)
                           input(&tree,tmpl->info,tmpl->key);
                           if (tmpr)
                           input(&tree,tmpr->info,tmpr->key);   
		           return 1;
                   } 
	            
    if ((tree)->key!=key) {
                          if(key<tree->key) 
     findkeyThenDel(((tree)->left),key);
                          if(key>tree->key)               
     findkeyThenDel(((tree)->right),key);
     } }
     return 0;
}


void 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, char * fileName) {
     ReadInfo(tree, fileName);
     cout << "key\t" << "Release\t" << "String" << endl;   
     treeView(tree);
     }


void Insert(Node *&tree, char *fileName) 
{
    //ReadInfo(tree, fileName);
   	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 (!tree) {
    inputRoot((&tree),itm,key);
    WriteInfo(tree,fileName); 
    return;}
	if  (findkey(tree,key,release,string)) {
    WriteInfo(tree,fileName); return;}
    input((&tree),itm,key); 
    WriteInfo(tree,fileName);
 }

void Delete(Node *&tree, char * fileName) {
     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;
     }

void Quit(Node *&tree, char * fileName) {
     if (tree != NULL) {
     delRoot(tree);
     Quit(tree,fileName);
		 } 
		 else return;
      }
     
     
int main()
{
	setlocale(LC_ALL, "Russian");
	char fileName[BUF_SIZE];
    cout<<"insert file name"<<endl;
    cin.getline(fileName,BUF_SIZE);
	fclose(fopen(fileName,"wb+"));		
	Node *tree=NULL;
  				
	int answer = 1;
	do {							
		answer = Menu();
 		func[answer](tree,fileName);
	} while (answer);

}