BFS / DFS (Binary Tree)

이런 정렬되지 않은 모양의 트리를 만들고 BFS, DFS를 구현해보려고 한다.

 

• BFS with queue

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
class Node {
private:
	Node* left;
	Node* right;
	Node* root;
	int val;
public:
	Node() : val(0), left(nullptr), right(nullptr), root(nullptr) {};
	Node(int _val) : val(_val), left(nullptr), right(nullptr), root(nullptr) {};
	
	void SetLeft(Node* node) { this->left = node; }
	void SetRight(Node* node) { this->right = node; }
	Node* getLeft() { return left; }
	Node* getRight() { return right; }
	int getValue() { return val; }
	~Node() {};
};

void bfs(Node* node) {
	queue<Node *> q;
	q.push(node);

	while (!q.empty()) {
		node = q.front();
		int value = node->getValue();
		q.pop();
		cout << value << " ";
		if (node->getLeft()) q.push(node->getLeft());
		if (node->getRight()) q.push(node->getRight());
	}
}

int main(void) {
	Node* node1 = new Node(1);
	Node* node2 = new Node(2);
	Node* node3 = new Node(3);
	Node* node4 = new Node(4);

	Node* node5 = new Node(5);
	Node* node6 = new Node(6);
	node4->SetLeft(node1);
	node4->SetRight(node2);
	node1->SetLeft(node3);
	node1->SetRight(node5);
	node2->SetRight(node6);

	bfs(node4);
    
	return 0;
}

// result : 4, 1, 2, 3, 5, 6

 

• DFS with recursion ( inorder )

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
class Node {
private:
	Node* left;
	Node* right;
	Node* root;
	int val;
public:
	Node() : val(0), left(nullptr), right(nullptr), root(nullptr) {};
	Node(int _val) : val(_val), left(nullptr), right(nullptr), root(nullptr) {};
	
	void SetLeft(Node* node) { this->left = node; }
	void SetRight(Node* node) { this->right = node; }
	Node* getLeft() { return left; }
	Node* getRight() { return right; }
	int getValue() { return val; }
	~Node() {};
};
void inorder(Node* node) {
	if (node == nullptr) return;

	inorder(node->getLeft());
	cout << node->getValue() << " ";
	inorder(node->getRight());
}

int main(void) {
	Node* node1 = new Node(1);
	Node* node2 = new Node(2);
	Node* node3 = new Node(3);
	Node* node4 = new Node(4);

	Node* node5 = new Node(5);
	Node* node6 = new Node(6);
	node4->SetLeft(node1);
	node4->SetRight(node2);
	node1->SetLeft(node3);
	node1->SetRight(node5);
	node2->SetRight(node6);

	inorder(node4);

	return 0;
}

// result : 3, 1, 5, 4, 2, 6

 

• DFS with iterative ( inorder )

#include<iostream>
#include<queue>
#include<stack>
using namespace std;

class Node {
private:
	Node* left;
	Node* right;
	Node* root;
	int val;
public:
	Node() : val(0), left(nullptr), right(nullptr), root(nullptr) {};
	Node(int _val) : val(_val), left(nullptr), right(nullptr), root(nullptr) {};
	
	void SetLeft(Node* node) { this->left = node; }
	void SetRight(Node* node) { this->right = node; }
	Node* getLeft() { return left; }
	Node* getRight() { return right; }
	int getValue() { return val; }
	~Node() {};
};

void dfs(Node* node) {
	stack<Node*> s;

	while (!s.empty() || node != nullptr) {
		while (node != nullptr) {
			s.push(node);
			node = node->getLeft();
		}
		node = s.top(); s.pop();
		cout << node->getValue() << " ";
		node = node->getRight();
	}
}
int main(void) {
	Node* node1 = new Node(1);
	Node* node2 = new Node(2);
	Node* node3 = new Node(3);
	Node* node4 = new Node(4);

	Node* node5 = new Node(5);
	Node* node6 = new Node(6);
	node4->SetLeft(node1);
	node4->SetRight(node2);
	node1->SetLeft(node3);
	node1->SetRight(node5);
	node2->SetRight(node6);

	dfs(node4);

	return 0;
}