-
2022.06.04
[Python] 이진 트리(Binary Tree)
이진 트리(Binary Tree) 이진 트리(Binary Tree)의 기본 이진 트리의 개념 트리(Tree) 자료구조는 나무를 거꾸로 뒤집어 놓은 형태이다. 트리의 맨 위를 뿌리(Root, 루트)라고 한다. 루트를 레벨 0으로 두고 나뭇잎(Leaf, 리프)에 해당하는 아래로 내려올 수록 레벨이 1씩 증가한다. 트리에서 각 위치를 노드(Node)라고 한다. 각 노드는 선, 즉 에지(Edge)로 연결되어 있다. 위 노드와 바로 아래 노드의 관계를 부모-자식 관계(Parent-Child Relationship)라고 한다. 자식 노드의 개수를 차수(Degree)라고 한다. 차수가 0인 노드를 리프(Leaf)라고 한다. 트리의 차수는 차수가 가장 높은 노드를 기준으로 정한다. 컴퓨터는 데이터를 0과 1로 표현하므..
-
2021.05.15
[C++] 트리 순회(Tree Traversal)
트리 순회(Traversal) 트리 순회 방법 트리 순회 방법은 다음과 같이 4가지가 있음. 전위 순회(Preorder Traversal) 중위 순회(In-Order Traversal) 후위 순회(Post-Order Traversal) 레벨 순서 순회(Level Order Traversal) 전위 순회(Preorder Traversal) 재귀적 인 방식으로 다음의 노드를 방문함. ① 현재 노드 (C) ② 현재 노드의 왼쪽 하위 노드 (L) ③ 현재 노드의 오른쪽 하위 노드 (R) 전위(Pre) 상위 노드를 하위 노드보다 먼저 방문한다는 뜻 전위 순회는 항상 부모 노드 를 방문한 다음, 왼쪽자식 노드, 오른쪽 자식 노드를 차례로 방문함. 이러한 방식의 순회를 루트 노드에서만 수행하는 것이 아니라, 루트 노..
-
2021.05.15
[C++] 조직 구조도 만들기 (이진 트리 이용)
조직 구조도 만들기 (이진 트리 이용) 서론 트리(Tree) 자료구조를 이용하여 조직 구조도를 만들어보자. 이진 트리(Binary Tree)를 이용하고, 1명의 상사 직원 밑에 2명의 부하 직원을 둘 수 있다고 가정한다. 상사 직원이 없을 경우, 부하 직원을 추가할 수 없다. 코드 #include #include struct node { std::string position; node* first; node* second; }; struct org_tree { node* root; static org_tree create_org_structure(const std::string& pos) { org_tree tree; tree.root = new node {pos, NULL, NULL}; return t..
