[자료구조] Tree: 정의 및 depth와 height 구하기

Tree

 

1. Tree의 정의 및 관련 용어

 

Tree(트리)는 root라고 불리는 지정된 노드가 있고, root를 제외한 모든 노드가 유일한 부모 노드를 가지는 그래프의 일종이다.

 

관련 용어

- node(노드): 트리의 구성 요소

- edge(간선): 노드와 노드를 연결하는 연결선

- root node: 트리 구조에서 최상위에 존재하는 노드

- internal node(내부 노드): 잎 노드가 아닌 모든 노드

- leaf node(잎 노드): 자식 노드가 없는 노드

- depth(깊이): 자신을 제외한 조상 노드의 개수

- node의 height(높이): (해당 node가 leaf node면 0) 해당 노드의 자식의 height 중 가장 높은 값 + 1

- Tree의 height(높이): 해당 트리의 루트의 height

 

문제를 풀다 보면 depth와 height의 용어의 정의가 충돌할 때도 있다.

하지만 이 글은 'Data Structures and Algorithms in C++ Second Edition - Michael T. Goodrich 외 2인'에 정의된 개념을 참고하여 쓴다.

아래는 직접 트리 각 노드의 height와 depth를 계산하여 표시한 그림이다.

 

 

 

 

트리는 재귀적이다.

하나의 트리는 여러 개의 sub tree(서브 트리)로 구성되어 있기 때문이다.

 

따라서 위의 그림처럼 각 노드의 height와 depth를 구할 때도 재귀적인 접근이 필요하다.

 

1) Tree의 height 구하기

함수를 설계하기 전에 Tree의 height 정의를 다시 살펴보자.

 

Tree의 height란 root node의 height인데 이는 max depth와 같다.

즉, root node로부터 leaf node까지 재귀가 진행되며 최댓값이 나올 때마다 전역에 선언된 최종 답을 갱신해준다.

 

class Solution {
public:
	int answer = 0;
	void findMaxDepth(TreeNode* nd, int depth) {
		//return 조건 : 해당 nd가 leaf node일 때 함수를 끝낸다
		if (nd==NULL) {
			return;
		}

		//답 갱신 과정
		if (answer<depth)answer = depth;

		if (nd->left != NULL) {
			findMaxDepth(nd->left, depth + 1);
		}
		if (nd->right != NULL) {
			findMaxDepth(nd->right, depth + 1);
		}
	}

	int maxDepth(TreeNode*root) {
		findMaxDepth(root, 0);
		return answer;
	}
};

 

2. 노드의 depth 구하기

 

각 노드의 depth는 root node로부터 자식 노드로 내려갈 때마다 depth가 1씩 추가된다.

즉, 재귀 함수의 return 조건을 해당 노드가 root node일 때 0을 return하는 것으로 설정하고

root node가 아닐 경우 재귀적으로 현재 노드의 부모 노드의 depth길이를 구해 1을 더한 값을 return한다.

 

int findDepth(Node* cur) {
		if (cur->par == NULL) {
			return 0;
		}
		return findDepth(cur->par) + 1;
}

 

아래 코드는 vector stl을 사용한 tree 구현 코드이다.

vector에 저장할 원소의 자료형은 Node형 포인터로 트리의 각 노드를 가리킨다.

또한 tree는 항상 root node로 1을 갖는다고 가정한다.

 

/*
20191111
Data Structure Tree Implementation
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
public:
	int data;
	Node* par;
	vector<Node*>child;

	Node(int data) {
		this->data = data;
		this->par = NULL;
	}
};

class Tree {
public:
	Node * root;
	vector<Node*>tree;

	Tree() {
		Node*root = new Node(1);
		tree.push_back(root);
	}

	void inssert(int child, int par) {
		for (int i = 0; i < tree.size(); ++i) {
			if (tree[i]->data == par) {
				Node*node = new Node(child);
				tree[i]->child.push_back(node);
				node->par = tree[i];
				tree.push_back(node);
				return;
			}
		}
	}

	Node* findNode(int data) {
		for (int i = 0; i < tree.size(); ++i) {
			if (tree[i]->data == data) {
				return tree[i];
			}
		}
		return NULL;
	}

	int findDepth(Node* cur) {
		if (cur->par == NULL) {
			return 0;
		}
		return findDepth(cur->par) + 1;
	}
};