알고리즘 서론 제10 장 10.4 뿌리 나무의 표시
1. 이 진 트 리
(1) 이 진 트 리 T 를 가리 키 는 아버지, 왼쪽 아들, 오른쪽 아들 을 도 메 인 p, left, right 로 저장 합 니 다.없 으 면 NULL.
(2) 결점 구조
struct node
{
node *p;
node *left;
node *right;
int key;
};(3) 나무의 구조
struct Bin_Tree
{
node *head;
};2. 가지 수 무한 한 뿌리 나무
(1) 왼쪽 아이 오른쪽 형제 표현법
(2) 결점 구조
struct node
{
node *p;
node *left_child;
node *right_sibling;
int key;
};(3) 나무의 구조
struct Tree
{
node *head;
};연습
10.4-2
알고리즘 서론 10.4 - 2 O (n) 시간 재 귀 이 진 트 리 옮 겨 다 니 기
TREE-PRINT(T)
1 print key[T]
2 if left[T] != NIL
3 TREE-PRINT(left[T])
4 if right[T] != NIL
5 TREE-PRINT(right[T])10.4-3
알고리즘 서론 10.4 - 3 O (n) 이 진 트 리 비 재 귀적 옮 겨 다 니 기
TREE-PRINT(T, S)
1 print key[T]
2 PUSH(S, T)
3 while true
4 if left[T] != NIL
5 then T <- left[T]
6 else
7 do
8 T = POP(S)
9 if T = NIL
10 then return
11 while left[T] = NIL
12 T <- right[T]10.4-4
이 진 트 리 의 옮 겨 다 니 는 과정 과 같 습 니 다.
10.4-5
알고리즘 서론 - 10.4 - 5 참조
중 서 를 옮 겨 다 니 는 것 과 유사 한 처리 방법 을 사용 하여 하나의 결점 에 대해 다음 과 같은 몇 가지 상황 으로 나 눌 수 있다.
1. 부 결점 에서 자 결점 으로 들 어가 처리
(1) 왼쪽 아이 가 있 으 면 왼쪽 아 이 를 처리한다.
(2) 자신 에 게 돌아 가기
(3) 자신 방문
(4) 오른쪽 아이 가 있 으 면 오른쪽 아 이 를 처리한다.
(5) 자신의 아버지 결점 으로 돌아간다.
2. 왼쪽 아이 에 게 서 돌아 오 는 것 은 왼쪽 아이 가 이미 처 리 했 고 자신 이 아직 방문 하지 않 았 으 며 자신의 오른쪽 아이 도 처리 하지 않 았 다 는 것 을 의미한다. 1 - (2)
3. 오른쪽 아이 에 게 서 돌아 온 다 는 것 은 좌우 아이 가 모두 처 리 했 고 자신 도 방 문 했 으 며 더 높 은 곳 으로 돌아 간 다 는 것 을 의미한다.
4. 뿌리 지점 으로 되 돌아 갈 때 옮 겨 다 니 기 끝
10.4-6
parent 지침 을 제거 합 니 다. 불 값 이 1 일 때 rightchild 는 부모 의 결점 을 가리 키 고 불 값 이 0 일 때 rightchild 는 오른쪽 형 제 를 가리 키 며 나머지 용법 은 변 하지 않 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
