6. binary tree

1. ?Sa @ea U CW ME;D 8 U =aW M WbS W e Introduction to Tree/Binary Tree

2. L SS h *3 tp 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 S O 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 RSU SS SbS * y p SWU k 루트 루트 루트 트리1 트리2 트리3 레벨 1 레벨 2 레벨 3 레벨 4 차수: 3 차수: 2 차수: 3 차수: 1 차수: 2 트리의 높이: 4 t 포리스트

6. :W O e L 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 O e 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 :W O e L SS k g g g k g * g

11. 3 X y b + c a / * + (x+y)*((a+b)/c)

12. 3 n

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 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

18. 3 k 현재 노드 ! ObS O

19. W RS ObS O * LD 3 D + 3 , LJ 3 J LD LJ + * 3.

20. W RS ObS O 6 6

21. W RS ObS O d inOrder (x) { if (x != NULL) { inOrder (x->left); print x; inOrder (x->right); } }

22. W RS ObS O d inOrder (x) { if (x != NULL) { inOrder (x->left); print x; inOrder (x->right); } } @ A : B = C 9 D > ; ?

23. S RS ObS O * 3 + LD 3 D , LJ 3 J 2. 1. 3.

24. S RS ObS O d preOrder (x) { if (x != NULL) { print x; preOrder (x->left); preOrder (x->right); } }

25. S RS ObS O 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. SbS RS ObS O …

30. SbS RS ObS O … 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

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

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

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

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

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. Binary Search Tree

65. 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

66. y v Se Se Se Se Se s :KL 3 k :W O e KSO Q L SS ST aP SS aP SS WU

67. 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

68. 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

69. 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* *+

73. 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

80. 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, ,,

84. :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

85. :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* *+

89. :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;

90. :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; }

91. :KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0

92. :KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2

93. :KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 2

98. :KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2

99. :KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, 2 ,,

104. :KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,,

105. :KL 3 k :KL A S G S O W y g Se i *1 0 , *+ +/ ,* +0 I* 2 I+ ,, I, *2 2 ,, *2

109. :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

110. :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 ,)

116. :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 를 삽입

117. :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

118. :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; }

119. :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

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 A S G S O W ,) -) +) *) +. ,.

122. :KL 3 :KL A S G S O W ,) -)+) *) +. ,.

123. 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

124. 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 을 삽입

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 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; }

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 82 35 01 4 9 ) (( )( ( )

131. :KL g k o

132. :KL g +k o (( )( ( ( 6 941 0 8 ) (( )( ( ( 5 32 )

133. :KL g +k o (( )( ( ( 3 68 012 ) (( )( ( ( 5 64 9 2 )

6. binary tree

Recommended

More Related Content

What's hot (15)

Viewers also liked (20)

Similar to 6. binary tree (20)

More from Geunhyung Kim (6)

Recently uploaded (20)

6. binary tree