Содержание


Работа со структурами данных в языках Си и Python

Часть 5. Деревья

Comments

Серия контента:

Этот контент является частью # из серии # статей: Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Работа со структурами данных в языках Си и Python

Следите за выходом новых статей этой серии.

Начиная с этой статьи мы переходим от связных списков к изучению деревьев. Это не случайно, так оба эти типа структур данных построены на основе рекурсии. Фактически, связные списки являются подвидом деревьев, называемым вырожденным деревом. В данной статье будут рассмотрены общие принципы построения деревьев и различные варианты обхода узлов дерева.

Основные принципы

Первое появление концепции дерева в математике зафиксировано в середине 19-го века, а затем деревья стали использоваться в самых разных областях, например, в теории электрических цепей или химической изометрии. Использование древовидных структур в информационных технологиях началось с приложений для манипулирования алгебраическими формулами в 60-ых годах прошлого века, примерно тогда же появились традиционные алгоритмы для обхода деревьев.

В общем смысле, дерево - это иерархическая структура, хранящая коллекцию объектов. Деревья широко применяются в компьютерных технологиях, и самым близким примером является файловая система, представляющая собой иерархическую структуру из файлов и каталогов. Дерево (англ. tree) — это непустая коллекция вершин и ребер, удовлетворяющих определенным требованиям. Вершина (англ. vertex) — это объект, называемый также узлом (англ. node) по аналогии со списками, который может иметь имя и содержать другую информацию. Ключевое свойство дерева — между любыми двумя узлами существует только один путь, соединяющий их. Если между какой-либо парой узлов существует более одного пути или если между какой-либо парой узлов путь отсутствует, то подобная структура называется графом, а не деревом. Несвязанный набор деревьев называется лесом (англ. forest).

Для определения узлов существуют следующие сложившиеся термины:

  • root - узел, расположенный в корне дерева;
  • siblings - узлы, имеющие одного и того же родителя;
  • ancestor или parent – родительский узел;
  • descendant – дочерний узел;
  • size – размер узла, равный количеству дочерних узлов плюс один.

В рамках данной статьи будут обсуждаться деревья с произвольным количеством дочерних узлов. Упорядоченное (англ. ordered) дерево — это дерево с определенным корневым узлом, в котором также определен порядок следования дочерних узлов для каждого узла.

Деревья можно разделить на следующие категории:

  1. деревья без корня;
  2. деревья с корнем;
  3. упорядоченные деревья;
  4. м-арные и бинарные деревья.

На рисунке 1 показано, как оглавление книги можно представить в виде дерева. В показанном примере корневой узел имеет три поддерева – три главы, каждая из которых в свою очередь имеет свои подразделы.

Рисунок 1. Пример древовидной структуры
Рисунок 1. Пример древовидной структуры
Рисунок 1. Пример древовидной структуры

Путь (англ. path) - это последовательность узлов, которые нужно пройти, чтобы из корневого узла попасть в какой-либо дочерний узел. Длина пути равна числу узлов минус один. Высота (англ. height) - это путь от корня до наиболее удаленного узла. Например, на рисунке 1 высота поддерева часть № 1 равна единице, часть № 2 - двум, а высота поддерева часть № 3 равна нулю, так как оно не имеет дочерних узлов. Дочерние узлы обычно принять считать слева направо, но это можно делать в различном порядке. На рисунке 2 приведен пример дерева и результат использования трех различных подходов для обхода узлов.

Рисунок 2. Пример древовидной структуры
Рисунок 2. Пример древовидной структуры
  1. preorder – сверху-вниз-слева-направо: F, B, A, D, C, E, G, I, H;
  2. inorder – слева-вверх-вниз-вправо: A, B, C, D, E, F, G, H, I;
  3. postorder – обратное движение от детей к родителям: A, C, E, D, B, H, I, G, F.

Если сравнить древовидные структуры со связными списками, то станет понятно, что наибольшую сложность при работе с деревьями представляют динамические операции, такие как вставка и удаление узлов. Например, при удалении узла из бинарного дерева необходимо решить проблему наличия двух дочерних и одного родительского узла.

Рекурсивная реализация алгоритмов для обхода дерева

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

Листинг 1. Псевдокод алгоритмов для обхода дерева
preorder(node)
  print node.value
  if node.left ≠ null then preorder(node.left) 
  if node.middle ≠ null then preorder(node.middle) 
  if node.right ≠ null then preorder(node.right)

inorder(node)
  if node.left  ≠ null then inorder(node.left)
  print node.value
  if node.middle ≠ null then inorder(node.middle)
  if node.right ≠ null then inorder(node.right)

postorder(node)
  if node.left  ≠ null then postorder(node.left)
  if node.middle ≠ null then postorder(node.middle)
  if node.right ≠ null then postorder(node.right)
  print node.value

В листинге 2 приведен пример обхода 3-нарного дерева (где каждый узел может иметь не более трех дочерних элементов) с помощью различных алгоритмов, реализованных на языке Си. Дерево из 10 узлов будет сформировано в методе main, а затем к нему будут применены три варианта обхода, которые будут приведены в отдельном листинге.

Листинг 2. Реализация дерева на языке Си
#include <stdio.h>                           
#include<stdlib.h>

//структура для описания узла дерева
struct tree                                  
{ 
    int data;                                
    struct tree *lchild, *mchild, *rchild;   
};

struct tree *my_insert(struct tree *p,int n, int dir);
void inorder(struct tree *p);                
void preorder(struct tree *p);               
void postorder(struct tree *p);              

int main()                                  
{ 
	int x,y,i;                                    
	struct tree *root;
	struct tree *node_2, *node_3, *node_5;
	struct tree *node_8, *node_9, *node_6,*node_10,*node_4, *node_7   ;
	
	//создание дерева
	root = NULL;
	root = my_insert(root,1,0);		
	node_2 = my_insert(root,2,0);		
	node_3 = my_insert(root,3,1);		
	node_4 = my_insert(root,4,2);		
	node_5 = my_insert(node_3,5,0);		
	node_8 = my_insert(node_5,8,0);		
	node_9 = my_insert(node_5,9,2);		
	node_6 = my_insert(node_3,6,2);		
	node_10 = my_insert(node_6,10,1);		
	node_7 = my_insert(node_4,7,1);		

	//выполнение обхода дерева различными способами
	preorder(root);
	printf("\n");
	inorder(root);
	printf("\n");
	postorder(root);

		return 0;
}

В листинге 3 приведен исходный код функции для вставки узлов в дерево. Данная функция принимает на вход три параметра: указатель на вставляемый узел, значение вставляемого узла и направление вставки — влево, в середину или вправо.

Листинг 3. Функция для вставки узлов в дерево
struct tree * my_insert(struct tree *p,int n, int dir)               
{
	struct tree *temp;

	temp = (struct tree *)malloc(sizeof(struct tree));
	temp->data = n;
	temp->lchild = temp->rchild=NULL;

	if(p==NULL)
	{
		return temp;
	}
	else
	{
		if(dir ==0) // влево
		{
			p->lchild = temp;
			return temp;
		}
		else if(dir ==1) // посередине
		{
			p->mchild = temp;
			return temp;
		}
		else // вправо
		{
			p->rchild = temp;
			return temp;
		}
	}	
}

В листинге 4 приведен исходный код функций, реализующих различные варианты обхода дерева.

Листинг 4. Функции для обхода узлов дерева
void inorder(struct tree *p)
{
    if(p!=NULL)
    {
        inorder(p->lchild);
        printf("%d ",p->data);
        inorder(p->mchild);
        inorder(p->rchild);
    }
}

void preorder(struct tree *p)
{
    if(p!=NULL)
    {
        printf("%d ",p->data);
        preorder(p->lchild);
        preorder(p->mchild);
        preorder(p->rchild);
    }
}

void postorder(struct tree *p)
{
    if(p!=NULL)
    {
        postorder(p->lchild);
        postorder(p->mchild);
        postorder(p->rchild);
        printf("%d ",p->data);
    }
}

В листинге 5 приведена реализация алгоритмов обхода дерева на языке Python. В нем объявляются два класса — один для узлов и другой для самого дерева. В конструкторе класса Tree для наглядности объявляются ссылки на узлы.

Листинг 5. Реализация обхода дерева на языке Python
//класс, представляющий узел
class node:
    def __init__(self, data = None, lchild = None, mchild = None, rchild = None):
        self.data = data
        self.lchild  = lchild
        self.mchild  = mchild
        self.rchild  = rchild

    def __str__(self):
        return 'Node ['+str(self.value)+']'

//класс, представляющий дерево
class Tree:
    def __init__(self):
        self.root = None
        self.node_2  = None
        self.node_3  = None
        self.node_4  = None
        self.node_5  = None
        self.node_6  = None
        self.node_7  = None
        self.node_8  = None
        self.node_9  = None
        self.node_10  = None

//функция для добавления элементов в дерево
    def my_insert(self, root_node, data, dir):
        temp = node(0,None,None,None)
        temp.data = data
        if root_node == None:
          return temp
        else:
          if dir == 0:
            root_node.lchild = temp
            return temp
          elif dir == 1:
            root_node.mchild = temp
            return temp
          else:
            root_node.rchild = temp
            return temp
            

//рекурсивные функции для обхода дерева
    def inorder(self,noda):
        if noda!=None:
          self.inorder(noda.lchild);
          print("%d " % noda.data)
          self.inorder(noda.mchild)
          self.inorder(noda.rchild)

    def preorder(self,noda):
        if noda!=None:
          print (" %d  " % noda.data)
          self.preorder(noda.lchild);
          self.preorder(noda.mchild)
          self.preorder(noda.rchild)

    def postorder(self,noda):
        if noda!=None:
          self.postorder(noda.lchild);
          self.postorder(noda.mchild)
          self.postorder(noda.rchild)
          print (" %d  " % noda.data)

//создание дерева
t  = Tree()
t.root   = t.my_insert(t.root,1,0)
t.node_2 = t.my_insert(t.root,2,0);   
t.node_3 = t.my_insert(t.root,3,1);   
t.node_4 = t.my_insert(t.root,4,2);   
t.node_5 = t.my_insert(t.node_3,5,0);   
t.node_8 = t.my_insert(t.node_5,8,0);   
t.node_9 = t.my_insert(t.node_5,9,2);   
t.node_6 = t.my_insert(t.node_3,6,2);   
t.node_10 = t.my_insert(t.node_6,10,1);   
t.node_7  = t.my_insert(t.node_4,7,1);   

//обход дерева
t.preorder(t.root);
t.inorder(t.root);
t.postorder(t.root);

Нерекурсивная реализация обхода дерева

Дерево можно обойти, и не используя рекурсию, причем это можно сделать любым из трех способов: inorder, preorder и postorder. Для этого можно использовать стандартный стек, работающий по принципу LIFO (последним пришел, первым ушел), в который будут записываться узлы по мере их прохождения. В качестве примера также будет использоваться три-нарное дерево.

Листинг 6. Нерекурсивный обзор дерева на языке Си
#include <stdio.h>                           
#include<stdlib.h>
#include <iostream>
#include <stack>

using namespace std;

struct tree                                  
{ 
    int data;                                
    struct tree *lchild, *mchild, *rchild;   
};

/*
 * функции для итеративного обхода дерева
 */
void iterativeInorder(tree* root) 
{
	stack<tree*> nodeStack;
	tree *_root, *curr = root;
	_root = root;
	for (;;) 
	{
		if (curr != NULL) 
		{
			nodeStack.push(curr);
			curr = curr->lchild;
			continue;
		}
		if (nodeStack.size() == 0) 
		{
			if(_root != NULL)
			{
				curr = _root->rchild;
				_root = NULL;
				continue;
			}
			else return;
		}   
		curr = nodeStack.top();
		nodeStack.pop();
		cout <<  curr->data << " ";
		if(curr->mchild != NULL)
			curr = curr->mchild;
		else 
			curr = curr->rchild;
	}
}

void iterativePreorder(tree* root) 
{
	stack<tree*> nodeStack;
	tree *_root, *curr = root;
	_root = root;
	for (;;) 
	{
		while (curr != NULL) 
		{
			cout << curr->data << " ";
			nodeStack.push(curr);
			curr = curr->lchild;
		}	
		if (nodeStack.size() > 0) 
		{
			curr = nodeStack.top();
			nodeStack.pop();
			if(curr->mchild != NULL)
				curr = curr->mchild;
			else 
				curr = curr->rchild;
		}
		else
		{
			if(_root != NULL)
			{
				curr = _root->rchild;
				_root = NULL;
				continue;
			}
			else return;
		}
	}
}

void iterativePostorder(tree* root) 
{
	tree *curr = root;
	stack<tree*> s1,s2;
	s1.push(curr);
	tree *tmp=NULL;
	while (s1.size() > 0)
	{
		tmp = s1.top();
		s1.pop();
		s2.push(tmp);
		if (tmp->lchild)
			s1.push(tmp->lchild);
		if (tmp->mchild)
			s1.push(tmp->mchild);
		if (tmp->rchild)
			s1.push(tmp->rchild);
	}
	
	while(s2.size() > 0)
	{
		tmp = s2.top();
		s2.pop();
		cout << tmp->data << " ";
	}
}

/*
 * функция для добавления узлов в дерево
 */
struct tree * my_insert(struct tree *p,int n, int dir)               
{
	struct tree *temp;
	temp = (struct tree *)malloc(sizeof(struct tree));
	temp->data = n;
	temp->lchild = temp->rchild=NULL;
	if(p==NULL)
	{
		return temp;
	}
	else
	{
		if(dir ==0) // влево
		{
			p->lchild = temp;
			return temp;
		}
		else if(dir ==1) // посередине
		{
			p->mchild = temp;
			return temp;
		}
		else // вправо
		{
			p->rchild = temp;
			return temp;
		}
	}
}

int main()                                  
{ 
	int x,y,i;                                    
	struct tree *root;
	struct tree *node_2, *node_3, *node_5, *node_8;
	struct tree *node_9, *node_6,*node_10,*node_4, *node_7   ;
		
	root = NULL;
	root = my_insert(root,1,0);		
	node_2 = my_insert(root,2,0);		
	node_3 = my_insert(root,3,1);		
	node_4 = my_insert(root,4,2);		
	node_5 = my_insert(node_3,5,0);		
	node_8 = my_insert(node_5,8,0);		
	node_9 = my_insert(node_5,9,2);		
	node_6 = my_insert(node_3,6,2);		
	node_10 = my_insert(node_6,10,1);		
	node_7 = my_insert(node_4,7,1);		

	iterativeInorder(root);
	printf("\n");
	iterativePreorder(root);
	printf("\n");
	iterativePostorder(root);
	
	return 0;
}

Формы представления дерева

Одной из форм представления дерева является обычный массив. Пусть T - дерево, узлы в котором пронумерованы от 1 до n. Простейшей формой представления дерева T может быть линейный массив A, в котором каждый элемент массива A[i] представляет собой указатель на узел или его родителя.

Если i и j - два узла, и узел j является родителем для узла i, то

A[i] = j

Для идентификации корневого узла, указатель на его родителя можно сделать нулевым, как показано ниже:

A[i] = 0

Каждый узел может иметь только одного родителя. Одновременно с массивом A можно завести массив L, в котором будут храниться метки для узлов. На рисунке 3 дерево представлено в виде массива родителей для каждого узла. Однако при использовании такого представления остается неясным, в каком порядке идут дочерние узлы.

Рисунок 3. Представление дерева в виде массива
Рисунок 3. Представление дерева в виде массива
Рисунок 3. Представление дерева в виде массива

Еще один возможный вариант представления деревьев – это использование связного списка, содержащего все узлы дерева, при этом дочерние узлы хранятся вместе с родительским, как показано на рисунке 4.

Рисунок 4. Представление дерева в виде списка
Рисунок 4. Представление дерева в виде списка
Рисунок 4. Представление дерева в виде списка

На этом рисунке показан общий массив узлов, пронумерованный от 1 до 10. У отдельных узлов из этого списка есть дочерние узлы, которые в общем списке помечены точками. Но так как массив имеет фиксированный размер, то в такое дерево нельзя вставить новый узел.

Виды деревьев

Дерево выражений (англ. expression tree) - это разновидность бинарного дерева, предназначенная для отображения арифметических или логических выражений, при этом операнды размещаются в листьях, как показано на рисунке 5.

Рисунок 5. Примеры использования дерева выражений
Рисунок 5. Примеры использования дерева выражений
Рисунок 5. Примеры использования дерева выражений

В узлах так называемого triply linked дерева, кроме ссылок на левый и правый дочерний узлы, хранится и ссылка на родительский узел, как показано на рисунке 6.

Рисунок 6. triply linked дерево
Рисунок 6. triply linked дерево
Рисунок 6. triply linked дерево

На рисунке 7 представлены еще два интересных варианта дерева – кольцевое дерево и дерево, не имеющее корня.

Рисунок 7. Необычные варианты деревьев
Рисунок 7. Необычные варианты деревьев
Рисунок 7. Необычные варианты деревьев

Заключение

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


Ресурсы для скачивания


Похожие темы

  • Работа со структурами данных в языках Си и Python. Часть 1.
  • Работа со структурами данных в языках Си и Python. Часть 2.
  • Работа со структурами данных в языках Си и Python. Часть 3.
  • Работа со структурами данных в языках Си и Python. Часть 4.
  • Работа со структурами данных в языках Си и Python. Часть 5.

Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=660980
ArticleTitle=Работа со структурами данных в языках Си и Python: Часть 5. Деревья
publish-date=05262011