트리 종합연산(후위연산+노드갯수+높이)

자료구조의 트리 단원을 배우고 나서 응용할 수 있는 몇가지 연산들을 한 코드에 담아봤습니다.

후위 연산, 노드의 갯수, 단말노드의 갯수, 트리의높이를 구하는 코드입니다.

재귀함수를 이해하고 응용할 수 있어야함을 알 수 있습니다.

소스코드는 아래 그림과 같이 트리가 이루어져 있을 때를 가정합니다.

코드

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define max(a,b) (((a)>(b))?(a):(b))
typedef struct treeNode
{
	int data;
	struct treeNode* left;
	struct treeNode* right;
}treeNode;

treeNode n5 = { 0,NULL,NULL };
treeNode n4 = { 1,NULL,NULL };
treeNode n3 = { 2,NULL,NULL };
treeNode n2 = { 3,&n4,&n5 };
treeNode n1 = { 4,&n2,&n3 };
treeNode* root = &n1;
int cal_post(treeNode* root)
{
	int left, right;
	if (root)
	{
		left = cal_post(root->left);
		right = cal_post(root->right);
		return root->data + left + right;
	}
	return 0;
}
int node_count(treeNode* root)
{
	int count = 0;
	if (root)
	{
		count = 1+node_count(root->left) + node_count(root->right);
	}
	return count;
}
int leaf_node(treeNode* root)
{
	int count = 0;
	if (root)
	{
		if (root->left==NULL && root->right==NULL)
		{
			return 1;
		}
		else
		{
			return leaf_node(root->left) + leaf_node(root->right);
		}
	}
	return count;
}
int height(treeNode* root)
{
	int hight = 0;
	int left, right;
	if (root)
	{
		left = height(root->left);
		right = height(root->right);
		return 1+max(left, right);
	}
	return hight;
}
int main()
{
	printf("후위덧셈!!\n%d\n", cal_post(root));
	printf("노드의갯수!!!\n%d\n", node_count(root));
	printf("단말노드의갯수!!\n%d\n", leaf_node(root));
	printf("트리의높이는!!\n%d\n", height(root));
}

결과