본문 바로가기

부트캠프교육중301

트리 순회 -트리의 모든 노드를 한번씩 방문하는 것. -모든 노드를 순회하는 방법엔 크게 세가지가 있다.(트리구조가 계층적구조라는 특별한 특징때문에) -전위 순회, 중위 순회, 후위 순회 -모두 노드를 순회할때 왼쪽부터 오른쪽으로 조회한다는 공통점이 있다. 전위 순회 (preorder traverse) -ABDHIEJK CFLMGNO -가장 먼저 방문하는 노드는 루트이다. -루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다. -부모 노드가 제일 먼저 방문되는 순회방식이다. -주로 트리를 복사할때 사용. 중위 순회 (inorder traverse) -HDIBJEKA LFMCNGO -제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드.. 2023. 3. 15.
이진트리, 이진탐색트리 -자식 노드가 최대 두개인 노드로 구성된 트리. 이 두개의 자식노드는 왼쪽 자식노드와 오른쪽 자식노드로 나눌수있다. -이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다. -자료의 삽입, 삭제 방법에 따라 정이진트리, 포화이진트리, 완전이진트리로 나뉜다. #특징 -정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. -포화 이진 트리(Perfect binary tree): 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져있는 트리이다. -완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨이 노드.. 2023. 3. 15.
tree #스택과 큐는 list자료구조의 특별한경우. 트리와 그래프는 비선형 자료구조의 특별한 경우. -나무를 거꾸로 뒤집어 놓은 듯한 모습.(하나의 뿌리로부터 가지가 사방으로 뻗은 형태) -그래프의 여러 구조중 단방향 그래프의 한 구조. -계층적 자료구조: 데이터가 바로 아래에 있는 하나 이상의 데이터에 한 개의 경로와 하나의 방향으로만 연결됨. -비선형구조: 데이터를 순차적으로 나열시킨 선형구조가 아니라, 하나의 데이터 아래에 여러개의 데이터가 존재할수있음(나뭇가지처럼) -계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클(cycle)이 없다. -사이클이 없는 하나의 연결 그래프(connected Graph)라고 할수있다. -사이클: 시작 노드에서 출발해 다른 노드를 거쳐 시작 노드로 .. 2023. 3. 15.
Queue Queue -줄을 서서 기다리다, 대기행렬 -톨게이트에 진입한 순서대로 통행료를 내고 톨게이트를 통과한다............. -톨게이트가 queue, 자동차 data -가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 통과한다. 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 빠져나가기전까지는 톨게이트를 빠져나갈수없다. # 구조 -stack과 반대되는 개념 -먼저 들어간 데이터가 먼저 나오는 FIFO(first in first out)혹은 LILO(last in last out)을 특징으로 가진다. -입력의 방향과 출력의 방향이 각각 고정되어있다.(영화관의 입구 하나, 출구 하나, 두 문은 다르다.) -데이터를 입력할 시에는 큐의 끝에서(tail), 테이터를 출력할때는 큐의 맨 앞에서 (head) 진.. 2023. 3. 14.

티스토리툴바