티스토리 뷰

Develop Story/Data Structure & Algorithm

<뇌를 자극하는 알고리즘 #4>: 트리(LCRSTree) 퀴즈풀이

wisecow 2017. 7. 22. 19:11

Vitamin Quiz

 문제) 아래 예제 프로그램에서 특정 레벨의 모든 노드를 출력하는 함수 LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level)를 작성하라. 함수의 원형은 다음과 같다.

void LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level);


풀이 // 이 글은 드래그 및 복붙이 안되므롤 아래 첨부한 파일을 다운받아 보시기 바랍니다. 첫 번째는 교재의 소스코드, 두 번째는 데브맷의 풀이 소스입니다.

이 문제의 핵심은 원하는 레벨의 모든 노드를 출력하기 위해서는 부모노드의 정보를 기억할 필요가 있다는 겁니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/*************************************************
 ** LCRSTree Vitamin Quiz
*************************************************/
 
#include <stdio.h>
#include <stdlib.h>
 
typedef char ElementType;
 
typedef struct tagLCRSNode
{
  struct tagLCRSNode* LeftChild;
  struct tagLCRSNode* RightSibling;
 
  ElementType Data;
} LCRSNode;
 
 
LCRSNode* LCRS_CreateNode(ElementType NewData);
void      LCRS_DestroyNode(LCRSNode* Node);
void      LCRS_DestroyTree(LCRSNode* Root);
 
void      LCRS_AddChildNode(LCRSNode* ParentNode, LCRSNode *ChildNode);
void      LCRS_PrintTree(LCRSNode* Node, int Depth);
 
LCRSNode* LCRS_CreateNode(ElementType NewData)
{
  LCRSNode* NewNode = (LCRSNode*)malloc(sizeof(LCRSNode));
  NewNode->LeftChild = NULL;
  NewNode->RightSibling = NULL;
  NewNode->Data = NewData;
 
  return NewNode;
}
 
void LCRS_DestroyNode(LCRSNode* Node)
{
  free(Node);
}
 
void LCRS_DestroyTree(LCRSNode* Root)
{
  if (Root->RightSibling != NULL)
    LCRS_DestroyTree(Root->RightSibling);
 
  if (Root->LeftChild != NULL)
    LCRS_DestroyTree(Root->LeftChild);
 
  Root->LeftChild = NULL;
  Root->RightSibling = NULL;
 
  LCRS_DestroyNode(Root);
}
 
void LCRS_AddChildNode(LCRSNode* Parent, LCRSNode *Child)
{
  if (Parent->LeftChild == NULL)
  {
    Parent->LeftChild = Child;
  }
  else
  {
    LCRSNode* TempNode = Parent->LeftChild;
    while (TempNode->RightSibling != NULL)
      TempNode = TempNode->RightSibling;
 
    TempNode->RightSibling = Child;
  }
}
 
void LCRS_PrintTree(LCRSNode* Node, int Depth)
{
  int i = 0;
  for (i = 0; i<depth; i++)="" printf("="" ");="" printf("%c\n",="" node-="">Data);
 
  if (Node->LeftChild != NULL)
    LCRS_PrintTree(Node->LeftChild, Depth + 1);
 
  if (Node->RightSibling != NULL)
    LCRS_PrintTree(Node->RightSibling, Depth);
}
 
 
 
void LCRS_PrintNodesAtLevel(LCRSNode *Root, int Level)
{
  int i;
  LCRSNode *Parent = NULL;
  Level--;
  while (Level--) // 바로 전 부모까지 이동
  {
    Root = Root->LeftChild;
  }
  Parent = Root; // 바로 전 부모 정보 저장
 
  for (i = 0; i < Level; i++)
    printf(" ");
 
  while (Parent) { // 부모 또한 우측으로 계속 이동한다는 게 핵심입니다.
    while (Parent->LeftChild) { // 각 부모별로 왼쪽 자식부터 오른쪽 자식까지 순회합니다.
      printf("%c ", Parent->LeftChild->Data);
      Parent->LeftChild = Parent->LeftChild->RightSibling;
    }
    Parent = Parent->RightSibling; // 부모를 우측으로 이동합니다.
  }
}
 
int main(void)
{
  /*  노드 생성 */
  LCRSNode* Root = LCRS_CreateNode('A');
 
  LCRSNode* B = LCRS_CreateNode('B');
  LCRSNode* C = LCRS_CreateNode('C');
  LCRSNode* D = LCRS_CreateNode('D');
  LCRSNode* E = LCRS_CreateNode('E');
  LCRSNode* F = LCRS_CreateNode('F');
  LCRSNode* G = LCRS_CreateNode('G');
  LCRSNode* H = LCRS_CreateNode('H');
  LCRSNode* I = LCRS_CreateNode('I');
  LCRSNode* J = LCRS_CreateNode('J');
  LCRSNode* K = LCRS_CreateNode('K');
 
  /*  트리에 노드 추가 */
  LCRS_AddChildNode(Root, B);
  LCRS_AddChildNode(B, C);
  LCRS_AddChildNode(B, D);
  LCRS_AddChildNode(D, E);
  LCRS_AddChildNode(D, F);
 
  LCRS_AddChildNode(Root, G);
  LCRS_AddChildNode(G, H);
 
  LCRS_AddChildNode(Root, I);
  LCRS_AddChildNode(I, J);
  LCRS_AddChildNode(J, K);
 
  /*  트리 출력 */
  LCRS_PrintTree(Root, 0);
  LCRS_PrintNodesAtLevel(Root, 2); // 비타민 퀴즈 실험부분
 
  /*  트리 소멸시키기 */
  LCRS_DestroyTree(Root);
 
  return 0;
}
 
/*************************************************
 ** End Line
*************************************************/
</depth;>

데브맷 풀이.c


저작자표시 비영리

'Develop Story > Data Structure & Algorithm' 카테고리의 다른 글

<알고리즘: 삽입정렬> 기본개념과 설명 및 코드  (0) 2017.07.23
<뇌를 자극하는 알고리즘 #5>: 버블정렬(BubbleSort) 퀴즈풀이  (0) 2017.07.23
<뇌를 자극하는 알고리즘 #3>: 배열로 구현된 스택(AS) 퀴즈풀이  (0) 2017.07.22
<뇌를 자극하는 알고리즘 #2>: 이중 연결 리스트(DLL) 퀴즈풀이  (0) 2017.07.22
<뇌를 자극하는 알고리즘 #1>: 단일 연결 리스트(SLL) 퀴즈풀이  (0) 2017.07.21
공유하기 링크
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday