Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Контейнер для хранения дерева

Автор: RAN 7.9.2003, 05:05

http://forum.vingrad.ru/index.php?act=ST&f=1&t=12249 тема навеяла мысль создать контейнер для хранения данных в виде дерева. Вот я и набросал, если так можно сказать, односвязное дерево. Это значит, что движение возможно лишь от корня и от первого элемента, но не в обратных порядках.

Итак, описание
tree<T> Tree; - создаёт контейнер дерева, который хранит элементы типа T
tree<T>::iterator i; - объявляем итератор (на самом деле над ним надо работать, он не функционирует пока как итератор)
Tree.addChild(T x); - добаляет новый элемент в корень дерева
Tree[0].addChild(T x); - добаляет новое детё первому элементу в корне дерева
Tree[0].addNext(T x); - раздвинуть элементы и впихнуть после Tree[0] новый элемент
i->push_back(T x); - Добавить элемент в конец, на том же уровне, что и итератор i. Не совсем традиционно, будем думать.
Новигация
i->getNext(); - Если i - это итератор, то оператор вернёт следующий элемент, того же уровня, или ноль если последний. Оператор ++ пока не работает
i->getChild(); - Ну, а это детё, или ноль, если детей нет

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

Вот файл определения контейнера:
tree.h

Код


template <class T> class tree_item;

template <class T>
class tree {
private:
	tree_item<T>* root;
public:
	tree() { root = 0; }
	~tree() { delete root;	}
	typedef tree_item<T>* iterator;
	typedef tree_item<T>& reference;
	
	iterator addChild(const T a)
	{
  if(root == 0)
  {
  	root = new tree_item<T>(a);
  	return root;
  }
  else
  	return root->push_back(a);
	}


	reference operator[](unsigned i)
	{
  tree_item<T> *item = root;
  while(i--)
  	item = item->getNext();
  return *item;
	}
};

template <class T>
class tree_item {
private:
	tree_item *nextItem, *childItem;
	T data;
public:
	tree_item(const T a) { nextItem = 0; childItem = 0; data = a; }
	
                //Деструктор интересный получился. Мне нравится.
                ~tree_item()
	{
  if(childItem) delete childItem;
  if(nextItem) delete nextItem;
	}
    
                tree_item& operator=(const T x) { data = x; return *this; }
	operator T() { return data; }

	tree_item& operator[](unsigned i)
	{
  tree_item *item = childItem;
  while(i--)
  	item = item->nextItem;
  return *item;
	}

	tree_item* addNext(const T a)
	{
  tree_item* item = new tree_item(a);
  item->nextItem = nextItem;
  nextItem = item;
	}
	
	tree_item* push_back(const T a)
	{
  tree_item *last = this;
  while(last->nextItem)
  	last = last->nextItem;
  last->nextItem = new tree_item(a);
  return last->nextItem;
	}

	tree_item* addChild(const T a)
	{
  if(childItem == 0)
  {
  	childItem = new tree_item(a);
  	return childItem;
  }
  else
  	return childItem->push_back(a);
	}

	inline tree_item* getNext() { return nextItem; }
	inline tree_item* getChild() { return childItem; }
};

Вот пример использования

Код


#include <iostream.h>
#include <string>
#include "tree.h"
using namespace std;

void print(tree<string>::iterator i);

void main()
{
	tree<string> Tree;
	
// Заполняем дерево (взял из книги по AutoCAD оглавление, рядом лежала)
	Tree.addChild("1. О системе AutoCAD 2002 в целом");
	Tree[0].addChild("1.1 Назначение системы");
	Tree[0].addChild("1.2 Требования к вычислительной среде");
	Tree[0].addChild("1.3 Установка системы");
	Tree[0][2].addChild("1.3.1 Для программиста");
	Tree.addChild("2. Элементы интерфейса");
	Tree[1].addChild("2.1 Строка меню");
	Tree[1][0].addChild("2.1.1 Меню File");

//Вывод на консоль
	print(&Tree[0]);
}

void print(tree<string>::iterator i)
{
	while(i)
	{
  cout << string(*i).c_str() << endl;
  if(i->getChild())
  	print(i->getChild());
  i = i->getNext();
	}
}

Вот. Надо класс итератора ещё написать, удаление реализовать. Потом можно будет контейнер двусвязный сделать и т.д.

Автор: mr.DUDA 7.9.2003, 10:23

RAN, я бы сначала поискал в Сети примерчики, может народ уже давно это реализовал. Но суть моего поста не в этом. А в том, что в STL уже реализовано дерево для "внутреннего потребления", т.е. для нужд других классов STL.

(Раньше здесь был БОЛЬШОЙ кусок кода из STL

)

Автор: mr.DUDA 7.9.2003, 10:27

ЗЫ, в STL от Хьюлетт Паккарда файлец называется "Xtree", в StlPort - это пара "_tree.h" и "_tree.c". Сбалансированное двоичное дерево (красный и черный "цвета" и прочее).

ЗЫ(2), это всё не ради выпендрёжа, просто реализацию произвольного дерева можно делать не с нуля, а взять куски STL'овского сорца. Особенно помочь это может в геморе с итераторами и пр.

ЗЫ(3), своего варианта пока что не придумал...

Автор: RAN 7.9.2003, 10:48

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

Автор: RAN 7.9.2003, 11:14

Цитата

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

http://cpp.hotmail.ru/prjct03_1.html, нашёл. А можно было самим реализовать

. Может лучше бы было