본문 바로가기
Data Structure

C, C++ Binary Tree(이진 트리) 만들기 (version 1)

by SuldenLion 2023. 4. 7.
반응형

C와 C++로 Binary Tree 구현하기

 

C로 Binary Tree를 구현하고 C++로 바꿔보는 것 까지 해보겠다.

 

Binary Tree라 하면, 각각의 노드가 최대 두 개의 자식 노드를 가지는 Tree 자료 구조로, 왼쪽 자식 노드와 오른쪽 자식 노드로 나뉜다.

 

 

트리에 7, 3, 2, 6, 9, 5, 8의 데이터를 넣는다고 해보자

 

Tree가 처음에 비어있을 경우, 노드를 하나 할당해주고 트리가 해당 노드를 가리키게 한다.

 

그 다음 3을 넣는다면 트리가 가리키는 노드들을 타고 내려가면서 노드들이 가지는 data 값과 새로 들어올 data값(=3)을 비교한다. 들어올 값이 비교하는 노드의 데이터 값보다 작다면 lchild 쪽으로, 크다면 rchild 쪽으로 간다.

lchild나 rchild가 NULL을 가리킬 때까지 노드들을 타고 내려가다가 leaf 노드에 다다르게 되면 새로운 노드를 할당해서 그 leaf 노드와 연결해주면 된다.

 

위의 숫자 (7, 3, 2, 6, 9, 5, 8) 이 추가되는 과정을 이어서 보겠다.

 

add(3)
add(2)
add(6)
add(9)
add(5)
add(8)

 

 

이런식으로 데이터가 추가되어진다.

 

typedef struct _treeNode {
	struct _treeNode *lchild;
	int data;
	struct _treeNode *rchild;
} TreeNode;

void addNode(TreeNode *node, int x) 
{
	if (x > node->data) {
		if (node->rchild == NULL) {
			TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
			newNode->lchild = NULL;
			newNode->data = x;
			newNode->rchild = NULL;
			node->rchild = newNode;
		} else {
			addNode(node->rchild, x);
		}
	} else {
		if (node->lchild == NULL) {
			TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
			newNode->lchild = NULL;
			newNode->data = x;
			newNode->rchild = NULL;
			node->lchild = newNode;
		} else {
			addNode(node->lchild, x);
		}
	}
}

void inorder(TreeNode *node) 
{
	if (node->lchild != NULL) inorder(node->lchild);
	printf("%d ", node->data);
	if (node->rchild != NULL) inorder(node->rchild);
}

int getDepth(TreeNode *node)
{
	int n1 = 0;
	int n2 = 0;

	if (node->lchild != NULL) n1 = getDepth(node->lchild);
	if (node->rchild != NULL) n2 = getDepth(node->rchild);
	if (n1 > n2) return n1 + 1;
	else return n2 + 1;
}

int getCount(TreeNode *node)
{
	int n1 = 0;
	int n2 = 0;

	if (node->lchild != NULL) n1 = getCount(node->lchild);
	if (node->rchild != NULL) n2 = getCount(node->rchild);
	return n1 + n2 + 1;
}

void add(TreeNode **tree, int x)
{
	if (*tree == NULL) {
		TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
		newNode->lchild = NULL;
		newNode->data = x;
		newNode->rchild = NULL;
		*tree = newNode;
		return;
	}
	addNode(*tree, x);
}

void inorderTree(TreeNode *tree)
{
	printf("[ ");
	if (tree == NULL) {
		printf("]");
		return;
	}
	inorder(tree);
	printf("]\n");
}

int getTreeDepth(TreeNode *tree) 
{
	if (tree == NULL) {
		return 0;
	}
	return getDepth(tree);
}

int getNodeCount(TreeNode *tree) 
{
	if (tree == NULL) {
		return 0;
	}
	return getCount(tree);
}


main()
{
	TreeNode *tree = NULL;
	int n = 0;

	add(&tree, 7);
	add(&tree, 3);
	add(&tree, 2);
	add(&tree, 6);
	add(&tree, 9);
	add(&tree, 5);
	add(&tree, 8);

	inorderTree(tree);

	n = getTreeDepth(tree);
	printf("depth = %d\n", n);

	n = getNodeCount(tree);
	printf("count = %d\n", n);
}

 

트리에 데이터를 추가시켜주고 Inorder 방식 Traverse를 해보고 Tree의 Depth와 Node의 개수를 구해보는 소스코드이다.

 

Left > Root > Right 순서의 Inorder traverse는 다음 순서로 순회하며 데이터를 출력한다.

 

getDepth()는 재귀적으로 반복하며 각 노드의 lchild 에서 구해온 getDepth의 값과 rchild 에서 구해온 getDepth()의 값을 비교하여 더 큰값에 +1을 한 후 상위 노드로 return 시켜준다.

 

getNodeCount()도 재귀적이며 각 노드의 lchild에서 구한 getNodeCount()와 rchild의 getNodeCount()를 +1과 함께 더해서 return 한다.

 

 

이렇게 만들어보니 비효율적인 트리가 되어버린것을 알 수 있다.

 

바로 전체 노드의 개수를 구하겠다고 모든 노드를 recursive하게 돌아야 한다는 것이다.

 

Tree의 size같은 경우는 Tree 구조체를 하나 놓고 Data member로 count 값을 두어 add() 작업이 있을때마다 증가시켜주는 식으로 하면 getCount를 효율적으로 할 수 있을 것이다.

 

 

 

이런식으로 말이다.

 

그럼 약간의 수정을 거쳐서 다시 코드를 짜보겠다.

 

#include <stdio.h>
#include <malloc.h>

typedef struct _treeNode {
	struct _treeNode *lchild;
	int data;
	struct _treeNode *rchild;
} TreeNode;

typedef struct _tree {
	TreeNode *root;
	int count;
} Tree;

void initTree(Tree *tree)
{
	tree->root = NULL;
	tree->count = 0;
}

void addNode(TreeNode *node, int x) 
{
	if (x > node->data) {
		if (node->rchild == NULL) {
			TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
			newNode->lchild = NULL;
			newNode->data = x;
			newNode->rchild = NULL;
			node->rchild = newNode;
		} else {
			addNode(node->rchild, x);
		}
	} else {
		if (node->lchild == NULL) {
			TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
			newNode->lchild = NULL;
			newNode->data = x;
			newNode->rchild = NULL;
			node->lchild = newNode;
		} else {
			addNode(node->lchild, x);
		}
	}
}

void inorder(TreeNode *node) 
{
	if (node->lchild != NULL) inorder(node->lchild);
	printf("%d ", node->data);
	if (node->rchild != NULL) inorder(node->rchild);
}

void preorder(TreeNode *node) 
{
	printf("%d ", node->data);
	if (node->lchild != NULL) preorder(node->lchild);
	if (node->rchild != NULL) preorder(node->rchild);
}

void postorder(TreeNode *node) 
{
	if (node->lchild != NULL) postorder(node->lchild);
	if (node->rchild != NULL) postorder(node->rchild);
	printf("%d ", node->data);
}

int getDepth(TreeNode *node)
{
	int n1 = 0;
	int n2 = 0;

	if (node->lchild != NULL) n1 = getDepth(node->lchild);
	if (node->rchild != NULL) n2 = getDepth(node->rchild);
	if (n1 > n2) return n1 + 1;
	else return n2 + 1;
}

int getCount(TreeNode *node)
{
	int n1 = 0;
	int n2 = 0;

	if (node->lchild != NULL) n1 = getCount(node->lchild);
	if (node->rchild != NULL) n2 = getCount(node->rchild);
	return n1 + n2 + 1;
}

void add(Tree *tree, int x)
{
	tree->count++;
	if (tree->root == NULL) {
		TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
		newNode->lchild = NULL;
		newNode->data = x;
		newNode->rchild = NULL;
		tree->root = newNode;
		return;
	}
	addNode(tree->root, x);
}

void inorderTree(Tree *tree)
{
	printf("[ ");
	if (tree->root == NULL) {
		printf("]");
		return;
	}
	inorder(tree->root);
	printf("]\n");
}

void preorderTree(Tree *tree)
{
	printf("[ ");
	if (tree->root == NULL) {
		printf("]");
		return;
	}
	preorder(tree->root);
	printf("]\n");
}

void postorderTree(Tree *tree)
{
	printf("[ ");
	if (tree->root == NULL) {
		printf("]");
		return;
	}
	postorder(tree->root);
	printf("]\n");
}

int getTreeDepth(Tree *tree) 
{
	if (tree->root == NULL) {
		return 0;
	}
	return getDepth(tree->root);
}

int getNodeCount(Tree *tree) 
{
	if (tree->root == NULL) {
		return 0;
	}
	return getCount(tree->root);
}


main()
{
	Tree tree;
	int n = 0;

	initTree(&tree);

	add(&tree, 7);
	add(&tree, 3);
	add(&tree, 2);
	add(&tree, 6);
	add(&tree, 9);
	add(&tree, 5);
	add(&tree, 8);

	inorderTree(&tree);

	n = getTreeDepth(&tree);
	printf("depth = %d\n", n);

	//n = getNodeCount(&tree);
	//printf("count = %d\n", n);

	preorderTree(&tree);

	postorderTree(&tree);

	printf("%d\n", tree.count);
}

 

tree.count로 바로 트리의 노드수를 가져올 수 있다.

 

그리고 preorder와 postorder traverse이다.

 

Preorder traverse (Root > Left > Right 순서로 순회)
Postorder traverse (Left > Right > Root 순서로 순회)

 

 

 

 

다음은 위 코드를 cpp로 바꿔볼것이다.

메인 파일과 tree의 헤더파일, 구현파일로 나눠보겠다.

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

void main()
{
	Tree tree;
	int n = 0;

	tree.add(7);
	tree.add(3);
	tree.add(2);
	tree.add(6);
	tree.add(9);
	tree.add(5);
	tree.add(8);

	tree.inorder();

	n = tree.getDepth();
	cout << "depth = " << n << endl;

	n = tree.getCount();
	cout << "count = " << n << endl;

	tree.preorder();
	tree.postorder();
}

메인 파일이다.

 

#include <stdio.h>
#include <malloc.h>


class Tree {
	class TreeNode {
		TreeNode *lchild;
		int data;
		TreeNode *rchild;
	public:
		TreeNode(int x) {
			lchild = rchild = NULL;
			data = x;
		}
		void add(int x);
		void inorder();
		void preorder();
		void postorder();
		int getDepth();
		int getCount();
	};
	TreeNode *root;
	int count;
public:
	Tree();
	void add(int x);
	void inorder();
	void preorder();
	void postorder();
	int getDepth();
	inline int getCount() { return count; }
};

Tree의 헤더파일이다.

 

TreeNode 같은 경우는 Tree 밖에서 사용되지 않을 것이기 때문에 Tree 안에 Inner class로써 만들어준다.

 

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

void Tree::TreeNode::add(int x) 
{
	if (x > data) {
		if (rchild == NULL) {
			TreeNode *newNode = new TreeNode(x);
			rchild = newNode;
		} else {
			rchild->add(x);
		}
	} else {
		if (lchild == NULL) {
			TreeNode *newNode = new TreeNode(x);
			lchild = newNode;
		} else {
			lchild->add(x);
		}
	}
}

void Tree::TreeNode::inorder() 
{
	if (lchild != NULL) lchild->inorder();
	cout << data << " ";
	if (rchild != NULL) rchild->inorder();
}

void Tree::TreeNode::preorder() 
{
	cout << data << " ";
	if (lchild != NULL) lchild->preorder();
	if (rchild != NULL) rchild->preorder();
}

void Tree::TreeNode::postorder() 
{
	if (lchild != NULL) lchild->postorder();
	if (rchild != NULL) rchild->postorder();
	cout << data << " ";
}

int Tree::TreeNode::getDepth()
{
	int n1 = 0;
	int n2 = 0;

	if (lchild != NULL) n1 = lchild->getDepth();
	if (rchild != NULL) n2 = rchild->getDepth();
	if (n1 > n2) return n1 + 1;
	else return n2 + 1;
}

int Tree::TreeNode::getCount()
{
	int n1 = 0;
	int n2 = 0;

	if (lchild != NULL) n1 = lchild->getCount();
	if (rchild != NULL) n2 = rchild->getCount();
	return n1 + n2 + 1;
}

Tree::Tree() 
{
	root = NULL;
	count = 0;
}

void Tree::add(int x)
{
	count++;
	if (root == NULL) {
		TreeNode *newNode = new TreeNode(x);
		root = newNode;
		return;
	}
	root->add(x);
}

void Tree::inorder()
{
	cout << "[ ";
	if (root == NULL) {
		cout << "]" << endl;
		return;
	}
	root->inorder();
	cout << "]" << endl;
}

void Tree::preorder()
{
	cout << "[ ";
	if (root == NULL) {
		cout << "]" << endl;
		return;
	}
	root->preorder();
	printf("]\n");
}

void Tree::postorder()
{
	cout << "[ ";
	if (root == NULL) {
		cout << "]" << endl;
		return;
	}
	root->postorder();
	printf("]\n");
}

int Tree::getDepth() 
{
	if (root == NULL) {
		return 0;
	}
	return root->getDepth();
}

 

구현된건 C와 내용이 같고 TreeNode의 함수를 쓰기 위해서는 Tree에 있다는 표시(scope resolution operator ::)를 해준다.

 

반응형

'Data Structure' 카테고리의 다른 글

TableModel 만들기  (1) 2024.01.06
TreeModel 만들기  (1) 2024.01.06
C# 2차원 배열 & 가변 배열 정리  (0) 2023.04.02
C언어 1차원 배열과 2차원 배열 간단한 정리와 테스트  (0) 2023.04.01
C++ LinkedList 만들기 (version 4 - Doubly LinkedList)  (0) 2023.03.31

관련글

댓글

티스토리툴바