자료구조 & 알고리즘9 이진 탐색 트리 특징, 노드삽입, 구현 ●이진탐색트리(Binary Search Tree : BST) -부모를 기준으로 왼쪽에 있는 노드들은 모두 부모보다 작은 데이터, 오른쪽은 부모보다 큰 데이터. ex) 22를 기준으로 왼쪽은 모두 22보다 작은 데이터, 오른쪽은 22보다 큰 데이터 -작으면 왼쪽, 크면 오른쪽에 위치하기 때문에 중복 데이터는 허용되지 않는다. ●노드삽입 방법 -루트부터 비교하면서 내려온다. 말단까지. ex) 8번노드 삽입하는 과정. 8은 22보다 작으니 왼쪽으로, 15보다 작으니 왼쪽으로, 7보다 크니 오른쪽으로, 10보다 작으니 왼쪽으로 가는데 10왼쪽 자리가 없다. 그래서 10의 왼쪽자리에 자식노드로 삽입이 된다. ●이진탐색트리 삽입을 코드로 구현 완성된 코드 typedef struct TREE { int value; .. 2023. 2. 22. 트리 순회 구현 -트리 순회 구현 typedef struct TREE { int value; struct TREE* left; struct TREE* right; } TREE; 먼저 TREE라는 구조체를 만들어 줍니다. value는 데이터값, left는 왼쪽자식, right는 오른쪽 자식을 의미합니다. void display(TREE* t) { if(t) { display(t->left); printf("%d", t->value); display(t->right); } } 루트의 주소를 담고 있는 t라는 포인터를 매개변수로 받는다. display(t->left)로 왼쪽 재귀호출, display(t->right)로 오른쪽 재귀호출을 함으로써 모든 노드를 방문할 수 있다. 출력하는 printf구문을 위 코드와 같이 두 di.. 2023. 2. 21. 트리의 용어, 종류, 트리 순회 ●트리의 용어 -트리 : 나무형태의 자료구조, 부모-자식의 관계로 이루어져있다. -루트(root) : 최상위 부모 -이진트리(binary tree) : 부모가 자식을 최대 2개 가지는 트리구조 cf)삼진트리 : 부모가 자식을 최대 3개 가진다. -서브트리 : 자식이 부모가 되어 다시 자식을 가지게 되면 서브트리가 형성되었다 라고 말한다. 위의 그림을 보면 D, E 노드는 B의 자식이다. 그런데 D는 다시 H, I 자식이 있으니 서브트리가 형성되었다. -리프(leaf) : 더이상 자식이 없는 노드를 말한다. 위의 그림을 보면 H, I, J, F, G는 그 밑에 자식이 없으니 리프이다. 나무를 거꾸로 만들어 놓았다고 생각하면 용어 이해가 쉽다. 나무의 맨 위의 자리에 뿌리가 있고 끝에는 잎사귀가 있다. 그래.. 2023. 2. 20. 이전 1 2 다음
