tree.cpp

#include <iostream>

using namespace std;

struct element //элемент стека на списке
{
  int value;
  element* next;

  element(int value, element* next)
  {
	  this->value = value;
	  this->next = next;
  }
};

class Stack //стек
{
public:
	Stack();
	~Stack();
	void push(int value); //add value
	int pop(); //delete top
	int top() const; //get top
	int full() const; //is full
	int empty() const; //is empty
private:
	element* head; //head of stack
};

Stack::Stack()
{
	head = 0;
}

Stack::~Stack()
{
	element* p = head;
	while (head) {
		head = head->next;
		delete p;
		p = head;
	}
}

void Stack::push(int value)
{
	head = new element(value, head);
}

int Stack::pop()
{
	int x = head->value;
	element* temp = head;
	head = head->next;
	delete temp;
	return x;
}

int Stack::top() const
{
	return head->value;
}

int Stack::full() const
{
	return 0;
}

int Stack::empty() const
{
	return head == 0;
}

namespace tree_list {

  struct Child
  {
	Child(int n, Child* s) :name(n), sibling(s) { }
	int name; //имя сына
	Child* sibling; //указатель на правого брата
  };

  struct Node
  {
	char mark; //метка
	int next; //указатель на ячейку массива для списка свободных
	Child* child; //указатель на список сыновей
  };

  class tree
  {
  public:
	  tree() { root = -1; }
	  ~tree() { reset(); }
	  tree& create0(char m);//создаем узел-результат с меткой m, вызывается на пустом дереве (неявно)
	  tree& create(char m);//сливаем новый узел с деревом, на к. вызываем, новый узел - корень дерева с 1 поддеревом
	  tree& create(char m, tree& T);//создает дерево слиянием узла и дерева, новый узел стан корнем, В дерево
	  int get_root();//Возвращает корень дерева, если его нет - пустое дерево
	  int get_parent(int n);//Возвращает родителя узла. Если это корень - вернет пустое дерево
	  int left_most_child(int n);//Возвращает самого левого сына узла, если узел - лист, В пустое дерево
	  int right_sibling(int n);//Возвращает правого брата, если его нет - пустое дерево
	  char get_mark(int n);//Возвращает метку узла
	  void reset();//делает дерево пустым
	  static void init();//инициализация массива для курсоров
  private:
	  int root;
	  static const int size = 10;
	  static Node list[size];//	массив узлов, номер узла - его индекс в массиве
	  static int SPACE;
	  int search(int x);//Поиск узла. Вернет индекс родителя или -1, если узла нет
	  void remove(int n);//Помещение узла в список свободных
	  int add(char mark, Child* срш);//Перемещение узла из списка свободных  назначением потмка с
	  int search_sibling(int parent, int x);//Поиск в списке сыновей правого брата по родителю и левому брату
  };

  Node tree_list::tree::list[size];
  int  tree_list::tree::SPACE;

  /* *
   * Инициализация ячеек
   * */
  void tree::init()
  {
	  SPACE = 0;
	  for (int i = 0; i<size-1; i++)
		  list[i].next = i+1;
	  list[size-1].next = -1;
  }

  /* *
   * Создаем узел с меткой. Вызывается на пустом дереве
   * */
  tree& tree::create0(char m)
  {
	  root = add(m, 0);
	  return *this;
  }
/*
 * сливаем новый узел с деревом, на котором вызываем
 * новый узел - корень дерева с одним поддеревом
 * */
  tree& tree::create(char m)
  {
	  Child* c = new Child(root, 0); //элемент-сын из корня
	  root = add(m, c); //старый корень становится сыном
	  return *this;
  }

  /*
   * Создаем узел-корень. Дерево, на котором вызываем - левый потомок, а дерево, которое передаем - правый потомок
   */
  tree& tree::create(char m, tree& T)
  {
	  Child* c2 = new Child(T.root, 0);  //Элемент-сын из корня2
	  Child* c1 = new Child(root, c2); // Элемент-сын из корня1
	  root = add(m, c1);
	  return *this;
  }
/* *
 * Вставка в свободное место
 * Вернет указатель(индекс) на вставленный элемент
 * */
  int tree::add(char mark, Child* child) {
	  int n = SPACE; //место под новый узел
	  SPACE = list[SPACE].next; //меняем указатель на свободное место
	  list[n].child = child; //ставим новый узел выше предыдущего
	  list[n].mark = mark;
	  return n; //возвращаем указатель на вставленный элемент
  }

  /* Возвращает корень дерева, на котором вызван метод */
  int tree::get_root()
  {
	  return root;
  }

  /* Есть ли в списке сыновей у определенного сына - брат (по родителю и левому брату поиск)
   * Если есть, вернуть этого брата. Если нет - то вернуть '-1' */
  int tree::search_sibling(int parent, int x)
  {
	  Stack stk;
	  int current_parent = root;
	  int current_child = list[root].child->name;
	  while (current_parent != parent)
	  {
		  current_parent = current_child;
		  current_child = list[current_child].child->name;
	  }

//	  Child* n = list[parent].child; //указатель на левого сына
//	  while (n->name != x) //пока не найдем текущий элемент
//		  n = n->sibling; //идем правее по дереву
//	  if (n->sibling) //если есть брат
//		  return n->sibling->name;
//	  return -1;
  }

  /*
   * Поиск узла.
   * Возвращает указатель на узел
   * Если узла нет, возвращает '-1'
   * */
  int tree::search(int x)
  {
	  Stack s;
	  int current_node = root;
	  int parent = -1;
	  int sibling = -1;

//	  Если у корня есть потомок, то начинаем поиск с него, т.к. у корня нет братьев
	  if (!list[root].child)
		  return -1;

//	  Готовим начальные элементы к поиску 'x' в дереве
	  s.push(root); //т.к. уже проверили корень дерева, то сразу добавляем в стек
	  parent = current_node; //родителем для следующего шага становится текущий элемент (корень)
	  current_node = list[root].child->name; //сдвигаем текущий элемент "вниз и влево"

//	  Собственно ищем 'x' в дереве
	  do {
		  if (current_node == x) //Если текущий узел - нужный узел, то возвращаем его родителя и выходим из функции
			  return parent;

//		  Ищем узел
		  sibling = search_sibling(parent, current_node); //правый брат текущего элемента
		  if (sibling != -1) //если есть брат
		  {
			  s.push(current_node); //добавляем в стек
			  current_node = sibling; //переходим к брату
		  }
		  else
		  {
			  while (!s.empty()) //пока не поднялись по дереву к корню
			  {
				  if (list[current_node].child) //если есть потомок, то переходим к левому сыну
				  {
					  parent = current_node;
					  current_node = list[current_node].child->name;
					  break; //выходим из цикла
				  }
				  else current_node = s.pop(); //больше никаких связей нет, топоднимаемся на уровень
			  }
		  }
	  }
	  while (current_node != root);
	  return -1; //узел не найден
  }

  int tree::get_parent(int n)
  { //возвращает самого левого сына узла, если узел - лист, вернет пустое дерево
	  if (root == n) //у корня нет родителя
		  return -1;
	  if (root == -1 || list[n].child == 0) //для проверки нужно хотя бы 2 узла
		  return -1;
	  return search(n); //	возвращает родителя или -1, если узел не найден
  }

  int tree::left_most_child(int n)
  {
	  if (root == n) //искомый узел - корень, поиск не нужен
		  return list[n].child->name;
	  if (root == -1 || list[n].child == 0) //для проверки нужно хотя бы 2 узла
		  return -1;
	  if (search(n) != -1) //узел найден
		  return list[n].child->name;
	  return -1;
  }

  int tree::right_sibling(int n)
  {
	  if (root == n) //у корня нет братьев
		  return -1;

	  if (root == -1 || list[root].child == 0) //для проверки нужно хотя бы 2 узла
		  return -1;

	  int p = search(n);
	  if (p != -1) //если есть родитель, то возвращаем правого брата (если есть)
		  return search_sibling(p, n);

	  return -1; //если нет ни брата, ни узла
  }

  char tree::get_mark(int n)
  {
	  if (root == n)
		  return list[n].mark;

	  if (root == -1)
		  return '\0';

	  if (list[root].child == 0)
		  return '\0';

	  if (search(n) != -1)
		  return list[n].mark;

	  return '\0';
  }

  void tree::remove(int n)
  {
	  list[n].next = SPACE;
	  SPACE = n;
  }

  void tree::reset()
  {
	  if (root == -1)
		  return;

	  Stack s;
	  int n = root, p = -1, sib = -1;

	  if (list[root].child) //если у корня есть потомок, то начинаем с него
	  {
		  s.push(root);
		  p = n;
		  n = list[root].child->name;
	  }
	  else return;

	  do {
		  sib = search_sibling(p, n);
		  if (sib != -1) //есть брат
		  {
			  s.push(n);
			  n = sib; //переходим к брату
		  }
		  else
			  while (!s.empty()) //пока не поднялись к корню
			  {
				  if (list[n].child) //если есть потомок, то переходим к левому сыну
				  {
					  p = n;
					  n = list[n].child->name;
					  break;
				  } //больше никаких связей нет
				  remove(n);
				  n = s.pop();//	подимаемся выше на уровень
			  }
	  }
	  while (n != root);
	  remove(root);
	  root = -1;
  }

}

using namespace tree_list;

//вывод дерева слева направо
void print_tree(tree& T)
{
	if (T.get_root() == -1)
		return;

	cout << "> ";

	Stack s;
	int name = T.get_root(), p;

	do {
		if (T.left_most_child(name) != -1) //если потомок слева есть
		{
			s.push(name); //добавляем его в стек
			name = T.left_most_child(name); //спускаемся на уровень ниже
		}
		else //если потомка нет
		{
			cout << name << "(" << T.get_mark(name) << ") ";
			while (name != T.get_root()) {
				if (name == T.left_most_child(s.top())) //если узел - левый сын, то выведем родителя (чтобы вывести 1 раз)
					cout << s.top() << "(" << T.get_mark(s.top()) << ") ";
				if (T.right_sibling(name) != -1) //есть правый брат
				{
					name = T.right_sibling(name); //переходим к брату
					break; //выходим во внешний цикл
				}
				else
					name = s.pop(); //поднимаем все на уровень выше
			}
		}
	}
	while (name != T.get_root());
	cout << endl;
}

int main(void)
{
	tree::init();
	tree T, T1, T2, T3, T4;
	T.create0('c');
	T.create('d');
	cout << "T: c + d" << endl;
	print_tree(T);
	T1.create0('f');
	cout << "T1: f" << endl;
	T.create('e', T1);
	cout << "T: e + T1\n";
	print_tree(T);
	T2.create0('a');
	cout << "T2: a" << endl;
	T2.create('b', T);
	cout << "T2: b + T" << endl;
	print_tree(T2);
	T3.create0('h');
	cout << "T3: h\n";
	T4.create0('j');
	cout << "T4: j\n";
	T3.create('i', T4);
	cout << "T3: i + T4";
	print_tree(T3);
	T2.create('g', T3);
	cout << "T2: g + T3" << endl;
	print_tree(T2);
	return 0;
}