Geunhyung Kim, profile picture
Uploaded byGeunhyung Kim
294 views

6. binary tree

1. The document introduces binary trees, including common tree terminology like nodes, edges, root, parent, child, leaf, and subtree. 2. It explains different ways to traverse a binary tree, including in-order, pre-order, and post-order traversal. 3. It also covers level order traversal using a queue, where nodes are added level by level from left to right.

Downloaded 16 times
1 / 133
2 / 133
3 / 133
4 / 133
5 / 133
6 / 133
7 / 133
8 / 133
9 / 133
10 / 133
11 / 133
12 / 133
13 / 133
14 / 133
15 / 133
16 / 133
17 / 133
18 / 133
19 / 133
20 / 133
21 / 133
22 / 133
23 / 133
24 / 133
25 / 133
26 / 133
27 / 133
28 / 133
29 / 133
30 / 133
31 / 133
32 / 133
33 / 133
34 / 133
35 / 133
36 / 133
37 / 133
38 / 133
39 / 133
40 / 133
41 / 133
42 / 133
43 / 133
44 / 133
45 / 133
46 / 133
47 / 133
48 / 133
49 / 133
50 / 133
51 / 133
52 / 133
53 / 133
54 / 133
55 / 133
56 / 133
57 / 133
58 / 133
59 / 133
60 / 133
61 / 133
62 / 133
63 / 133
64 / 133
65 / 133
66 / 133
67 / 133
68 / 133
69 / 133
70 / 133
71 / 133
72 / 133
73 / 133
74 / 133
75 / 133
76 / 133
77 / 133
78 / 133
79 / 133
80 / 133
81 / 133
82 / 133
83 / 133
84 / 133
85 / 133
86 / 133
87 / 133
88 / 133
89 / 133
90 / 133
91 / 133
92 / 133
93 / 133
94 / 133
95 / 133
96 / 133
97 / 133
98 / 133
99 / 133
100 / 133
101 / 133
102 / 133
103 / 133
104 / 133
105 / 133
106 / 133
107 / 133
108 / 133
109 / 133
110 / 133
111 / 133
112 / 133
113 / 133
114 / 133
115 / 133
116 / 133
117 / 133
118 / 133
119 / 133
120 / 133
121 / 133
122 / 133
123 / 133
124 / 133
125 / 133
126 / 133
127 / 133
128 / 133
129 / 133
130 / 133
131 / 133
132 / 133
133 / 133
?Sa @ea U CW ME;D 8 U =aW M WbS W e Introduction to Tree/Binary Tree
L SS h *3 tp g v h p v 3 gp s n v 3 p n s v v 3 n k
g SRUS n SOT RS W S O RS g k t 내부 노드
O S n : ; 9 g Q W R n 9 : ; WP W U g … O QS RSQS RO k t 형제 노드 C의 자식 노드 자손 노드 H, I, J 의 부모 노드 모든 노드의 조상 노드
aP SS w > S k RSU SS SbS * y p SWU k 루트 루트 루트 트리1 트리2 트리3 레벨 1 레벨 2 레벨 3 레벨 4 차수: 3 차수: 2 차수: 3 차수: 1 차수: 2 트리의 높이: 4 t 포리스트
:W O e L SS + g + g tp3 * + p v g r x 3 gp v 3 n k
k g * k SRUS g *k g n k g g g g k k k + * k g g g k g y k +k g + * K 3 K 5 * + - 1 f + * 5 + * k
>a :W O e L SS g 3 + g k g + * * + * g * + , - . / 0 k g Fk
* + , - . / N개의 노드로 포화 이진 트리 또는 완전 이진 트리를 구성할 때 이진 트리의 높이는 log2N 임 ; S S :W O e L SS g g k + * + * k * + * g
K Sc :W O e L SS k g g g k g * g
3 X y b + c a / * + (x+y)*((a+b)/c)
3 n
3 93 -) :3 +) ;3 *) 3 *) J3 +) A B C D R (40) (20) (10) (10) (20) (20) -) /) *)) 0 1 10 11 111 110 1100 1101 A: 0 B: 10 C: 1100 D: 1101 R: 111
* + , - . / 9 : ; = > ( )
typedef struct TreeNode { int data; struct TreeNode *left, *right; } TreeNode; 9 : ; 9 FMDD FMDD 9 FMDD FMDD = FMDD FMDD > FMDD
이진 트리 순회
p v m y l W RS ObS O S RS ObS O RS ObS O SbS RS ObS O 3 … 3 D … 3 J 3 k S bS O
3 k 현재 노드 ! ObS O
W RS ObS O * LD 3 D + 3 , LJ 3 J LD LJ + * 3.
W RS ObS O 6 6
W RS ObS O d inOrder (x) { if (x != NULL) { inOrder (x->left); print x; inOrder (x->right); } }
W RS ObS O d inOrder (x) { if (x != NULL) { inOrder (x->left); print x; inOrder (x->right); } } @ A : B = C 9 D > ; ?
S RS ObS O * 3 + LD 3 D , LJ 3 J 2. 1. 3.
S RS ObS O d preOrder (x) { if (x != NULL) { print x; preOrder (x->left); preOrder (x->right); } }
S RS ObS O d preOrder (x) { if (x != NULL) { print x; preOrder (x->left); preOrder (x->right); } } 9 : @ A = B C ; > D ?
RS ObS O * LD 3 D + LJ 3 J , 3 2.1. 3.
RS ObS O d postOrder (x) { if (x != NULL) { postOrder (x->left); postOrder (x->right); print x; } }
RS ObS O d postOrder (x) { if (x != NULL) { postOrder (x->left); postOrder (x->right); print x; } } @ A B C = : D > ? ; 9
SbS RS ObS O …
SbS RS ObS O … 9 : ; = > ? @ A B C D
level_order(x) { if (x == NULL) return; } NULL NULL NULL NULL NULL NULL NULL NULL SbS RS ObS O
level_order(x) { if (x == NULL) return; } NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B D x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE C x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEF C x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F G x = A; SbS RS ObS O
level_order(x) { if (x == NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F G x = A; SbS RS ObS O
Binary Search Tree
N O W O SO Q 7 >W RW U O SQWTWQ SQ R T O OP S O S T SQ R 3 l 9 SQ R Q W T S S TWS R 3 v L S SQ R T SdO S O O S ORR S aRS WRS WTWQO W a PS O R QWO SQa W e a PS S Q 3 L S Se W O TWS R a SR T RW Q W W O W U SQ R 9 O SdO S QWO SQa W e a PS aRS WRS WTWQO W a PS QO PS a SR O Se 3 v KSO Q 3 k KSO Q
y v Se Se Se Se Se s :KL 3 k :W O e KSO Q L SS ST aP SS aP SS WU
KSO Q 3 A S 3 S S S3 KSO Q A S S S S h SWU h 3 h :KL3 :W O e KSO Q L SS
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
y Se is Se is u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
:KL 3 i a a S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0
:KL 3 i a a S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
:KL 3 i a a S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
:KL 3 i a a S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
:KL 3 i a a S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
:KL 3 :KL KSO Q G S O W 3 L SSF RS 3 SO Q F RS L SSF RS W Se 4 + 3 RS Se i TreeNode* searchNode(TreeNode *root, int key) { if (root == NULL) return NULL; if (root->data == key) return root; else if (root->data > key) return searchNode(root->left, key); else return searchNode(root->right, key); } typedef struct TreeNode { int data; struct TreeNode *left, *right; }TreeNode;
:KL 3 :KL KSO Q G S O W 3 L SSF RS 3 SO Q F RS L SSF RS W Se 4 + 3 RS Se i TreeNode* searchNode(TreeNode *root, int key) { while (root != NULL) { if (root->data == key) return root; else if (root->data > key) root = root->left; else root = root->right; } return NULL; }
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,,
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
:KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,) Q5) 29 를 삽입
:KL 3 :KL A S G S O W Se i y g g [ RS Se L FMDD l L SSF RS L SSF RS RO O o N Se L SSF RS 6 ST L SSF RS 6 WU ,, L L SSF RS n
:KL 3 :KL A S G S O W 3 b WR 3 W S F RS L SSF RS W Se 4 + 3 RS Se i void insertNode(TreeNode **root, int key){ TreeNode *parentNode = NULL, *currentNode, *newNode; currentNode = *root; while (currentNode != NULL) { if (currentNode->data == key) return; parentNode = currentNode; if (currentNode->data > key) currentNode = currentNode->left; else currentNode = currentNode->right; }
:KL 3 :KL A S G S O W 3 b WR 3 W S F RS L SSF RS W Se 4 + 3 RS Se i void insertNode(TreeNode **root, int key){ TreeNode *parentNode = NULL, *currentNode, *newNode; currentNode = *root; while (currentNode != NULL) { if (currentNode->data == key) return; parentNode = currentNode; if (currentNode->data > key) currentNode = currentNode->left; else currentNode = currentNode->right; } (( g (( o (( Seg s
:KL 3 newNode = (TreeNode *)malloc(sizeof(TreeNode)); if (newNode == NULL) return; newNode->data = key; newNode->left = newNode->right = NULL; if (parentNode != NULL) if (parentNode->data > key) parentNode->left = newNode; else parentNode->right = newNode; else *root = newNode; } :KL A S G S O W (( Se i o (( o L SSF RS rh s n n
:KL 3 :KL A S G S O W ,) -) +) *) +. ,.
:KL 3 :KL A S G S O W ,) -)+) *) +. ,.
y ,g o ] N L f ] N L U L 5314 6723 0 ] N L f ] N L f :KL 3 k :KL S S S G S O W *1 0 , *+ +/ ,* +0
y ,g o ] N L f ] N L U L 5314 6723 0 ] N L f ] N L f :KL 3 k :KL S S S G S O W *1 0 , *+ +/ ,* +0 I* +0 I+ +/ I, 0 Q4) 18 을 삽입
:KL 3 g ) * + g * o :KL S S S G S O W g ) * + 7
:KL 3 g ) o g * o L ] L L ,, l n ] L a :KL S S S G S O W g + o L ] ] L e [ L n ] L a L ] L [ L ] L L ] L [ d L ] L ] L a
:KL 3 :KL S S S G S O W 3 b WR 3 RS S SF RS L SSF RS W Se 4 + 3 RS Se i void deleteNode(TreeNode **root, int key){ TreeNode *pNode = NULL, *curNode, *newNode; TreeNode *child, *succ; *succParent; curNode = *root; while (curNode != NULL && curNode->data != key) { pNode = curNode; if (curNode->data > key) curNode = curNode->left; else curNode = curNode->right; } if (curNode == NULL) { printf(“key is not int the treen”); return; }
:KL 3 if (curNode->left == NULL && curNode->left == NULL){ if (pNode != NULL) if (pNode->left == curNode) pNode->left = NULL; else pNode->right = NULL; else *root = NULL; } else if (curNode->left == NULL || curNode->left == NULL){ child = (curNode->left != NULL) ? curNode->left : curNode->right; if (pNode != NULL) { if (pNode->left == curNode) pNode->left = NULL; else pNode->right = NULL; } else *root = NULL; } :KL S S S G S O W
:KL 3 else { succParent = curNode; succ = curNode->left; while (succ->right != NULL) { succParent = succ; succ = succ->right; } if (succParent->right == succ) succParent->right = succ->left; else succParent->left = succ->left; curNode->data = succ->data; curNode = succ; } free(curNode); } :KL S S S G S O W (( g + o (( aQQHO S (( y (( h *1 0 , *+ +/ ,* */*) *, *1 *0 2 +/ ,* 1 aQQ aQQ
:KL o (( )( ( 6 82 35 01 4 9 ) (( )( ( )
:KL g k o
:KL g +k o (( )( ( ( 6 941 0 8 ) (( )( ( ( 5 32 )
:KL g +k o (( )( ( ( 3 68 012 ) (( )( ( ( 5 64 9 2 )

More Related Content

PPT
Link list part 2
byAnaya Zafar
 
PPT
Doublylinklist
byritu1806
 
PDF
The Ring programming language version 1.6 book - Part 84 of 189
byMahmoud Samir Fayed
 
DOCX
ภาษา C โปรแกรมย่อยและฟังก์ชันมาตรฐาน
byNoppanon YourJust'one
 
PDF
GeoGebra JavaScript CheatSheet
byJose Perez
 
PDF
T3chFest 2016 - The polyglot programmer
byDavid Muñoz Díaz
 
PDF
GUL UC3M - Introduction to functional programming
byDavid Muñoz Díaz
 
DOC
week-16x
byKITE www.kitecolleges.com
 
Link list part 2
byAnaya Zafar
 
Doublylinklist
byritu1806
 
The Ring programming language version 1.6 book - Part 84 of 189
byMahmoud Samir Fayed
 
ภาษา C โปรแกรมย่อยและฟังก์ชันมาตรฐาน
byNoppanon YourJust'one
 
GeoGebra JavaScript CheatSheet
byJose Perez
 
T3chFest 2016 - The polyglot programmer
byDavid Muñoz Díaz
 
GUL UC3M - Introduction to functional programming
byDavid Muñoz Díaz
 
week-16x
byKITE www.kitecolleges.com
 

What's hot

ODP
Exploiting Memory Overflows
byAnkur Tyagi
 
PDF
The best language in the world
byDavid Muñoz Díaz
 
PDF
Stack
bySwarup Kumar Boro
 
PDF
Что нам готовит грядущий C#7?
byAndrey Akinshin
 
PDF
Exploring slides
byakaptur
 
PPTX
Link list
bySyeda Javeria
 
PDF
Byterun, a Python bytecode interpreter - Allison Kaptur at NYCPython
byakaptur
 
PDF
.NET 2015: Будущее рядом
byAndrey Akinshin
 
PDF
Rainer Grimm, “Functional Programming in C++11”
byPlatonov Sergey
 
PDF
Lisp tutorial
byNilt1234
 
PDF
Faster Python, FOSDEM
byVictor Stinner
 
PPTX
โปรแกรมย่อยและฟังชันก์มาตรฐาน
byknang
 
PPTX
Stack using Linked List
bySayantan Sur
 
PDF
Diving into byte code optimization in python
byChetan Giridhar
 
PPT
Stack queue
byHarry Potter
 
Exploiting Memory Overflows
byAnkur Tyagi
 
The best language in the world
byDavid Muñoz Díaz
 
Stack
bySwarup Kumar Boro
 
Что нам готовит грядущий C#7?
byAndrey Akinshin
 
Exploring slides
byakaptur
 
Link list
bySyeda Javeria
 
Byterun, a Python bytecode interpreter - Allison Kaptur at NYCPython
byakaptur
 
.NET 2015: Будущее рядом
byAndrey Akinshin
 
Rainer Grimm, “Functional Programming in C++11”
byPlatonov Sergey
 
Lisp tutorial
byNilt1234
 
Faster Python, FOSDEM
byVictor Stinner
 
โปรแกรมย่อยและฟังชันก์มาตรฐาน
byknang
 
Stack using Linked List
bySayantan Sur
 
Diving into byte code optimization in python
byChetan Giridhar
 
Stack queue
byHarry Potter
 

Viewers also liked

PDF
Curriculam Vitae_ Dhyanesh Singh
byDhyanesh Singh
 
PDF
Arizona divorce law
byThomas Mastromatto NMLS #145824
 
DOC
LinkedIn Profile.doc-SABARI
bySabari parasuram G
 
DOCX
Q4
bybrookemedia
 
PDF
FINAL RR INFO GRAPH
byMark Richard Dagel
 
PDF
CDLP
byThomas Mastromatto NMLS #145824
 
PPTX
Speech 5 -tis the season (1)
byaas24118
 
PDF
Arizona supreme court divorce booklet
byThomas Mastromatto NMLS #145824
 
PDF
Tibau,carmen
byESO1
 
PDF
3. linked list
byGeunhyung Kim
 
PDF
اشتباهات امنیتی در سفر
byAila Sayyadi
 
PPTX
Otitis media crónica supurada
byDianaBlasto
 
PDF
Binary tree
byRajendran
 
PPT
Binary trees
bySimratpreet Singh
 
PPTX
School Prospectus Research
bydanieswallow98
 
PPTX
Altar de Muertos
byErika Said
 
PPTX
Cse Binary tree presentation
byসৈয়দ সাব্বির রহমান
 
PPT
binary tree
byShankar Bishnoi
 
PPTX
Binary tree and Binary search tree
byMayeesha Samiha
 
PPTX
Film poster analysis success criteria
byCoombeMedia1
 
Curriculam Vitae_ Dhyanesh Singh
byDhyanesh Singh
 
Arizona divorce law
byThomas Mastromatto NMLS #145824
 
LinkedIn Profile.doc-SABARI
bySabari parasuram G
 
Q4
bybrookemedia
 
FINAL RR INFO GRAPH
byMark Richard Dagel
 
CDLP
byThomas Mastromatto NMLS #145824
 
Speech 5 -tis the season (1)
byaas24118
 
Arizona supreme court divorce booklet
byThomas Mastromatto NMLS #145824
 
Tibau,carmen
byESO1
 
3. linked list
byGeunhyung Kim
 
اشتباهات امنیتی در سفر
byAila Sayyadi
 
Otitis media crónica supurada
byDianaBlasto
 
Binary tree
byRajendran
 
Binary trees
bySimratpreet Singh
 
School Prospectus Research
bydanieswallow98
 
Altar de Muertos
byErika Said
 
Cse Binary tree presentation
byসৈয়দ সাব্বির রহমান
 
binary tree
byShankar Bishnoi
 
Binary tree and Binary search tree
byMayeesha Samiha
 
Film poster analysis success criteria
byCoombeMedia1
 

Similar to 6. binary tree

PDF
My C proggram is having trouble in the switch in main. Also the a co.pdf
bymeerobertsonheyde608
 
DOCX
10 Solution#include-iostream-h- #include-conio-h- #include-process-h-.docx
bytodd991
 
PDF
Please write in C++ and should be able to compile and debug.Thank yo.pdf
byajaycosmeticslg
 
PDF
program on string in java Lab file 2 (3-year)
byAnkit Gupta
 
PDF
Inserindo em Ordem Crescente na Lista Encadeada
byElaine Cecília Gatto
 
PPTX
Binary search tree.pptx
bySanthiya S
 
PDF
Write a C++ program that implements a binary search tree (BST) to man.pdf
byhardjasonoco14599
 
PDF
CODE#include stdlib.h #include stdio.hstruct task{proce.pdf
byfathimalinks
 
PPTX
Binary tree
byraviahuja11
 
PDF
#include <stdio.h> #include <malloc.h> #define ISEMP.pdf
byharihelectronicspune
 
PPTX
Stack, Queue, Linked List.pptx
byBharati Vidyapeeth COE, Navi Mumbai
 
PPTX
Stack, queue, linked list
bySonali Mhatre
 
PDF
Consider an extension of the queue abstract data type, called a .pdf
byarorasales234
 
PDF
includestdio.h #includestdlib.h int enqueue(struct node ,.pdf
bygalagirishp
 
DOCX
Avl tree
byloyola ICAM college of engineering and technology
 
PPTX
Double linked list
byraviahuja11
 
PDF
寫程式？那些老師沒教的事 (Git 部分節錄)
by均民 戴
 
PPTX
Binary Search Tree
byraviahuja11
 
DOCX
Artificial intelligence
byAditya Sharma
 
DOCX
Data structure lab on practical computer science.docx
bynishapatil20005
 
My C proggram is having trouble in the switch in main. Also the a co.pdf
bymeerobertsonheyde608
 
10 Solution#include-iostream-h- #include-conio-h- #include-process-h-.docx
bytodd991
 
Please write in C++ and should be able to compile and debug.Thank yo.pdf
byajaycosmeticslg
 
program on string in java Lab file 2 (3-year)
byAnkit Gupta
 
Inserindo em Ordem Crescente na Lista Encadeada
byElaine Cecília Gatto
 
Binary search tree.pptx
bySanthiya S
 
Write a C++ program that implements a binary search tree (BST) to man.pdf
byhardjasonoco14599
 
CODE#include stdlib.h #include stdio.hstruct task{proce.pdf
byfathimalinks
 
Binary tree
byraviahuja11
 
#include <stdio.h> #include <malloc.h> #define ISEMP.pdf
byharihelectronicspune
 
Stack, Queue, Linked List.pptx
byBharati Vidyapeeth COE, Navi Mumbai
 
Stack, queue, linked list
bySonali Mhatre
 
Consider an extension of the queue abstract data type, called a .pdf
byarorasales234
 
includestdio.h #includestdlib.h int enqueue(struct node ,.pdf
bygalagirishp
 
Avl tree
byloyola ICAM college of engineering and technology
 
Double linked list
byraviahuja11
 
寫程式？那些老師沒教的事 (Git 部分節錄)
by均民 戴
 
Binary Search Tree
byraviahuja11
 
Artificial intelligence
byAditya Sharma
 
Data structure lab on practical computer science.docx
bynishapatil20005
 

More from Geunhyung Kim

PDF
7. sorting
byGeunhyung Kim
 
PDF
5.node js
byGeunhyung Kim
 
PDF
5. queue
byGeunhyung Kim
 
PDF
4. stack
byGeunhyung Kim
 
PDF
1. introduction to algorithm
byGeunhyung Kim
 
PDF
11. git basic
byGeunhyung Kim
 
7. sorting
byGeunhyung Kim
 
5.node js
byGeunhyung Kim
 
5. queue
byGeunhyung Kim
 
4. stack
byGeunhyung Kim
 
1. introduction to algorithm
byGeunhyung Kim
 
11. git basic
byGeunhyung Kim
 

Recently uploaded

PPTX
Environmental Degradation and Pollution
bySheila Mae Ellima
 
PPTX
Composition and characteristics of blood
byManarat International University
 
PDF
Tonometry ppt_slide_Notes_download .pdf
byAnmol Singh
 
PDF
Lehigh University Eng. Programs for Thailand
bycama23
 
PPTX
English Home Language & First Additional Language P2 Preparation.pptx
byMasingita Maswanganye
 
PPTX
Presentation one The History of Eugenics
bymbuyisaandiswa81
 
PPTX
Cartoon Revisions and Advertisement Grade 10
byBathabile Ngcobo
 
PDF
Hit The Homerun FINAl- A U25 sorts quiz of Jigisha 4.0 organized by Pragya, ...
byPragya - UEM Kolkata Quiz Club
 
PPTX
YSPH VMOC Special Report - Measles - The Americas -10-19-2025.pptx
byYale School of Public Health - The Virtual Medical Operations Center (VMOC)
 
PPTX
Discharge procedure.................pptx
byAneetaSharma15
 
PPTX
How to Configure Custom Addons Path in Odoo 18
byCeline George
 
PPTX
Types of contract under Indian Contract Law.pptx
byKeerthana Chinnathambi
 
PDF
Hit The Homerun Prelims- A U25 sports quiz of Jigisha 4.0 organized by Pragya...
byPragya - UEM Kolkata Quiz Club
 
PPTX
ZULU METHODOLOGY 3B MICRO LESSON PRESENTATION.pptx
bySiphokazi Ncobela
 
PDF
President John Dramani Mahama has declared three days of national mourning fo...
bynservice241
 
PPTX
Quiz-O-Force Diwali Quiz Final Round.pptx
bySourav Kr Podder
 
PPTX
Mary Shelley's Frankenstein. Gothic novel characteristics.
byRaquel FC
 
PPTX
Isikhangisi .pptx....ukubaluleka kokwazi isikhangiso.
byKwanele28
 
PDF
Science, Education and Innovations in the Context of Modern Problems, Issue 1...
byRahilNecef
 
PPTX
Quiz-O-Force Diwali Quiz Preliminary.pptx
bySourav Kr Podder
 
Environmental Degradation and Pollution
bySheila Mae Ellima
 
Composition and characteristics of blood
byManarat International University
 
Tonometry ppt_slide_Notes_download .pdf
byAnmol Singh
 
Lehigh University Eng. Programs for Thailand
bycama23
 
English Home Language & First Additional Language P2 Preparation.pptx
byMasingita Maswanganye
 
Presentation one The History of Eugenics
bymbuyisaandiswa81
 
Cartoon Revisions and Advertisement Grade 10
byBathabile Ngcobo
 
Hit The Homerun FINAl- A U25 sorts quiz of Jigisha 4.0 organized by Pragya, ...
byPragya - UEM Kolkata Quiz Club
 
YSPH VMOC Special Report - Measles - The Americas -10-19-2025.pptx
byYale School of Public Health - The Virtual Medical Operations Center (VMOC)
 
Discharge procedure.................pptx
byAneetaSharma15
 
How to Configure Custom Addons Path in Odoo 18
byCeline George
 
Types of contract under Indian Contract Law.pptx
byKeerthana Chinnathambi
 
Hit The Homerun Prelims- A U25 sports quiz of Jigisha 4.0 organized by Pragya...
byPragya - UEM Kolkata Quiz Club
 
ZULU METHODOLOGY 3B MICRO LESSON PRESENTATION.pptx
bySiphokazi Ncobela
 
President John Dramani Mahama has declared three days of national mourning fo...
bynservice241
 
Quiz-O-Force Diwali Quiz Final Round.pptx
bySourav Kr Podder
 
Mary Shelley's Frankenstein. Gothic novel characteristics.
byRaquel FC
 
Isikhangisi .pptx....ukubaluleka kokwazi isikhangiso.
byKwanele28
 
Science, Education and Innovations in the Context of Modern Problems, Issue 1...
byRahilNecef
 
Quiz-O-Force Diwali Quiz Preliminary.pptx
bySourav Kr Podder
 

6. binary tree

  • 1.
    ?Sa @ea UCW ME;D 8 U =aW M WbS W e Introduction to Tree/Binary Tree
  • 2.
    L SS h *3tp g v h p v 3 gp s n v 3 p n s v v 3 n k
  • 3.
    g SRUS n SOT RS W SO RS g k t 내부 노드
  • 4.
    O S n :; 9 g Q W R n 9 : ; WP W U g … O QS RSQS RO k t 형제 노드 C의 자식 노드 자손 노드 H, I, J 의 부모 노드 모든 노드의 조상 노드
  • 5.
    aP SS w > S k RSUSS SbS * y p SWU k 루트 루트 루트 트리1 트리2 트리3 레벨 1 레벨 2 레벨 3 레벨 4 차수: 3 차수: 2 차수: 3 차수: 1 차수: 2 트리의 높이: 4 t 포리스트
  • 6.
    :W O eL SS + g + g tp3 * + p v g r x 3 gp v 3 n k
  • 7.
    k g *k SRUS g *k g n k g g g g k k k + * k g g g k g y k +k g + * K 3 K 5 * + - 1 f + * 5 + * k
  • 8.
    >a :W Oe L SS g 3 + g k g + * * + * g * + , - . / 0 k g Fk
  • 9.
    * + , - ./ N개의 노드로 포화 이진 트리 또는 완전 이진 트리를 구성할 때 이진 트리의 높이는 log2N 임 ; S S :W O e L SS g g k + * + * k * + * g
  • 10.
    K Sc :WO e L SS k g g g k g * g
  • 11.
  • 12.
  • 13.
    3 93 -) :3+) ;3 *) 3 *) J3 +) A B C D R (40) (20) (10) (10) (20) (20) -) /) *)) 0 1 10 11 111 110 1100 1101 A: 0 B: 10 C: 1100 D: 1101 R: 111
  • 14.
    * + , - ./ 9 : ; = > ( )
  • 15.
    typedef struct TreeNode{ int data; struct TreeNode *left, *right; } TreeNode; 9 : ; 9 FMDD FMDD 9 FMDD FMDD = FMDD FMDD > FMDD
  • 16.
  • 17.
    p v m yl W RS ObS O S RS ObS O RS ObS O SbS RS ObS O 3 … 3 D … 3 J 3 k S bS O
  • 18.
  • 19.
    W RS ObSO * LD 3 D + 3 , LJ 3 J LD LJ + * 3.
  • 20.
    W RS ObSO 6 6
  • 21.
    W RS ObSO d inOrder (x) { if (x != NULL) { inOrder (x->left); print x; inOrder (x->right); } }
  • 22.
    W RS ObSO d inOrder (x) { if (x != NULL) { inOrder (x->left); print x; inOrder (x->right); } } @ A : B = C 9 D > ; ?
  • 23.
    S RS ObSO * 3 + LD 3 D , LJ 3 J 2. 1. 3.
  • 24.
    S RS ObSO d preOrder (x) { if (x != NULL) { print x; preOrder (x->left); preOrder (x->right); } }
  • 25.
    S RS ObSO d preOrder (x) { if (x != NULL) { print x; preOrder (x->left); preOrder (x->right); } } 9 : @ A = B C ; > D ?
  • 26.
    RS ObS O *LD 3 D + LJ 3 J , 3 2.1. 3.
  • 27.
    RS ObS O d postOrder(x) { if (x != NULL) { postOrder (x->left); postOrder (x->right); print x; } }
  • 28.
    RS ObS O d postOrder(x) { if (x != NULL) { postOrder (x->left); postOrder (x->right); print x; } } @ A B C = : D > ? ; 9
  • 29.
  • 30.
    SbS RS ObSO … 9 : ; = > ? @ A B C D
  • 31.
    level_order(x) { if (x== NULL) return; } NULL NULL NULL NULL NULL NULL NULL NULL SbS RS ObS O
  • 32.
    level_order(x) { if (x== NULL) return; } NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 33.
    level_order(x) { if (x== NULL) return; } NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 34.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 35.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 36.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 37.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 38.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 39.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 40.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 41.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 42.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 43.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL x = A; SbS RS ObS O
  • 44.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B x = A; SbS RS ObS O
  • 45.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B D x = A; SbS RS ObS O
  • 46.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE x = A; SbS RS ObS O
  • 47.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE x = A; SbS RS ObS O
  • 48.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE x = A; SbS RS ObS O
  • 49.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DE C x = A; SbS RS ObS O
  • 50.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEF C x = A; SbS RS ObS O
  • 51.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C x = A; SbS RS ObS O
  • 52.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C x = A; SbS RS ObS O
  • 53.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C x = A; SbS RS ObS O
  • 54.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D x = A; SbS RS ObS O
  • 55.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D x = A; SbS RS ObS O
  • 56.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D x = A; SbS RS ObS O
  • 57.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E x = A; SbS RS ObS O
  • 58.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E x = A; SbS RS ObS O
  • 59.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E x = A; SbS RS ObS O
  • 60.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F x = A; SbS RS ObS O
  • 61.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F x = A; SbS RS ObS O
  • 62.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F G x = A; SbS RS ObS O
  • 63.
    level_order(x) { if (x== NULL) return; } enQueue(queue, x); A while (!isEmpty(queue)) { } x = deQueue(queue); print x->data; if (x->left != NULL) enQueue(queue, x->left); B if (x->right != NULL) enQueue(queue, x->right); C A NULL NULL NULL NULL NULL NULL NULL NULL B DEFG C D E F G x = A; SbS RS ObS O
  • 64.
  • 65.
    N O WO SO Q 7 >W RW U O SQWTWQ SQ R T O OP S O S T SQ R 3 l 9 SQ R Q W T S S TWS R 3 v L S SQ R T SdO S O O S ORR S aRS WRS WTWQO W a PS O R QWO SQa W e a PS S Q 3 L S Se W O TWS R a SR T RW Q W W O W U SQ R 9 O SdO S QWO SQa W e a PS aRS WRS WTWQO W a PS QO PS a SR O Se 3 v KSO Q 3 k KSO Q
  • 66.
    y v Se Se Se SeSe s :KL 3 k :W O e KSO Q L SS ST aP SS aP SS WU
  • 67.
    KSO Q 3 AS 3 S S S3 KSO Q A S S S S h SWU h 3 h :KL3 :W O e KSO Q L SS
  • 68.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0
  • 69.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 70.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 71.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 72.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 73.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
  • 74.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
  • 75.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
  • 76.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
  • 77.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
  • 78.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
  • 79.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0
  • 80.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
  • 81.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
  • 82.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
  • 83.
    y Se is Seis u Se is Se i Se i Se i Se i Se i :KL 3 k :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+ I+ +0 I, ,,
  • 84.
    :KL 3 i aa S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0
  • 85.
    :KL 3 i aa S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 86.
    :KL 3 i aa S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 87.
    :KL 3 i aa S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 88.
    :KL 3 i aa S a Se i is Se i i Se i i :KL KSO Q G S O W *1 0 , *+ +/ ,* +0 I* *+
  • 89.
    :KL 3 :KL KSOQ G S O W 3 L SSF RS 3 SO Q F RS L SSF RS W Se 4 + 3 RS Se i TreeNode* searchNode(TreeNode *root, int key) { if (root == NULL) return NULL; if (root->data == key) return root; else if (root->data > key) return searchNode(root->left, key); else return searchNode(root->right, key); } typedef struct TreeNode { int data; struct TreeNode *left, *right; }TreeNode;
  • 90.
    :KL 3 :KL KSOQ G S O W 3 L SSF RS 3 SO Q F RS L SSF RS W Se 4 + 3 RS Se i TreeNode* searchNode(TreeNode *root, int key) { while (root != NULL) { if (root->data == key) return root; else if (root->data > key) root = root->left; else root = root->right; } return NULL; }
  • 91.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0
  • 92.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2
  • 93.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
  • 94.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
  • 95.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
  • 96.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
  • 97.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2
  • 98.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2
  • 99.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
  • 100.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
  • 101.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
  • 102.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
  • 103.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,
  • 104.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,,
  • 105.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
  • 106.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
  • 107.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
  • 108.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2
  • 109.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2
  • 110.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
  • 111.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
  • 112.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
  • 113.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
  • 114.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
  • 115.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,)
  • 116.
    :KL 3 k :KLA S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 Q4) 30 을 삽입 2 ,, *2 ,) Q5) 29 를 삽입
  • 117.
    :KL 3 :KL AS G S O W Se i y g g [ RS Se L FMDD l L SSF RS L SSF RS RO O o N Se L SSF RS 6 ST L SSF RS 6 WU ,, L L SSF RS n
  • 118.
    :KL 3 :KL AS G S O W 3 b WR 3 W S F RS L SSF RS W Se 4 + 3 RS Se i void insertNode(TreeNode **root, int key){ TreeNode *parentNode = NULL, *currentNode, *newNode; currentNode = *root; while (currentNode != NULL) { if (currentNode->data == key) return; parentNode = currentNode; if (currentNode->data > key) currentNode = currentNode->left; else currentNode = currentNode->right; }
  • 119.
    :KL 3 :KL AS G S O W 3 b WR 3 W S F RS L SSF RS W Se 4 + 3 RS Se i void insertNode(TreeNode **root, int key){ TreeNode *parentNode = NULL, *currentNode, *newNode; currentNode = *root; while (currentNode != NULL) { if (currentNode->data == key) return; parentNode = currentNode; if (currentNode->data > key) currentNode = currentNode->left; else currentNode = currentNode->right; } (( g (( o (( Seg s
  • 120.
    :KL 3 newNode =(TreeNode *)malloc(sizeof(TreeNode)); if (newNode == NULL) return; newNode->data = key; newNode->left = newNode->right = NULL; if (parentNode != NULL) if (parentNode->data > key) parentNode->left = newNode; else parentNode->right = newNode; else *root = newNode; } :KL A S G S O W (( Se i o (( o L SSF RS rh s n n
  • 121.
    :KL 3 :KL AS G S O W ,) -) +) *) +. ,.
  • 122.
    :KL 3 :KL AS G S O W ,) -)+) *) +. ,.
  • 123.
    y ,g o ] NL f ] N L U L 5314 6723 0 ] N L f ] N L f :KL 3 k :KL S S S G S O W *1 0 , *+ +/ ,* +0
  • 124.
    y ,g o ] NL f ] N L U L 5314 6723 0 ] N L f ] N L f :KL 3 k :KL S S S G S O W *1 0 , *+ +/ ,* +0 I* +0 I+ +/ I, 0 Q4) 18 을 삽입
  • 125.
    :KL 3 g )* + g * o :KL S S S G S O W g ) * + 7
  • 126.
    :KL 3 g )o g * o L ] L L ,, l n ] L a :KL S S S G S O W g + o L ] ] L e [ L n ] L a L ] L [ L ] L L ] L [ d L ] L ] L a
  • 127.
    :KL 3 :KL SS S G S O W 3 b WR 3 RS S SF RS L SSF RS W Se 4 + 3 RS Se i void deleteNode(TreeNode **root, int key){ TreeNode *pNode = NULL, *curNode, *newNode; TreeNode *child, *succ; *succParent; curNode = *root; while (curNode != NULL && curNode->data != key) { pNode = curNode; if (curNode->data > key) curNode = curNode->left; else curNode = curNode->right; } if (curNode == NULL) { printf(“key is not int the treen”); return; }
  • 128.
    :KL 3 if (curNode->left== NULL && curNode->left == NULL){ if (pNode != NULL) if (pNode->left == curNode) pNode->left = NULL; else pNode->right = NULL; else *root = NULL; } else if (curNode->left == NULL || curNode->left == NULL){ child = (curNode->left != NULL) ? curNode->left : curNode->right; if (pNode != NULL) { if (pNode->left == curNode) pNode->left = NULL; else pNode->right = NULL; } else *root = NULL; } :KL S S S G S O W
  • 129.
    :KL 3 else { succParent= curNode; succ = curNode->left; while (succ->right != NULL) { succParent = succ; succ = succ->right; } if (succParent->right == succ) succParent->right = succ->left; else succParent->left = succ->left; curNode->data = succ->data; curNode = succ; } free(curNode); } :KL S S S G S O W (( g + o (( aQQHO S (( y (( h *1 0 , *+ +/ ,* */*) *, *1 *0 2 +/ ,* 1 aQQ aQQ
  • 130.
    :KL o (( )( ( 6 8235 01 4 9 ) (( )( ( )
  • 131.
  • 132.
    :KL g +ko (( )( ( ( 6 941 0 8 ) (( )( ( ( 5 32 )
  • 133.
    :KL g +ko (( )( ( ( 3 68 012 ) (( )( ( ( 5 64 9 2 )