알고리즘 복습)트리 기초

트리

 

트리란 계층적 구조를 갖는 데이터를 표현하기 위한 자료구조이다. 그래프와 동일하게 노드와 간선을 가지고 있으나, 계층이 있다는 점에서 그래프와 차별점을 갖는다.

 

트리의 특징

 

트리는 다음과 같은 특징을 갖는다.

1.오직 하나의 루트 노드를 갖는다.

2.루트노드와 자식노드들은 0개 이상의 자식을 갖는다.

3.모든 자식노드는 하나의 부모노드만을 갖는다.

4.N개의 노드가 있을경우 항상 N-1개의간선을 갖는다.

이진트리

 

트리 용어

 

루트 노드(root node) : 최상위 노드이며, 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node) : 자식이 없는 노드, leaf 노드라고도 부른다.
간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
형제(sibling): 같은 부모를 가지는 노드
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
서브 트리(SubTree): 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

 

트리 구현

 

 

포인터 구현

 

struct Node
{
	Node() {}
	Node(const string& data):data(data) {}
	string data;
	vector<Node*> child;
};

Node* CreateTree()
{
	Node* root = new Node("개발실");
	{
		Node* node=new Node("디자인");
		root->child.push_back(node);
		{
           		Node* leaf=new Node("전투");
          		node->child.push_back(leaf);
           		Node* leaf=new Node("스토리");
           		node->child.push_back(leaf);
           
		
		}
        Node* node=new Node("프로그래밍");
		root->child.push_back(node);
	}
	return root;
}

 

스마트 포인터 구현

 

using Noderef = shared_ptr<struct Node>;

struct Node
{
	Node() {}
	Node(const string& data):data(data) {}
	string data;
	vector<Noderef>child2;
};

Noderef CreateTree2()
{
	Noderef root = make_shared<Node>("개발실");
	{
		Noderef node = make_shared<Node>("디자인팀");
		root->child2.push_back(node);
		{
			Noderef leaf = make_shared<Node>("전투");
			node->child2.push_back(leaf);
           	 	Noderef leaf = make_shared<Node>("스토리");
			node->child2.push_back(leaf);
		}
        Noderef node = make_shared<Node>("프로그래밍");
		root->child2.push_back(node);
	}
	return root;
}

 

트리 높이 계산

 

int GetHeight(Noderef node)
{
 int height=1;
 for(Noderef& child: node->child2)
 {
  height =max(height,GetHeight(child)+1);
 }
 return height;
}