Вопрос(бин.дерево)

[mike_tihomirov]

решаю примеры из задачника.(просто для себя)
Есть бин.дерево.(код с пояснениями ниже)
1 проблема: если я удаляю ветку, то потом не могу удалить все дерево.
2: никак не придумаю как удалить только узел, т.е. надо сохранить
наследников удаляемого узла и потом поменять связи с предком удаляемого узла.
3:и еще хотелось бы заменить все рекурсии итерациями.
Мож дадите хоть итеративный пример вставки, а там уж я как нить сам
соображу.
ps: вопросы улучшения кода мне добалды, я еще не на том уровне.

//------------------
struct Node
{
	int Var;
	Node* pPrev;
	Node* pLeftChild;
	Node* pRightChild;
	int Level;
};
//------------------
class Tree
{
private:
	Node* pNode;
public:
	Tree();
	Tree(int);
	~Tree();
public:
	bool Insert(int var);
	bool DeleteBranch(int var);
	bool DeleteTree();
	bool FindNode(int var);
private:
	bool _Insert(int var, Node*& pN, Node* parent, int level);
	bool _DeleteBranch(Node* pN);
	Node* _FindNode(int var, Node* pN);
};
//-----------------CONSTRUCTOR
Tree::Tree(){pNode = 0;}
//------------------
Tree::Tree(int var)
{
	pNode = new Node;
	pNode->Var = var;
	pNode->pPrev = 0;
	pNode->pLeftChild = 0;
	pNode->pRightChild = 0;
	pNode->Level = 0;
}
//------------------DESTRUCTOR
Tree::~Tree()
{
	if(pNode != 0)
		DeleteTree();
}
//------------------INSERT
bool Tree::Insert(int var)
{
	_Insert(var, pNode, 0, 0);

	return 0;
}
//------------------
bool Tree::_Insert(int var, Node*& pN, Node* parent, int level)
{
	if(pN == 0)
	{
		pN = new Node;
		pN->Var = var;
		pN->pPrev = parent;
		pN->pLeftChild = 0;
		pN->pRightChild = 0;
		pN->Level = level;
	}
	else
	{
		if(var < pN->Var)
		{
			_Insert(var, pN->pLeftChild, pN, level + 1);
		}
		else
		{
			_Insert(var, pN->pRightChild, pN, level + 1);
		}
	}
	return 0;
}
//------------------FINDNODE
bool Tree::FindNode(int var)
{
	Node* temp;
	temp = _FindNode(var, pNode);
	if(temp)
		return true;
	return false;
}
//------------------
Node* Tree::_FindNode(int var, Node* pN)
{
	Node* tempP;
	if(!pN || pN->Var == var)
		return pN;
	tempP = _FindNode(var, pN->pLeftChild);
	if(tempP)
		return tempP;
	return _FindNode(var, pN->pRightChild);
}
//------------------DELETEBRANCH
bool Tree::DeleteBranch(int var)
{
	_DeleteBranch(_FindNode(var, pNode));
	return 0;
}
//--------------------
bool Tree::_DeleteBranch(Node* pN)
{
	if (pN == NULL) 
		return 0;

	_DeleteBranch(pN->pLeftChild);
	_DeleteBranch(pN->pRightChild);
	
	//здесь как то надо присвоить NULL 
	//наследнику узла родителя
	//к примеру удаляем "1" тогда у "4"
	//должен pLeftChild = 0;
	//или "7" тогда pRightChild = 0;
	//штука в том что, если удаляем "11" т.е. корень
	//то у него то родителя нет!

	delete pN;

	return 0;
}
//--------------------DELETETREE
bool Tree::DeleteTree()
{
	_DeleteBranch(pNode);
	return 0;
}
//--------------------MAIN
int _tmain(int argc, _TCHAR* argv[])
{
	//к примеру
	Tree* tr = new Tree;

	tr->Insert(11);
	tr->Insert(8);
	tr->Insert(17);
	tr->Insert(4);
	tr->Insert(7);
	tr->Insert(13);
	tr->Insert(9);
	tr->Insert(28);
	tr->Insert(1);
	//----------
	tr->DeleteBranch(1);
	//----------
	//tr->DeleteTree();
	return 0;
}

[Nikita1987]

#include "stdafx.h"
#include <iostream>
#include <time.h>


using namespace std;
struct Elem
{
   char  key;		// данные
   Elem * left, * right, * parent;
};

class Tree
{
   // корень
   Elem * root;
public:
   Tree();
   ~Tree();
   // печать от указанного узла
   void Print(Elem * Node);
   // поиск от указанного узла
   Elem * Search(Elem * Node, int _key);
   // min от указанного узла
   Elem * Min(Elem * Node);
   // max от указанного узла
   Elem * Max(Elem * Node);
   // следующий для указанного узла
   Elem * Next(Elem * Node);
   // предыдущий для указанного узла
   Elem * Previous(Elem * Node);
   // вставка узла
   void Insert(Elem * z);
   // удаление ветки для указанного узла, 
   // 0 - удаление всего дерева
   void Del(Elem * z = 0);
   // получить корень
   Elem * GetRoot();
};

Tree::Tree()
{
   root = NULL;
}

Tree::~Tree()
{
   Del();
}

// Рекурсивный обход дерева
void Tree::Print(Elem * Node)
{
   if(Node != 0)
   {
      Print(Node->left);
      cout << Node->key << endl;
      Print(Node->right);
   }
}
Elem * Tree::Search(Elem * Node, int _key)
{
   // Пока есть узлы и ключи не совпадают
   while((Node != NULL) && (_key != Node->key))
   {
      if(_key < Node->key)
         Node = Node->left;
      else
         Node = Node->right;
   }
   return Node;
}

Elem * Tree::Min(Elem * Node)
{
   // Поиск самого "левого" узла
   if(Node != 0)
      while(Node->left != 0)
         Node = Node->left;
	
   return Node;
}

Elem * Tree::Max(Elem * Node)
{
   // Поиск самого "правого" узла
   if(Node != 0)
      while(Node->right != 0)
         Node = Node->right;
	
   return Node;
}

Elem * Tree::Next(Elem * Node)
{
   Elem * y = 0;
   if(Node != 0)
   {
      // если есть правый потомок
      if(Node->right != 0)
         return Min(Node->right);
		
      // родитель узла
      y = Node->parent;
      // если Node не корень и Node справа
      while(y != 0 && Node == y->right)
      {
         // Движемся вверх
         Node = y;
         y = y->parent;
      }
   }
   return y;
}

Elem * Tree::Previous(Elem * Node)
{
   Elem * y = 0;
   if(Node != 0)
   {
      // если есть левый потомок
      if(Node->left != 0)
         return Max(Node->left);
		
      // родитель узла
      y = Node->parent;
      // если Node не корень и Node слева
      while(y != 0 && Node == y->left)
      {
         // Движемся вверх
         Node = y;
         y = y->parent;
      }
   }
   return y;
}

Elem * Tree::GetRoot()
{
   return root;
}

void Tree::Insert(Elem * z)
{
   // потомков нет
   z->left = NULL;
   z->right = NULL;

   Elem * y = NULL;
   Elem * Node = root;

   // поиск места
   while(Node != NULL)
   {
      // будущий родитель
      y = Node;
      if (z->key < Node->key)
         Node = Node->left;
      else
         Node = Node->right;
   }
   // заполняем родителя
   z->parent = y;

   if(y == NULL) // элемент первый (единственный)
      root = z;
   // чей ключ больше?
   else
   {
		if (z->key < y->key)
			y->left = z;
		else
			y->right = z;
	}
}

void Tree::Del(Elem * z)
{
   // удаление куста
   if(z != 0)
   {
      Elem * Node, * y;

      // не 2 потомка
      if(z->left == 0 || z->right == 0)
         y = z;
      else
         y = Next(z);

      if(y->left != 0)
         Node = y->left;
      else
         Node = y->right;

      if(Node != 0)
         Node->parent = y->parent;
      // Удаляется корневой узел?
      if(y->parent == 0)
         root = Node;
      else if(y == y->parent->left) // слева от родителя?
         y->parent->left = Node;
      else
         y->parent->right = Node;  // справа от родителя?
		
      if(y != z)
      {
         // Копирование данных узла
         z->key = y->key;
      }

      delete y;
   }
   else // удаление всего дерева
      while(root != 0)
         Del(root);
}

Думаю разберешься

[mike_tihomirov]

Nikita1987
Спасибо.

[mike_tihomirov]

Чтоб не поднимать новой темы, задам доп. вопрос в этой.
Рекурсивный обход дерева это ясно, а вот как обойти без рекурсии.
У Кормена этого нет.
Я полагаю надо свой стек реализовать, так? это можно.
Но чето в башке не могу до кучи собрать.

[dxdy]

mike_tihomirov, да, можно обойтись без рекурсии. Все можно реализовать через стек, но один из случаев обхода даже удобнее было реализовать через очередь. Если хочешь, то у меня на компьютере где-то лежали исходники, помню это у меня была лабораторная работа по этой теме. Даже очередь и стек тогда реализовал через списки по требованию преподавателя.

[mike_tihomirov]

Здравсвуйте dxdy. Если можно киньте примеры на мыло mike_tihomirov@mail.ru
Заранее спасибо.