비선형 자료구조

그래프란?그래프는 정점(Vertex, Node)과 간선(Edge)로 이루어진 비선형 자료구조이다.여러 개의 노드가 서로 연결된 상태의 자료구조를 의미하며, 모든 노드가 연결되어 있지는 않다. 루트 노드가 없고, 부모-자식 관계가 없다는 것에서 트리와의 차이점이 발생한다. 그래프와 트리의 차이점 그래프트리정의노드(Node)와 노드를 연결하는 간선(Edge)을 하나로 모아둔 자료구조그래프의 한 종류로, DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류방향성방향 그래프(Directed)무방향 그래프(Undirected) 모두 존재방향 그래프(Directed)만 존재사이클사이클(Cycle) 가능, 자체 간선(Self-loop) 가능,순환(Cyclic), 비순환(Acyc..

이진트리란? 각 노드가 최대 2개의 자식을 갖는 트리이다. 하나의 노드의 자식이 3개 이상은 이진트리로 볼 수 없다. 이진트리의 특징 각 노드는 최대 2개의 자식을 가질 수 있으며, 왼쪽과 오른쪽 자식노드로 구분한다. 순회 방법은 전위 순회, 중위 순회, 후위 순회가 있다. 이진트리의 종류 전이진트리(Full Binary Tree or Strict Binary Tree) 모든 노드의 자식이 0개, 또는 2개의 자식을 갖는 트리를 말한다. 왼쪽 이미지의 경우, J의 노드가 K라는 자식을 갖고 있기 때문에 전이진트리가 성립하지 않는다. 오른쪽 이미지의 경우, 각 노드가 0개 또는 2개의 자식을 갖고있으므로 전이진트리가 성립한다. 완전이진트리(Complete Binary Tree) 마지막 레벨을 제외하고 모든..

트리란 트리는 그래프의 일종으로, 노드로 이루어진 계층적 구조이다. 한 노드를 시작으로 다른 노드를 순회하며 자기 자신에게 돌아오는 순환 없는 연결 그래프이다. 트리의 용어 루트 노드(Root Node): 트리 구조의 최상위 노드로, 모든 다른 노드들은 이 루트 노드에서 시작된다. 부모 노드(Parent Node): 다른 노드에게 연결된 상위 노드를 가리킨다. 자식 노드(Child Node): 부모 노드에 의해 직접적으로 연결된 하위 노드를 말한다. 잎 노드(Leaf Node): 자식 노드가 없는 노드로, 트리 구조의 끝에 위치한다. 서브 트리(Subtree): 트리 안에서 다른 트리를 포함하는 부분 트리를 의미한다. 형제(Sibling): 같은 부모를 가진 노드를 의미한다. 간선(edge): 노드를 연..