Обходы деревьев - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Добро пожаловать на один из самых интересных разделов в этой документации, тут вы познакомитесь с обходами деревьев

Обход узлов бинарного дерева в прямом, симметричном или обратном порядке

Все эти три обхода выглядят следующим образом

1. Обход дерева в прямом порядке(префиксный).

Это самый обычный обход дерева, к которому мы привыкли

inline void print(BinaryTree* root)
{
	if (!isEmpty(root))
	{
		cout << root->data << " ";
		if (!isEmpty(root->left))
			print(root->left);
		if (!isEmpty(root->right))
			print(root->right);
	}
	
}

2.Симметричный(инфиксный) обход дерева.По сути мы делаем все тоже самое только cout перемещается чуть ниже

inline void printS(BinaryTree* root)
{
	if (!isEmpty(root))
	{
		if (!isEmpty(root->left))
			printS(root->left);
		cout << root->data << " ";
		if (!isEmpty(root->right))
			printS(root->right);
	}
}

3.Обратный(постфиксный) обход дерева.Тут наш cout перемещается в самый низ и кайфует

inline void printOb(BinaryTree* root)
{
	if (!isEmpty(root))
	{
		if (!isEmpty(root->left))
			printOb(root->left);
		if (!isEmpty(root->right))
			printS(root->right);
		cout << root->data << " ";
	}
}

Обход дерева в ширину

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

inline void printWidth(BinaryTree* root)
{
	if (!isEmpty(root))
	{
		Queue<BinaryTree*> q;
		q.enque(root);
		while (!q.isEmpty())
		{
			BinaryTree* cur = q.peek();
			q.deque();
			cout << cur->data<<" ";
			if (!isEmpty(cur->left))
				q.enque(cur->left);
			if (!isEmpty(cur->right))
				q.enque(cur->right);
		}
	}
}

Итеративный(не рекурсивный) обход дерева в глубину.(симметричный)

В этом обходе мы используем стек.В начале мы закидываем корень в стек, затем туда же закидываем все левые звенья дерева,как только они кончаются, мы начинаем вынимать элементы из стека, параллельно наблюдая затем, есть ли правые звенья(если есть, то закидываем их в стек).И так пока не опустошим стек.

void iterativeDFS() {
	StackList<Node*> stack;
	Node* cur = root;
	stack.addElem(cur);
	while (!stack.isEmpty())
	{
		if (cur->left) {
			cur = cur->left;
			stack.addElem(cur);
		}
		else{
			cur = stack.peek();
			stack.removeElem();
			cout << cur->data << endl;
			if (cur->right) {
				cur = cur->right;
				stack.addElem(cur);
			}

		}
		
	}
}

Итеративный префиксный обход

void iterativeDFSPR() {
	StackList<Node*> stack;
	Node* cur = root;
	stack.addElem(cur);
	while (!stack.isEmpty())
	{
		cur = stack.peek();
		stack.removeElem();
		cout << cur->data << endl;
		
		if (cur->right) {
			stack.addElem(cur->right);
		}
		if (cur->left) {
			stack.addElem(cur->left);
		}

			
	}
}