반응형 tree3 4-1. 이진 트리 (Binary Tree) 이진 트리란? 트리의 차수가 2인 트리. 트리를 구성하는 노드들의 자식은 최대 2개이다. 하나의 부모 노드에는 왼쪽, 오른쪽 자식이 존재하는 형태이다. 이진 트리의 형태 1. 정 이진 트리 (Full Binary Tree) 모든 노드의 차수가 2 혹은 0인 경우이다. 만약 자식이 하나만 존재하는 노드가 있다면, 정 이진 트리라고 할 수 없다. 위 같은 경우 차수가 1인 노드가 존재하지 않고, 리프 노드를 제외한 노드들의 자식은 모두 2개 이므로 정 이진 트리이다. 2. 포화 이진 트리 (Perfect Binary Tree) 정 이진 트리의 조건에 더하여 모든 리프 노드의 레벨이 같아야 한다. 우리가 생각하는 예쁘게 꽉 찬 트리의 모습이 포화 이진 트리이다. 3. 완전 이진 트리 (Complete B.. 2024. 7. 7. 4. 트리 (Tree) 트리란? 노드 간에 부모 - 자식 관계를 가지는 방향성이 있는 그래프. 한 부모 노드가 여러 개의 자식 노드를 가질 수 있기 때문에 비 선형 자료 구조이다. 항상 부모가 없는 가장 상위의 루트(root)노드로 부터 시작해 뻗어나가는 모양이 나무와 닮아 tree라는 이름이 붙었다. 트리의 용어 트리에는 사용의 편리함을 위해 사용하는 개념과 용어들이 있다. 아래 트리의 예시를 기준으로 설명하겠다. 1. 루트 노드 (root) : 부모가 없는 가장 최상위 노드. 위 트리에서는 가장 상단의 1번 노드이다. 2. 부모 노드 (parent) : 한 노드와 연결된 상위 노드. 예를 들어 2번 노드의 부모는 1번 노드이고, 6번 노드의 부모는 3번 노드이다. 3. 자식 노드 (child) : 한 노드와 연결된 .. 2024. 7. 6. [C] 학교과제_황제노드찾기 학교과제로 풀었던 황제노드찾기. 내부노드를 한 번 씩만 방문해 황제노드를 판별하는 방식이다. 순회 방식은 레벨순회이다. 황제노드 - 자신은 로만노드가 아니지만 자기 아래 자손들이 모두 로만노드인 노드로만노드 - 자신의 오른쪽과 왼쪽 부트리의 노드 개수 차이가 5 이하인 노드 구글링 해도 황제, 로만노드의 개념이 나오지 않는 것을 보면 교수님이 고안해내신 개념인 것 같다. #include #include #include #include typedef struct node { struct node *left; struct node *right; }NODE; typedef struct { NODE *root; }TREE; // 각 노드의 좌,우 자식 유무에 대한 정보를 담은 함수. initNode를 편리하게 .. 2018. 7. 1. 이전 1 다음 반응형
