tree

Binary Tree (이진트리) 이진트리 개념 이진트리는 우리가 이전에 배운 트리의 특수한 형태이다. 일반 트리가 자식 수에 제한이 없다면, 이진트리는 1부모에 최대 2개의 자식 노드가 존재한다. 보통 왼쪽 노드, 오른쪽 노드라고 부르며 왼쪽 노드가 오른쪽 노드보다 우선하는 성질을 가진다. 일반 트리에서 설명하지 않았지만 트리는 자식간에 순서가 있는 ordered pair이다. 이진트리의 쓰임새는 아래와 같은 것들이 있다. 수식의 표현 트리 수식의 계산 트리 결정트리 우선 결정트리부터 설명해보면 internal node는 결정요소를 갖고있고 external node는 해당 결정요소에대한 결정 값들을 갖고있다. 후에 서술할 중위순회를 이용하면 수식을 표현할 수 있다. 완전 이진트리의 성질 완전 이진트리는..

Tree (트리) 트리 개념 트리는 non linear data structure이다. 앞서서 배운 리스트, 배열, 벡터는 모두 linear data structure이고 이런 선형 자료구조들은 원소들 간에 전/후 관계가 있다. 그러나 non linear data structure, 즉 비선형 자료구조는 원소들 간에 상/하 관계를 가지고 있다. 이런 것을 계층적 관계라고한다. 일반 트리 (General Tree) 트리는 보통 general tree와 binary tree로 구분하는데, general tree는 자식노드의 수가 제한이 없는 트리를 말한다. binary tree는 말 그대로 이진트리로, 자식 노드가 딱 2개만 제한이 되는 트리이다. 굳이 말하면 이진트리도 일반트리에 포함되어있다. 트리는 노드..