----------------------------------------------
----------------------------------------------
트리는
나무처럼 가지가 연결되는 구조인데
대표적인 트리구조는 폴더구조가 있습니다.
트리는 계층적 관계를 만들때 쓰는 자료구조입니다.
계층적 관계란 영어로
hierachical relationship이라고 합니다.
히어라키칼 릴레이션십이라고 합니다.
트리의 용어들을 살펴보자면
최상위 노드를 루트 노드라고 합니다.
그 하위 노드를 자식노드라고 하며
왼쪽이 레프트 차일드
오른쪽이 라이트 차일드 입니다.
상위노드가 부모이고
하위노드가 자식입니다.
루트 노드부터 레벨0이고
아래로 내려가면 레벨1
레벨2 이런식으로 됩니다.
같은 레벨에 있는 노드들을
형제 자매 노드라고 합니다.
영어로 시블링 노드입니다.
그리고 더이상 자식이 없는 노드를
단말 노드, 또는 잎 노드 라고 합니다.
영어로 리프 노드 라고 합니다.
그리고 루트 노드를 기준으로
왼쪽 서브트리
즉, 왼쪽 하위 트리
오른쪽 서브트리
즉, 오른쪽 하위 트리가 있습니다.
----------------------------------------------
첫 번째는,
자료구조 정의입니다.
노드 구조체를 정의하는데
이번에는
구조체의 구성요소로
데이터와
왼쪽 주소를 가지는 left 포인터
오른쪽 주소를 가지는 right 포인터가 있습니다.
----------------------------------------------
----------------------------------------------
----------------------------------------------
두 번째는,
트리노드를 생성하는
메이크 비트리 노드 함수를 구현하는 것입니다.
입력은 void이고
반환형은 트리노드 포인터 타입을 반환합니다.
구현방법은
함수 내부에서 동적할당으로 노드를 생성한다음
주소를 반환합니다.
반환된 주소는 main함수에 있는
트리노드 포인터가 넘겨받아
동적할당으로 생성된 노드를 가리키게 됩니다.
트리노드는 전역변수 버전으로
하면 매우 좋지 않은데
왜냐하면 전역변수로 하게되면
트리노드 마다 포인터가 필요하므로
너무 많은 전역변수가 생기게 됩니다.
그래서
바로 지역변수 버전을 사용합니다.
----------------------------------------------
----------------------------------------------
----------------------------------------------
세 번째는,
트리노드에 값을 설정하는 셋데이타
트리노드에서 값을 가져오는 겟데이타
함수 입니다.
----------------------------------------------
---------------------------------------
----------------------------------------------
----------------------------------------------
네 번째는,
트리노드의 왼쪽을 연결하는 함수를 구현하는 것입니다.
매개변수는 1차원 트리노드 포인터 2개가 있습니다.
부모가 될 노드
자식이 될 노드 입니다.
부모노드의 왼쪽에 자식을 연결합니다.
여기서 지역변수를 사용했는데
2차원 포인터를 쓰지 않은 이유를 잘 생각 해봅시다.
그림으로 살펴보면
첫번째 노드를 생성하고
두번째 노드를 생성하고
첫번째 노드의 왼쪽에
두번째 노드를 연결합니다.
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
다섯 번째는,
트리노드의 오른쪽을 연결하는 함수를 구현하는 것입니다.
매개변수는 1차원 트리노드 포인터 2개가 있습니다.
부모가 될 노드
자식이 될 노드 입니다.
부모노드의 오른쪽에 자식을 연결합니다.
여기서 지역변수를 사용했는데
2차원 포인터를 쓰지 않은 이유를 잘 생각 해봅시다.
그림으로 살펴보면
세번째 노드를 생성하고
첫번째 노드의 오른쪽에
세번째 노드를 연결합니다.
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
여섯번째는,
트리노드를 순회하는 함수를 만드는 것입니다.
순회란 traversal(트레벌설)이라고 하며
트리노드를 어떤 순서로 읽어들일 것이냐를
결정하는것을 말합니다.
일종의 순회공연 같은것입니다.
전위 순회는
(프리오더 트레벌설)이라고 하며
루트-왼쪽 서브트리-오른쪽서브트리 순서로 방문합니다.
중위 순회는
(인오더 트레벌설)이라고 하며
왼쪽 서브트리-루트-오른쪽서브트리 순서로 방문합니다.
후위 순회는
(포스트오더 트레벌설)이라고 하며
왼쪽 서브트리-오른쪽서브트리-루트 순서로 방문합니다.
----------------------------------------------
일단 전위순회부터 살펴보면
루트-왼쪽 서브트리-오른쪽 서브트리 순서로 진행하며
----------------------------------------------
전위 순회 동영상
루트 방문
왼쪽 서브트리에서
루트 방문
왼쪽,오른쪽
오른쪽 서브트리에서
루트 방문
왼쪽,오른쪽
----------------------------------------------
중위순회는
왼쪽 서브트리-루트-오른쪽 서브트리 순서로 진행하며
----------------------------------------------
중위 순회 동영상
왼쪽 서브트리에서
왼쪽,루트,오른쪽
그다음 루트 방문
오른쪽 서브트리에서
왼쪽,루트,오른쪽
----------------------------------------------
후위순회는
왼쪽 서브트리-오른쪽 서브트리-루트-순서로 진행하며
----------------------------------------------
후위 순회 동영상
왼쪽 서브트리에서
왼쪽,오른쪽
루트
오른쪽 서브트리에서
왼쪽,오른쪽
루트
루트방문
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
완성된 코드
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
----------------------------------------------
'자료구조' 카테고리의 다른 글
| [자료구조] 10장. 연결 리스트 큐 (지역변수) (Queue Linked List) (0) | 2020.04.10 |
|---|---|
| [자료구조] 9장. 연결 리스트 큐 (전역변수) (Queue Linked List) (0) | 2020.04.10 |
| [자료구조] 8장. 연결 리스트 스택 (지역변수) (Stack Linked List) (0) | 2020.04.10 |
| [자료구조] 7장. 연결 리스트 스택 (전역변수) (Stack Linked List) (0) | 2020.04.10 |
| [자료구조] 6장. 연결 리스트 설명과 구현 (Linked List) (0) | 2020.04.10 |
