не работает удаление и поиск в программе про бинарное дерево - Общие вопросы C/C++

Барби · 24.12.2008, 19:43

программа должна сравнивать 2 бинарных дерева, (чтобы проводить сравнение нужно осуществлять добвление, удаление) и поиск элементов по наличию. Не знаю почему, но удаление не работает, указываешь элемент,а удаляется либо последний введенный, либо вобще никакой не удаляется. И не работает поиск. Подскажите, пожалуйста, где ошибки и как поправить. программа запускается в консоле

Код:

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
typedef
 struct link
     {
      int data;
      link *left;
      link *right;
     };

class tree
{
 public:
   link *r;
   int m;
   int x;
   int depth;
   int minim;
   int c;
   int d;

link *Find(link* &Root, int a);
void add(link* &n,int arg);
void restruct(link * v);
void delete1(link *n,int arg);
void view(link* &n, int d);
void obhod1(link* &n, int *d1,int *min);
void obhod2(link* &n, int *d1,int min);
};

class bintree: public tree
{
 public:
 int  walk[100];

void Go(link *t,int y[], int &j);
};

link * tree::Find(link* &Root, int a)
    {
	if (Root == NULL) return(NULL);
	else
		if (a == Root->data) return(Root);
		else
			if (a < Root->data) return(Find(Root->left, a));
			else return(Find(Root->right, a));
    };

void bintree::Go(link *t,int y[],int &j)
{
  if (t!=NULL)
  {
    bintree::Go(t->left,y,j);
    {
      j++;
      y[j]=0;
    };
    bintree::Go(t->right,y,j);
    {
      j++;
      y[j]=1;
    };
  };
};



void tree::add(link* &n,int arg)
{
  link *ind;
  link *neo;
   neo = new link;
   neo->data=arg;
   neo->left=NULL;
   neo->right=NULL;
   if (n==NULL)  n = neo;
   else {
      ind=n;
      while (neo!=NULL) {
	 if (arg<ind->data)  {
	    if (ind->left==NULL)  {
	       ind->left=neo;
	       neo=NULL;
	    }
	    else ind=ind->left;
	 }
	 else
	    if (arg>ind->data)  {
	       if (ind->right==NULL)  {
		  ind->right=neo;
		  neo=NULL;
	       }
	       else ind=ind->right;
	    }
	    else {
	       puts("Such element is already exists");
	       neo=NULL;
	    };
      };
   };
}; /* add */

void tree::restruct(link *v)
{
  link *ind1;
  link *ind2;

   ind1=v;
   if (ind1->right==NULL)  {
      ind2=v;
      v=ind2->left;
      delete ind2;
   }
   else
      if (ind1->left==NULL)  {
	 ind2=v;
	 v=ind2->right;
	 delete ind2;
      }
      else {
	 ind2=ind1->left;
	 while (ind2->right!=NULL)  {
	    ind1=ind2;
	    ind2=ind2->right;
	 };
	 ind1->right=ind2->left;
	 ind2->left=v->left;
	 ind2->right=v->right;
	 delete v;
	 v=ind2;
      };
}; /* restruct */

void tree::delete1(link * n,int arg)
{
   link *del;
   link *ind;
   int t;

   t=0;
   del=n;
   while (del!=NULL && !t)  {
      if (arg==del->data)  t=1;
      else
	 if (arg<del->data)  {
	    ind=del;
	    del=del->left;
	 }
	 else {
	    ind=del;
	    del=del->right;
	 };
   };
      if (t)  {
	 if (del->left==NULL && del->right==NULL)  {
	    if (del==n)  { n=NULL; delete del; } else
	    if (ind->left==del)  {
	       ind->left=NULL;
	       delete del;
	    }
	    else {
	       ind->right=NULL;
	       delete del;
	    }
	 }
	 else
	    if (del==n)  restruct(n); else
	    if (ind->left==del)  restruct(ind->left);
	    else restruct(ind->right);
      }
      else puts("Element is absent");
}; /* delete */

void tree::view(link* &n, int d)
{
  int i;

   for (i=1; i<= d;i++) {
      printf("    "); };
   printf("%d\n",n->data);
   if (n->left==NULL && n->right==NULL)  d=d-1;
   else {
      if (n->right!=NULL)  {
	 d=d+1;
	 view(n->right,d);
      };
      if (n->left!=NULL)  {
	 d=d+1;
	 view(n->left, d);
      };
      d=d-1;
   };
}; /* view */

void tree::obhod1(link* &n, int *d1,int *min)
{
   if (n->left==NULL && n->right==NULL)  {
      if (d<*min)  *min=d;
      d=d-1; }
      else {
	 if (n->right!=NULL)  {
	    d=d+1;
	    obhod1(n->right, &d, min); };
	 if (n->left!=NULL)  {
	    d=d+1;
	    obhod1(n->left, &d,min); };
	d=d-1;
      };
}; /* obhod1 */

void tree::obhod2(link* &n, int *d1,int min)
{
   if (n->left==NULL && n->right==NULL)  {
      if (d==min)  printf("%d",n->data);
      d=d-1;
   }
   else {
      if (n->right!=NULL)  {
	 d=d+1;
	 obhod2(n->right,&d,min);
      };
      if (n->left!=NULL)  {
	 d=d+1;
	 obhod2(n->left, &d,min);
      };
      d=d-1;
   };
}; /* obhod2 */

Барби · 24.12.2008, 19:44

Код:

void main(void)
{
int temp,m,x,c,d,i;
bintree *pn,*pn1;
int flag;
   clrscr();
   m=1;
   temp=1;
   pn->r=NULL;pn1->r=NULL;
   while (m!=0) {
      printf("\n");
      printf("--- Type 1 to ADD new element\n");
      printf("--- Type 2 to DELETE element\n");
      printf("--- Type 3 to VIEW tree\n");
      printf("--- Type 4 to FIND elements with minimal depth\n");
      printf("--- Type 5 to TURN another tree\n");
      printf("--- Type 6 Equal?\n");
      printf("--- Type 7 Find element\n");
      printf("--- Type 0 to EXIT program\n");
      printf("\n");
      printf("Enter : ");
      scanf("%d",&m);
      printf("\n");
      switch (m){
       case	1 : {
	       printf("Enter new element : ");
	       scanf("%d",&x);
	       if(temp==1)   pn->add(pn->r, x);
		  else  pn1->add(pn1->r,x);
	    };break;
	case 2 : {
	       printf("Enter element you want to delete : ");
	       scanf("%d",x);
	       if (temp==1)  pn->delete1(pn->r, x);
		  else pn->delete1(pn1->r,x);
	    };break;
     case	3 : {
	       if (temp==1)   {
		    pn->depth=1;
		    if (pn->r==NULL)  printf("The tree is empty"); else {
		    printf("The tree is : \n");
		    pn->view(pn->r, pn->depth);
		    };
		    }
		  else {
			 pn1->depth=1;
			if (pn1->r==NULL)  printf("The tree is empty"); else {
			printf("The tree is : \n");
			pn1->view(pn1->r, pn1->depth);

		       };
	       };
	    };break;
   case	4 : {
	     if (temp==1)  {
	       pn->depth=1;
	       pn->minim=20;
	       if (pn->r!=NULL)  {
	       printf("Elements with minimal depth");
	       pn->obhod1(pn->r,&pn->depth,&pn->minim);
		  printf("%d",pn->minim);
		  pn->depth=1;
		  pn->obhod2(pn->r,&pn->depth,pn->minim);
	       }
	       else printf("The tree is empty");
	      }
	     else {
		  if (pn1->r!=NULL)  {
		  printf("Elements with minimal depth");
		  pn1->obhod1(pn1->r,&pn1->depth,&pn1->minim);
		  printf("%d",pn1->minim);
		  pn1->depth=1;
		  pn1->obhod2(pn1->r,&pn1->depth,pn1->minim);
		  }
		    else printf("The tree is empty");
		  };
	    };break;
      case	5: {
	    if (temp==1)  {
			    temp=2;
			    printf("Current 2\n");
			   }
	       else {
		     temp=1;
		     printf("Current 1\n");
		    };
	   }; break;
      case	6: {
	   c=0;d=0;
	   pn->Go(pn->r,pn->walk,c);
	   pn1->Go(pn1->r,pn1->walk,d);
	   if (c==d)  {
		       flag=1;
		       for (i=1;i<= c;i++)
			 if (pn1->walk[i]!=pn->walk[i])  flag=0;
		       if (flag)  printf("Equal\n");
			  else printf("No\n");
		       }
	      else printf("No\n");

	   }; break;
      case	7:{
	   printf("Enter  element to Find: ");
	   scanf("%d",x);
	   if (temp==1)  {
			  if (pn->Find(pn->r,x) != NULL)  printf("Yes\n");
			     else printf("No\n");
			  }
	      else {
		    if (pn1->Find(pn1->r,x)!= NULL)  printf("Yes\n");
		       else printf("No\n");
		   };
	  }; break;
      }; /* case */
   };
}

MaTBeu · 24.12.2008, 20:10

Девушка, почитайте вот Бинарное дерево.
Там рассмотрены алгоритм поиска и удаления узла из дерева.
В коде вашем разобраться сложновато, но скорее всего у вас не совсем правильны функции поиска и удаления.

ПыСы: замечания по коду - напишите конструктор в структуре link
вот к примеру так

Код:

link::link(int value)
:data(value),
left(NULL),
right(NULL)
{
}

это избавит вас от вот этого

Код:

neo = new link;
   neo->data=arg;
   neo->left=NULL;
   neo->right=NULL;

Этот код с помощью конструктора заменяется на

Код:

link *neo = new link(arg);

так просто читабельнее будет.

Барби · 24.12.2008, 21:10

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

MaTBeu · 24.12.2008, 21:51

О, такое задание было в книге Дейтелов "Как программировать на С++"!
Выводить дерево как оно рисутется.
Я это задание так и не сделал, но я вам скажу - прийдется использовать такую структуру как дек тоесть типа очереди, только добалять можно и в начало и в конец. Типа добавляете узел и его двух потомков - выводите, потом другой узел и его потомков, и так постепенно спускаетесь в самый низ одной ветки. Потом тоже самое для другой ветки.

ПыСы: сори, если непонятно, я сам не сильно понимаю, что говорю

И я тоже хочу узнать решение

Барби · 24.12.2008, 22:19

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

Код:

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
typedef
 struct link
     {
      int data;
      link *left;
      link *right;
     };

class tree
{
 public:
   link *r;
   int m;
   int x;
   int depth;
   int minim;
   int c;
   int d;

link *Find(link* &Root, int a);
void add(link* &n,int arg);
void restruct(link * v);
void delete1(link *n,int arg);
void view(link* &n, int d);
void obhod1(link* &n, int *d1,int *min);
void obhod2(link* &n, int *d1,int min);
};

class bintree: public tree
{
 public:
 int  walk[100];

void Go(link *t,int y[], int &j);
};

link * tree::Find(link* &Root, int a)
    {
	if (Root == NULL) return(NULL);
	else
		if (a == Root->data) return(Root);
		else
			if (a < Root->data) return(Find(Root->left, a));
			else return(Find(Root->right, a));
    };

void bintree::Go(link *t,int y[],int &j)
{
  if (t!=NULL)
  {
    bintree::Go(t->left,y,j);
    {
      j++;
      y[j]=0;
    };
    bintree::Go(t->right,y,j);
    {
      j++;
      y[j]=1;
    };
  };
};



void tree::add(link* &n,int arg)
{
  link *ind;
  link *neo;
   neo = new link;
   neo->data=arg;
   neo->left=NULL;
   neo->right=NULL;
   if (n==NULL)  n = neo;
   else {
      ind=n;
      while (neo!=NULL) {
	 if (arg<ind->data)  {
	    if (ind->left==NULL)  {
	       ind->left=neo;
	       neo=NULL;
	    }
	    else ind=ind->left;
	 }
	 else
	    if (arg>ind->data)  {
	       if (ind->right==NULL)  {
		  ind->right=neo;
		  neo=NULL;
	       }
	       else ind=ind->right;
	    }
	    else {
	       puts("Such element is already exists");
	       neo=NULL;
	    };
      };
   };
}; /* add */

void tree::restruct(link *v)
{
  link *ind1;
  link *ind2;

   ind1=v;
   if (ind1->right==NULL)  {
      ind2=v;
      v=ind2->left;
      delete ind2;
   }
   else
      if (ind1->left==NULL)  {
	 ind2=v;
	 v=ind2->right;
	 delete ind2;
      }
      else {
	 ind2=ind1->left;
	 while (ind2->right!=NULL)  {
	    ind1=ind2;
	    ind2=ind2->right;
	 };
	 ind1->right=ind2->left;
	 ind2->left=v->left;
	 ind2->right=v->right;
	 delete v;
	 v=ind2;
      };
}; /* restruct */

void tree::delete1(link * n,int arg)
{
   link *del;
   link *ind;
   int t;

   t=0;
   del=n;
   while (del!=NULL && !t)  {
      if (arg==del->data)  t=1;
      else
	 if (arg<del->data)  {
	    ind=del;
	    del=del->left;
	 }
	 else {
	    ind=del;
	    del=del->right;
	 };
   };
      if (t)  {
	 if (del->left==NULL && del->right==NULL)  {
	    if (del==n)  { n=NULL; delete del; } else
	    if (ind->left==del)  {
	       ind->left=NULL;
	       delete del;
	    }
	    else {
	       ind->right=NULL;
	       delete del;
	    }
	 }
	 else
	    if (del==n)  restruct(n); else
	    if (ind->left==del)  restruct(ind->left);
	    else restruct(ind->right);
      }
      else puts("Element is absent");
}; /* delete */

void tree::view(link* &n, int d)
{
  int i;

   for (i=1; i<= d;i++) {
      printf("    "); };
   printf("%d\n",n->data);
   if (n->left==NULL && n->right==NULL)  d=d-1;
   else {
      if (n->right!=NULL)  {
	 d=d+1;
	 view(n->right,d);
      };
      if (n->left!=NULL)  {
	 d=d+1;
	 view(n->left, d);
      };
      d=d-1;
   };
}; /* view */

void tree::obhod1(link* &n, int *d1,int *min)
{
   if (n->left==NULL && n->right==NULL)  {
      if (d<*min)  *min=d;
      d=d-1; }
      else {
	 if (n->right!=NULL)  {
	    d=d+1;
	    obhod1(n->right, &d, min); };
	 if (n->left!=NULL)  {
	    d=d+1;
	    obhod1(n->left, &d,min); };
	d=d-1;
      };
}; /* obhod1 */

void tree::obhod2(link* &n, int *d1,int min)
{
   if (n->left==NULL && n->right==NULL)  {
      if (d==min)  printf("%d",n->data);
      d=d-1;
   }
   else {
      if (n->right!=NULL)  {
	 d=d+1;
	 obhod2(n->right,&d,min);
      };
      if (n->left!=NULL)  {
	 d=d+1;
	 obhod2(n->left, &d,min);
      };
      d=d-1;
   };
}; /* obhod2 */

Барби · 24.12.2008, 22:20

Код:

void main(void)
{
int temp,m,x,c,d,i;
bintree *pn,*pn1;
int flag;
   clrscr();
   m=1;
   temp=1;
   pn->r=NULL;pn1->r=NULL;
   while (m!=0) {
      printf("\n");
      printf("--- Type 1 to ADD new element\n");
      printf("--- Type 2 to DELETE element\n");
      printf("--- Type 3 to VIEW tree\n");
      printf("--- Type 4 to FIND elements with minimal depth\n");
      printf("--- Type 5 to TURN another tree\n");
      printf("--- Type 6 Equal?\n");
      printf("--- Type 7 Find element\n");
      printf("--- Type 0 to EXIT program\n");
      printf("\n");
      printf("Enter : ");
      scanf("%d",&m);
      printf("\n");
      switch (m){
       case	1 : {
	       printf("Enter new element : ");
	       scanf("%d",&x);
	       if(temp==1)   pn->add(pn->r, x);
		  else  pn1->add(pn1->r,x);
	    };break;
	case 2 : {
	       printf("Enter element you want to delete : ");
	       scanf("%d",&x);
	       if (temp==1)  pn->delete1(pn->r, x);
		  else pn->delete1(pn1->r,x);
	    };break;
     case	3 : {
	       if (temp==1)   {
		    pn->depth=1;
		    if (pn->r==NULL)  printf("The tree is empty"); else {
		    printf("The tree is : \n");
		    pn->view(pn->r, pn->depth);
		    };
		    }
		  else {
			 pn1->depth=1;
			if (pn1->r==NULL)  printf("The tree is empty"); else {
			printf("The tree is : \n");
			pn1->view(pn1->r, pn1->depth);

		       };
	       };
	    };break;
   case	4 : {
	     if (temp==1)  {
	       pn->depth=1;
	       pn->minim=20;
	       if (pn->r!=NULL)  {
	       printf("Elements with minimal depth");
	       pn->obhod1(pn->r,&pn->depth,&pn->minim);
		  printf("%d",pn->minim);
		  pn->depth=1;
		  pn->obhod2(pn->r,&pn->depth,pn->minim);
	       }
	       else printf("The tree is empty");
	      }
	     else {
		  if (pn1->r!=NULL)  {
		  printf("Elements with minimal depth");
		  pn1->obhod1(pn1->r,&pn1->depth,&pn1->minim);
		  printf("%d",pn1->minim);
		  pn1->depth=1;
		  pn1->obhod2(pn1->r,&pn1->depth,pn1->minim);
		  }
		    else printf("The tree is empty");
		  };
	    };break;
      case	5: {
	    if (temp==1)  {
			    temp=2;
			    printf("Current 2\n");
			   }
	       else {
		     temp=1;
		     printf("Current 1\n");
		    };
	   }; break;
      case	6: {
	   c=0;d=0;
	   pn->Go(pn->r,pn->walk,c);
	   pn1->Go(pn1->r,pn1->walk,d);
	   if (c==d)  {
		       flag=1;
		       for (i=1;i<= c;i++)
			 if (pn1->walk[i]!=pn->walk[i])  flag=0;
		       if (flag)  printf("Equal\n");
			  else printf("No\n");
		       }
	      else printf("No\n");

	   }; break;
      case	7:{
	   printf("Enter  element to Find: ");
	   scanf("%d",&x);
	   if (temp==1)  {
			  if (pn->Find(pn->r,x) != NULL)  printf("Yes\n");
			     else printf("No\n");
			  }
	      else {
		    if (pn1->Find(pn1->r,x)!= NULL)  printf("Yes\n");
		       else printf("No\n");
		   };
	  }; break;
      }; /* case */
   };
    }

24.12.2008, 20:10	#3
MaTBeu Eclipse Foundation Старожил Регистрация: 19.09.2007 Сообщений: 2,604	Девушка, почитайте вот Бинарное дерево. Там рассмотрены алгоритм поиска и удаления узла из дерева. В коде вашем разобраться сложновато, но скорее всего у вас не совсем правильны функции поиска и удаления. ПыСы: замечания по коду - напишите конструктор в структуре link вот к примеру так Код: `link::link(int value) :data(value), left(NULL), right(NULL) { }` это избавит вас от вот этого Код: `neo = new link; neo->data=arg; neo->left=NULL; neo->right=NULL;` Этот код с помощью конструктора заменяется на Код: `link *neo = new link(arg);` так просто читабельнее будет.

24.12.2008, 21:10	#4
Барби Форумчанин Регистрация: 19.12.2007 Сообщений: 159	поиск получилось поправить, с удалением пока никак. у как сделать чтоб выводилось как бы домиком илипирамидкой, чтобы узел а подним две ветки апод ветками их ыетки ну или как то чтоб не в строку а чтоб показать где узел а где ветки? Пока ремонтируют кукольный домик, живу на форуме.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Поиск однофамильцев в программе	Lemo	Помощь студентам	2	11.11.2008 01:17
Бинарное дерево, нид хэлп	Roman-S	Общие вопросы C/C++	4	24.04.2008 14:24
Бинарное дерево	g0liath	Помощь студентам	2	16.02.2008 23:54

24.12.2008, 21:51	#5
MaTBeu Eclipse Foundation Старожил Регистрация: 19.09.2007 Сообщений: 2,604	О, такое задание было в книге Дейтелов "Как программировать на С++"! Выводить дерево как оно рисутется. Я это задание так и не сделал, но я вам скажу - прийдется использовать такую структуру как дек тоесть типа очереди, только добалять можно и в начало и в конец. Типа добавляете узел и его двух потомков - выводите, потом другой узел и его потомков, и так постепенно спускаетесь в самый низ одной ветки. Потом тоже самое для другой ветки. ПыСы: сори, если непонятно, я сам не сильно понимаю, что говорю И я тоже хочу узнать решение