ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Бинарное дерево поиска!! пожалуйста, помогоите!!!
3 сообщений из 3, страница 1 из 1
Бинарное дерево поиска!! пожалуйста, помогоите!!!
    #33287019
Andrey_Ohotin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Andrey_Ohotin
Гость
Привет!!! Помогите пожалуйста!! у меня задание.. я все написал, кроме функции удаления в бинарном дереве поиска.. (без повоторяющихся элементов) ..
Узел такой:

Код: plaintext
1.
2.
3.
4.
5.
 struct Node
		  {
			  int d;         //Переменная, в которой храним значения узлов в дереве.
			  Node* left;    //Указатели для перемещения по дереву влево.
			  Node* right;   //И вправо.
		  };

Вот функция удаления, реализована частично.. короче говоря практически никак нереализована.. "одно название" ... помогите пожалуйста..
Как удалять листья - я написал.. а вот как удалять к примеру корень.. может вы знаете? или знаете где есть пример.. очень ннужно!!!
... заранее ОГРОМНОЕ спасибо, а то я уже неделю сижу над этой функцией...

Код: plaintext
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.
 Node* search_delete(Node* root)
			  {
				  printf("| %s ",Rus("Введите ключ для удаления:"));
				  int d;
				  cin>>d;
				  Node* pv = root;
				  Node* prev;
				  bool found = false;			  
				  bool side = true;     //Флаг, для определения, с какой стороны удалять узел.
				  while(pv && !found)
				  {				  				  
					  if(d == pv->d)    //Если мы нашли элемент по заданному ключу, то проверяем дальше:
					  {
						  printf("| %s\n",Rus("Ключ найден и удален из дерева."));
						  if((pv->left == NULL) && (pv->right == NULL))  //Если у удаляемого элемента нет потомков, то просто удаляем его.
						  {						  
							  Node* dkey = new Node;
							  dkey = pv;
							  if(side)
							  {
								  prev->left =  0 ;
								  delete dkey;	
							  }
							  else
							  {
								  prev->right =  0 ;
								  delete dkey;
							  }							  
						  }
						  else if(pv->right)  //Если у элемета предка есть потомок справа, то необходимо найти минимальный элемент справа от предка.
						  { 
							 Node *ptr = pv;
							 ptr = ptr->right;
							 if(ptr->left == NULL)
							 {
								 if((ptr->right != NULL) && (ptr->left == NULL))
								 {
									 Node *cur = pv;
									 ptr->left = pv->left;
									 cur->right = ptr->right;
									 
									 ptr->right = cur->right;
									 pv->d = ptr->d;
									 pv->left = ptr->left;
									 pv->right = ptr->right;		

									 cur =  0 ;
                                     delete cur;									 
								 }		
								 else if((ptr->right == NULL) && (ptr->left == NULL))
								 {									 
									 pv->d = ptr->d;
									 pv->right =  0 ;
								 }
								 else if((ptr->right == NULL) && (ptr->left != NULL))
								 {

								 }
							 }
							 
							 delete ptr;							 
						  }
						  found = true;   
					  }
					  else if(d < pv->d)
					  {
						  side = true;
						  prev = pv;
						  pv = pv->left;  
					  }
					  else        
					  {
						  side = false;
						  prev = pv;
						  pv = pv->right; 
					  }				  
				  }
				  if(!found)
				  {
					  printf("| %s",Rus("Ключ в дереве не найден."));
				  }
				  return pv; 			 
			  }
...
Рейтинг: 0 / 0
24.09.2005, 08:45
| Ответить | Цитировать | Написать  
Бинарное дерево поиска!! пожалуйста, помогоите!!!
    #33287622
Фотография Анатолий Широков
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Анатолий Широков
Участник
Код: plaintext
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.
122.
123.
124.
125.
126.
127.
128.
#include <iostream>

struct node
{
	int key;
	node* lft;
	node* rgt;
	node(int key) : key(key), lft( 0 ), rgt( 0 )
	{
	}
	~node()
	{
		delete lft;
		delete rgt;
	}
	bool isleaf() const
	{
		return (lft == rgt) && (lft == NULL);
	}
};

node* destroy(node *n)
{
	//	дерево состоит из одной вершины
	if( n->isleaf() )
	{
		delete n; 
		return  0 ;
	}
	else
	//	левое поддерево пусто
	if( n->lft ==  0  )
	{
		//	сохраняем указатель на правое поддерево
		node* r = n->rgt;
		//	копируем состояние узла находящегося справа
		*n = *r;
		//	удаляем узел
		r->lft =  0 ;
		r->rgt =  0 ;
		delete r;
	} 
	else
	//	левое поддерево не пусто
	{
		//	ищем узел являющийся самым правым в левом поддереве
		//	самый правый узел
		node *c = n->lft;
		//	родитель самого правого узла 
		node *p = n->lft;
		
		//	двигаемся по правой ветви левого поддерева
		while( c->rgt )
		{
			p = c;
			c = c->rgt;
		}

		//	левое поддерево самого правого узла становиться правым поддеревом родителя
		p->rgt = c->lft;
		//	рвем отношение
		c->lft = NULL;
		//	переносим ключ
		n->key = c->key;
		//	удаляем самый правый узел
		delete c;
	}
	return n;
}

node* remove(node *n, int key)
{
	//	если достигли листа, то узла с данным ключем не существует
	if( n == NULL )
		return  0 ;
	//	если ключ текущего узла меньше искомого
	if( n->key < key )
	{
		//	идем по правой ветке
		n->rgt = remove(n->rgt, key);
		return n;
	}
	else
	//	если ключ текущего узла больше искомого
	if( key < n->key )
	{
		//	идем по левой ветке
		n->lft = remove(n->lft, key);
		return n;
	}
	//	ключ текущего узла равен искомому
	return destroy(n);
}

void print(node *n, int l =  0 )
{
	if( n )
	{
		print(n->rgt, l+ 2 );
		std::cout << std::string(l, ' ') << n->key << '\n';
		print(n->lft, l+ 2 );
	}
}

int main()
{
             // исходное дерево
	node *tree = new node( 10 );
	tree->lft = new node( 5 );
	tree->lft->rgt = new node( 8 );
	tree->lft->rgt->lft = new node( 6 );
	tree->rgt = new node( 15 );
             // исходное дерево
	print(tree);
             // последовательно удаляем каждый элемент дерева
	remove(tree,  10 );
	print(tree);
	tree = remove(tree,  6 );
	print(tree);
	tree = remove(tree,  5 );
	print(tree);
	tree = remove(tree,  8 );
	print(tree);
	tree = remove(tree,  15 );
	print(tree);
	delete tree;

	return  0 ;
}

Удачи!

ps:Ваш код не разбирал, поэтому, что в нем не так не знаю.
...
Рейтинг: 0 / 0
25.09.2005, 23:58
| Ответить | Цитировать | Написать  
Бинарное дерево поиска!! пожалуйста, помогоите!!!
    #33305138
AndreyYY
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreyYY
Гость
Большое спасибо!!! ))) правда я уже кое-как справился с этим.. но Ваш код занимает меньше пространства.. )))
...
Рейтинг: 0 / 0
05.10.2005, 07:27
| Ответить | Цитировать | Написать  
3 сообщений из 3, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Бинарное дерево поиска!! пожалуйста, помогоите!!!
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=57&msg=33305138&tid=2032688]:
 0ms
get settings:
 11ms
get forum list:
 21ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 28ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 60ms
get tp. blocked users:
 2ms
others: 248ms
total:  391ms
созд. / загр.: 391ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]