LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP : 1

Size: px

Start display at page:

Download "LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP : 1"

ちかこみしま
5 years ago
Views:

1 LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP : 1

2 2 データの追加データの取り出し : 1.2 [1] pp (binary tree) (three: ) ( ) 秋田高専校長準学士課程学生専攻科課程学生教員職員機械電気情報物質環境都市生産システム環境システム人文社会自然科学機械電気情報物質環境都市総務学生 :! 2

3 ? 親ブランチ B D ノード G H I リーフリーフリーフブランチノードブランチルート A レベル0 ブランチ C ノードレベル1 子 E ノード F レベル2 リーフ J レベルリーフ 1: (root: ) (node: ) (leaf: ) (branch: ) (parent) (child) (brother) : B E (preorder) 5 a b d g e h i c f j (postorder) g d b h e i a c f j

4 (inorder) 5 g d h i e b j f c a 2 a b c d e f g h i j 5: (binary tree) (postorder)

5 : (2 ).2 2,10,2,,12, :

6 : : 2 ( 10) ( 11) ( ) ( 12)

7 : 9 11: : C! typedef struct node_tag{ int ; struct node_tag *left; struct node_tag *right; }node; 1 node *root_tree=null; tree node (NULL) 7

8 root_tree NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL 1: 5 [ 1] 2? ( ) ( ) ( ) ( ) [ 2] [ ] 2 9,2,,5,9,5,11,12,1,2, 2 70,7,7,75,77, 2

9 [ ] 2 52,, [ 5] 2 [ 1] ( ) [1] pp [ 2] ( ) 2 2 [ ] ( ) [ ]

10 : 2 [ 5] : 2 [ ] ( ) 7 2 ( )AM :5 10

11 A 1: (b tree.h) 1 //============= ============================== 2 typedef struct node tag { int ; struct node tag l e f t ; 5 struct node tag r i g h t ; } node ; 7 //============== ================================= 9 extern node c r e a t n o d e ( int new data ) ; 10 extern void i n s e r t n o d e ( node t node, int new data ) ; 11 extern void d e l e t e n o d e ( node del node, int d e l d a t a ) ; 12 extern void p r i n t t r e e ( node t node, int depth ) ; extern node r o o t t r e e ; 2: (b tree.c) 1 #include <s t d i o. h> 2 #include <s t d l i b. h> #include b t r e e. h 5 node r o o t t r e e=null; 7 //============== ================================================== node c r e a t n o d e ( int new data ) 9 { 10 node new node ; new node=(node ) malloc ( s i z e o f ( node ) ) ; 1 1 new node > = new data ; 15 new node >l e f t = NULL; 1 new node >r i g h t = NULL; 17 1 return new node ; 19 } //============== ======================================= 2 void i n s e r t n o d e ( node t node, int new data ) 2 { 25 2 i f ( t node==null){ // r o o t ( ) 27 r o o t t r e e = c r e a t n o d e ( new data ) ; 2 return ; 29 } 0 1 i f ( t node > > new data ){ 2 i f ( t node >l e f t == NULL){ t node >l e f t=c r e a t n o d e ( new data ) ; } else { 5 i n s e r t n o d e ( t node >l e f t, new data ) ; } 11

12 7 } else { i f ( t node >r i g h t == NULL){ 9 t node >r i g h t=c r e a t n o d e ( new data ) ; 0 } else { 1 i n s e r t n o d e ( t node >r i g h t, new data ) ; 2 } } 5 return ; } 7 //============== ====================================== 9 void d e l e t e n o d e ( node del node, int d e l d a t a ) 50 { 51 node parent=null; // 52 node big=null; // 5 node pbig=null; // 5 int f l a g =0; 55 5 // 57 while ( d e l n o d e!=null && del node >!= d e l d a t a ){ 5 i f ( del node > < d e l d a t a ){ 59 parent = d e l n o d e ; 0 d e l n o d e = d e l n o d e > r i g h t ; 1 } else { 2 parent = d e l n o d e ; d e l n o d e = d e l n o d e > l e f t ; } 5 } 7 i f ( d e l n o d e==null){ p r i n t f (! \ n ) ; 9 return ; 70 } i f ( del node >l e f t == NULL){ // 7 i f ( parent==null){ // r o o t 7 r o o t t r e e = del node >r i g h t ; 75 } else i f ( parent > > d e l d a t a ){ // 7 parent >l e f t=del node >r i g h t ; 77 } else { // 7 parent >r i g h t=del node >r i g h t ; 79 } 0 f r e e ( d e l n o d e ) ; 1 return ; 2 } i f ( del node >r i g h t == NULL){ // 5 i f ( parent==null){ // r o o t r o o t t r e e = del node >r i g h t ; 7 } else i f ( parent > > d e l d a t a ){ parent >l e f t=del node >l e f t ; 9 } else { // 90 parent >r i g h t=del node >l e f t ; 91 } 92 f r e e ( d e l n o d e ) ; 9 return ; 9 } 95 9 // 97 9 pbig=d e l n o d e ; 12

13 99 big=del node >l e f t ; while ( big >r i g h t!= NULL){ // 102 pbig = big ; 10 big = big >r i g h t ; 10 f l a g = 1 ; 105 } del node > = big > ; i f ( f l a g == 0){ 110 pbig >l e f t = big >l e f t ; 111 } else { 112 pbig >r i g h t = big >l e f t ; 11 } f r e e ( big ) ; } //============== ===================================== 122 void p r i n t t r e e ( node t node, int depth ) 12 { 12 int i ; i f ( t node==null) return ; p r i n t t r e e ( t node >r i g h t, depth +1); for ( i =0; i <depth ; i ++) p r i n t f ( ) ; 11 p r i n t f ( %d\n, t node > ) ; 12 1 p r i n t t r e e ( t node >l e f t, depth +1); 1 15 return ; 1 } 1 #include <s t d i o. h> 2 #include b t r e e. h int main ( void ) 5 { 7 i n s e r t n o d e ( r o o t t r e e, 5 ) ; i n s e r t n o d e ( r o o t t r e e, 9 ) ; 9 i n s e r t n o d e ( r o o t t r e e, ) ; 10 i n s e r t n o d e ( r o o t t r e e, ) ; 11 i n s e r t n o d e ( r o o t t r e e, 7 ) ; 12 i n s e r t n o d e ( r o o t t r e e, ) ; 1 i n s e r t n o d e ( r o o t t r e e, 1 0 ) ; 1 i n s e r t n o d e ( r o o t t r e e, 1 2 ) ; 15 i n s e r t n o d e ( r o o t t r e e, 2 ) ; 1 i n s e r t n o d e ( r o o t t r e e, 1 ) ; 17 1 p r i n t f ( \n\n ) ; 19 p r i n t t r e e ( r o o t t r e e, 0 ) ; 20 : (main.c) 1

14 21 d e l e t e n o d e ( r o o t t r e e, 9 ) ; 22 p r i n t f ( \n\n ) ; 2 p r i n t t r e e ( r o o t t r e e, 0 ) ; 2 return 0 ; 25 } [1], ( ). C 2. ( ),

( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1

( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1 () 2006 2 27 1 10 23 () 30 () 27 [1] p.97252 7 2 2.1 2.1.1 1 LIFO(last in first out, ) (push) (pup) 1 1: 2.1.2 1 List 4-1(p.100) stack[] stack top 1 2 (push) (pop) 1 2 void stack push(double val) val stack