이진트리 순회 (Tree Traversal)

preorder (전위 순회)

루트->왼쪽 자식->오른쪽 자식

void preorder(BinaryNode* node) {
	if (node != NULL) {
		cout << "[" << node->getData() << "]";
		if (node->getLeft() != NULL) preorder(node->getLeft());
		if (node->getRight() != NULL) preorder(node->getRight());
	}
}

inorder (중위 순회)

왼쪽 자식->루트->오른쪽 자식

void inorder(BinaryNode* node) {
	if (node!= NULL) {
		if (node->getLeft() != NULL) inorder(node->getLeft());
		cout << "[" << node->getData() << "]";
		if (node->getRight() != NULL) inorder(node->getRight());
	}
}

postorder (후위 순회)

왼쪽 자식->오른쪽 자식->루트

void postorder(BinaryNode* node) {
	if (node != NULL) {
		if (node->getLeft() != NULL) postorder(node->getLeft());
		if (node->getRight() != NULL) postorder(node->getRight());
		cout << "[" << node->getData() << "]";
	}
}

주의

기존에 활용하던 BinaryNode 클래스와 BinaryTree 클래스에 preorder, inorder, postorder 함수를 추가해서 실행해보겠다

#include <iostream>
using namespace std;
class BinaryNode {
public:
	int data;
	BinaryNode* left;
	BinaryNode* right;
	BinaryNode(int val=0,BinaryNode* l=NULL,BinaryNode* r=NULL)
		:data(val),right(r),left(l){}
	~BinaryNode(){}
	void setData(int val) {
		data = val;
	}
	int getData() {
		return data;
	}
	void setLeft(BinaryNode* l) {
		left = l;
	}
	BinaryNode* getLeft() {
		return left;
	}
	void setRight(BinaryNode* r) {
		right = r;
	}
	BinaryNode* getRight() {
		return right;
	}
	bool isLeaf() {
		return right == NULL && left == NULL;
	}
};
class BinaryTree {
	BinaryNode* root;
public:
	BinaryTree() 
		:root(NULL){}
	~BinaryTree(){}
	void setRoot(BinaryNode* node) {
		root = node;
	}
	BinaryNode* getRoot() {
		return root;
	}
	bool isEmpty() {
		return root == NULL;
	}
	int getCount() {
		return isEmpty() ? 0 : getCount(root);
	}
	int getCount(BinaryNode* node) {
		if (node == NULL) return 0;
		return getCount(node->getLeft()) + getCount(node->getRight()) + 1;
	}
	int getHeight() {
		return isEmpty() ? 0 : getHeight(root);
	}
	int getHeight(BinaryNode* node) {
		if (node == NULL) return 0;
		int hLeft = getHeight(node->getLeft());
		int hRight = getHeight(node->getRight());
		return (hLeft > hRight) ? 1 + hLeft : 1 + hRight;
	}
	int getLeafCount() {
		return isEmpty() ? 0 : getLeafCount(root);
	}
	int getLeafCount(BinaryNode* node) {
		if (node == NULL) return 0;
		if (node->isLeaf()) return 1;
		else
			return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
	}
	void preorder(BinaryNode* node) {
		if (node != NULL) {
			cout << "[" << node->getData() << "]";
			if (node->getLeft() != NULL) preorder(node->getLeft());
			if (node->getRight() != NULL) preorder(node->getRight());
		}
	}
	void inorder(BinaryNode* node) {
		if (node!= NULL) {
			if (node->getLeft() != NULL) inorder(node->getLeft());
			cout << "[" << node->getData() << "]";
			if (node->getRight() != NULL) inorder(node->getRight());
		}

	}
	void postorder(BinaryNode* node) {
		if (node != NULL) {
			if (node->getLeft() != NULL) postorder(node->getLeft());
			if (node->getRight() != NULL) postorder(node->getRight());
			cout << "[" << node->getData() << "]";
		}
	}
};
int main() {
	BinaryTree tree;
	BinaryNode* d = new BinaryNode('D', NULL, NULL);
	BinaryNode* e = new BinaryNode('E', NULL, NULL);
	BinaryNode* f = new BinaryNode('F', NULL, NULL);
	BinaryNode* g = new BinaryNode('G', NULL, NULL);
	BinaryNode* b = new BinaryNode('B', d, e);
	BinaryNode* c = new BinaryNode('C', f, g);
	BinaryNode* a = new BinaryNode('A', b, c);
	tree.setRoot(a);
	cout << "전위순회 : ";
	tree.preorder(tree.getRoot());
	cout << endl;
	cout << "중위순회 : ";
	tree.inorder(tree.getRoot());
	cout << endl;
	cout << "후위순회 : ";
	tree.postorder(tree.getRoot());
	return 0;
}

실행해보면 출력값은 아래와 같다

// 출력
전위순회 : [65][66][68][69][67][70][71]
중위순회 : [68][66][69][65][70][67][71]
후위순회 : [68][69][66][70][71][67][65]

내가 구현한 트리는 이 사진처럼 생긴 트리인데 전위, 중위, 후위 순회로 출력했더니 키값인 알파벳이 출력되지 않고 숫자들이 출력되었다 처음에는 코드를 잘못 구현했다고 생각했지만 코드에서는 틀린 로직이 없어보였다

알고봤더니 키 값의 자료형을 int로 설정해두었기 때문이라는 발생한 문제라는 것을 알게 되었다

해결법1

preorder, inorder, postorder 함수에서 데이터를 받아서 출력하는 부분에서 자료형을 char로 변경한다

#include <iostream>
using namespace std;
class BinaryNode {
public:
	int data;
	BinaryNode* left;
	BinaryNode* right;
	BinaryNode(int val=0,BinaryNode* l=NULL,BinaryNode* r=NULL)
		:data(val),right(r),left(l){}
	~BinaryNode(){}
	void setData(int val) {
		data = val;
	}
	int getData() {
		return data;
	}
	void setLeft(BinaryNode* l) {
		left = l;
	}
	BinaryNode* getLeft() {
		return left;
	}
	void setRight(BinaryNode* r) {
		right = r;
	}
	BinaryNode* getRight() {
		return right;
	}
	bool isLeaf() {
		return right == NULL && left == NULL;
	}
};
class BinaryTree {
	BinaryNode* root;
public:
	BinaryTree() 
		:root(NULL){}
	~BinaryTree(){}
	void setRoot(BinaryNode* node) {
		root = node;
	}
	BinaryNode* getRoot() {
		return root;
	}
	bool isEmpty() {
		return root == NULL;
	}
	int getCount() {
		return isEmpty() ? 0 : getCount(root);
	}
	int getCount(BinaryNode* node) {
		if (node == NULL) return 0;
		return getCount(node->getLeft()) + getCount(node->getRight()) + 1;
	}
	int getHeight() {
		return isEmpty() ? 0 : getHeight(root);
	}
	int getHeight(BinaryNode* node) {
		if (node == NULL) return 0;
		int hLeft = getHeight(node->getLeft());
		int hRight = getHeight(node->getRight());
		return (hLeft > hRight) ? 1 + hLeft : 1 + hRight;
	}
	int getLeafCount() {
		return isEmpty() ? 0 : getLeafCount(root);
	}
	int getLeafCount(BinaryNode* node) {
		if (node == NULL) return 0;
		if (node->isLeaf()) return 1;
		else
			return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
	}
	void preorder(BinaryNode* node) {
		if (node != NULL) {
			cout << "[" << char(node->getData()) << "]"; // 변경한 부분
			if (node->getLeft() != NULL) preorder(node->getLeft());
			if (node->getRight() != NULL) preorder(node->getRight());
		}
	}
	void inorder(BinaryNode* node) {
		if (node!= NULL) {
			if (node->getLeft() != NULL) inorder(node->getLeft());
			cout << "[" << char(node->getData()) << "]"; // 변경한 부분
			if (node->getRight() != NULL) inorder(node->getRight());
		}

	}
	void postorder(BinaryNode* node) {
		if (node != NULL) {
			if (node->getLeft() != NULL) postorder(node->getLeft());
			if (node->getRight() != NULL) postorder(node->getRight());
			cout << "[" << char(node->getData()) << "]"; // 변경한 부분
		}
	}
};
int main() {
	BinaryTree tree;
	BinaryNode* d = new BinaryNode('D', NULL, NULL);
	BinaryNode* e = new BinaryNode('E', NULL, NULL);
	BinaryNode* f = new BinaryNode('F', NULL, NULL);
	BinaryNode* g = new BinaryNode('G', NULL, NULL);
	BinaryNode* b = new BinaryNode('B', d, e);
	BinaryNode* c = new BinaryNode('C', f, g);
	BinaryNode* a = new BinaryNode('A', b, c);
	tree.setRoot(a);
	cout << "전위순위 : ";
	tree.preorder(tree.getRoot());
	cout << endl;
	cout << "중위순위 : ";
	tree.inorder(tree.getRoot());
	cout << endl;
	cout << "후위순위 : ";
	tree.postorder(tree.getRoot());
	return 0;
}

해결법2

키값을 받는 변수인 data의 자료형을 char로 선언한다

#include <iostream>
using namespace std;
class BinaryNode {
public:
	char data; // 변경한 부분
	BinaryNode* left;
	BinaryNode* right;
	BinaryNode(char val=' ',BinaryNode* l=NULL,BinaryNode* r=NULL) // 변경한 부분
		:data(val),right(r),left(l){}
	~BinaryNode(){}
	void setData(char val) { // 변경한 부분
		data = val;
	}
	char getData() { // 변경한 부분
		return data;
	}
	void setLeft(BinaryNode* l) {
		left = l;
	}
	BinaryNode* getLeft() {
		return left;
	}
	void setRight(BinaryNode* r) {
		right = r;
	}
	BinaryNode* getRight() {
		return right;
	}
	bool isLeaf() {
		return right == NULL && left == NULL;
	}
};
class BinaryTree {
	BinaryNode* root;
public:
	BinaryTree() 
		:root(NULL){}
	~BinaryTree(){}
	void setRoot(BinaryNode* node) {
		root = node;
	}
	BinaryNode* getRoot() {
		return root;
	}
	bool isEmpty() {
		return root == NULL;
	}
	int getCount() {
		return isEmpty() ? 0 : getCount(root);
	}
	int getCount(BinaryNode* node) {
		if (node == NULL) return 0;
		return getCount(node->getLeft()) + getCount(node->getRight()) + 1;
	}
	int getHeight() {
		return isEmpty() ? 0 : getHeight(root);
	}
	int getHeight(BinaryNode* node) {
		if (node == NULL) return 0;
		int hLeft = getHeight(node->getLeft());
		int hRight = getHeight(node->getRight());
		return (hLeft > hRight) ? 1 + hLeft : 1 + hRight;
	}
	int getLeafCount() {
		return isEmpty() ? 0 : getLeafCount(root);
	}
	int getLeafCount(BinaryNode* node) {
		if (node == NULL) return 0;
		if (node->isLeaf()) return 1;
		else
			return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
	}
	void preorder(BinaryNode* node) {
		if (node != NULL) {
			cout << "[" << node->getData() << "]";
			if (node->getLeft() != NULL) preorder(node->getLeft());
			if (node->getRight() != NULL) preorder(node->getRight());
		}
	}
	void inorder(BinaryNode* node) {
		if (node!= NULL) {
			if (node->getLeft() != NULL) inorder(node->getLeft());
			cout << "[" << node->getData() << "]";
			if (node->getRight() != NULL) inorder(node->getRight());
		}

	}
	void postorder(BinaryNode* node) {
		if (node != NULL) {
			if (node->getLeft() != NULL) postorder(node->getLeft());
			if (node->getRight() != NULL) postorder(node->getRight());
			cout << "[" << node->getData() << "]";
		}
	}
};
int main() {
	BinaryTree tree;
	BinaryNode* d = new BinaryNode('D', NULL, NULL);
	BinaryNode* e = new BinaryNode('E', NULL, NULL);
	BinaryNode* f = new BinaryNode('F', NULL, NULL);
	BinaryNode* g = new BinaryNode('G', NULL, NULL);
	BinaryNode* b = new BinaryNode('B', d, e);
	BinaryNode* c = new BinaryNode('C', f, g);
	BinaryNode* a = new BinaryNode('A', b, c);
	tree.setRoot(a);
	cout << "전위순위 : ";
	tree.preorder(tree.getRoot());
	cout << endl;
	cout << "중위순위 : ";
	tree.inorder(tree.getRoot());
	cout << endl;
	cout << "후위순위 : ";
	tree.postorder(tree.getRoot());
	return 0;
}

결과

수정했더니 잘 출력되는 걸 확인할 수 있다!

// 출력
전위순위 : [A][B][D][E][C][F][G]
중위순위 : [D][B][E][A][F][C][G]
후위순위 : [D][E][B][F][G][C][A]