ce-10二分探索木PPT课件

1、ce-10. 二分探索木 （C応用，全回）1金子邦彦https:/www.kkaneko.jp/cc/c/index.html例題併合 併合動2 NULL NULLhead1tail1 tail1 ，併合便利head2tail2 NULLhead1tail1 3#include stdio.h#include struct data_list int data; struct data_list *next;void print_list(struct data_list *p) struct data_list *x; if ( p = NULL ) return; printf( %d,

2、p-data ); x = p-next; while( x != NULL ) printf( , %d, x-data ); x = x- next; printf( n ); struct data_list *new_list(int x) struct data_list *c = new(struct data_list); c-data = x; c-next = NULL; return c;void insert_list(struct data_list *p, int x) struct data_list *c = new(struct data_list); c-da

3、ta = p-data; c-next = p-next; p-data = x; p-next = c;int _tmain() int ch; struct data_list *head1; struct data_list *tail1; struct data_list *head2; struct data_list *tail2; head1 = new_list( 6789 ); insert_list( head1, 45 ); tail1 = head1-next; / 個目要素作時点 head1-next tail1 等 insert_list( head1, 123 )

4、; head2 = new_list( 789 ); insert_list( head2, 56 ); tail2 = head2-next; / 個目要素作時点 head2-next tail2 等 insert_list( head2, 1234 ); printf( 併合前n ); print_list( head1 ); print_list( head2 ); / tail1-next = head2; tail1 = tail2; printf( 併合後n ); print_list( head1 ); printf( Enter 1,2回押. 終了n); ch = getcha

5、r(); ch = getchar(); return 0; tail1-next = head2;tail1 = tail2; 4実行結果例二分探索木 (binary search tree) 整列可能任意個数集合対、効率良探索（二分探索）行構造 整列前：35 46 21 13 61 40 69 整列後（昇順）：13 21 35 40 46 61 69 節点出枝高本木構造（二分木）作、各節点置5二分探索木構造 節点(node)枝(branch) 枝間（親子）関係表 節点入（親）枝本 節点出（子）枝本6親子節点(node)枝(branch)子子親二分探索木構造（） 根(root)： 親持節点

6、葉(leaf)： 子持節点 部分木(subtree)： 任意節点下枝節点7部分木(subtree)根(root)葉(leaf)二分探索木再帰的構造 左部分木、右部分木二分木 親節点対処理、子節点対処理帰着多（例）探索，子移動，親処理同様処理繰返再帰関数用自然表現。8右部分木左部分木右部分木左部分木二分探索木各C言語構造体表現9/ 分木struct BTNodeBTNode *left;BTNode *right; int value;leftrightvalueleftrightvalueleftrightvalue個構造体int value 部分，格納応変二分探索木節点(node) 生成関数

7、 new_node10#include stdio.h#include struct BTNode BTNode *left; BTNode *right; int value;struct BTNode *new_node(int x, struct BTNode *y, struct BTNode*z) struct BTNode *w = new BTNode(); w-value = x; w-left = y; w-right = z; return w;int _tmain() int ch; BTNode *root; root = new_node( 100, NULL, NU

8、LL ); printf( Enter 1,2回押. 終了n); ch = getchar(); ch = getchar(); return 0; value, left, right 値例題，使用例題二分探索木生成 配置 左側子親小 右側子親大1135211340614669new_node 回呼出，節点7個作12#include stdio.h#include struct BTNode BTNode *left; BTNode *right; int value;void print_data( struct BTNode *root ) if ( root-left != NULL

9、) print_data( root-left ); printf( %dn, root-value ); if ( root-right != NULL ) print_data( root-right ); struct BTNode *new_node(int x, struct BTNode *y, struct BTNode *z) struct BTNode *w = new BTNode(); w-value = x; w-left = y; w-right = z; return w;int _tmain() int ch; BTNode *root; root = new_n

10、ode( 35, new_node( 21, new_node(13, NULL, NULL), NULL), new_node( 46, new_node(40, NULL, NULL), new_node(61, NULL, new_node(69, NULL, NULL); print_data( root ); printf( Enter 1,2回押. 終了n); ch = getchar(); ch = getchar(); return 0; 分木生成in-order 要素表示（in-order 後述）13実行結果例 in-order 表示14void print_data( st

11、ruct BTNode *root ) if ( root-left != NULL ) print_data( root-left ); printf( %dn, root-value ); if ( root-right != NULL ) print_data( root-right ); 35211340614669最初左部分木次自分（節点）最後右部分木例題二分探索木探索 指定要素存在探有無1535211340614669二分探索木探索 根(root)始。 探索値，各節点比較目標探 探索節点小，右側子進 探索節点大，左側子進16探索例（例） 節点40探場合 根値(35)，探索(40)比

12、較 探索方大，右側子節点移 次移節点値(46)探索(40)比較 探索方小，左子節点移 次移節点(40)，目標節点173521134061466918#include stdio.h#include struct BTNode BTNode *left; BTNode *right; int value;struct BTNode *find_node(int x, struct BTNode *root) BTNode *node; node = root; while( ( node != NULL ) & ( x != node-value ) ) if ( x value ) n

13、ode = node-left; else node = node-right; return node;struct BTNode *new_node(int x, struct BTNode *y, struct BTNode *z) struct BTNode *w = new BTNode(); w-value = x; w-left = y; w-right = z; return w;int _tmain() int ch; BTNode *root; BTNode *y; root = new_node( 35, new_node( 21, new_node(13, NULL,

14、NULL), NULL), new_node( 46, new_node(40, NULL, NULL), new_node(61, NULL, new_node(69, NULL, NULL); y = find_node( 40, root ); if ( y = NULL ) printf( 40 無n ); else printf( 40 有n ); printf( Enter 1,2回押. 終了n); ch = getchar(); ch = getchar(); return 0; 分木生成探索（見 NULL返）探索行関数19struct BTNode *find_node(int

15、 x, struct BTNode *root) BTNode *node; node = root; while( ( node != NULL ) & ( x != node-value ) ) if ( x value ) node = node-left; else node = node-right; return node;20実行結果例例題二分探索木挿入 要素挿入行関数作35 46 21 13 61 40 69 挿入，例題同二分探索木2135211340614669二分探索木挿入 二分探索木新挿入 挿入位置探 （find_node同要領） 新節点生成 挿入位置見節点、新節

16、点書換2223#include stdio.h#include struct BTNode BTNode *left; BTNode *right; int value;void print_data( struct BTNode *root ) if ( root-left != NULL ) print_data( root-left ); printf( %dn, root-value ); if ( root-right != NULL ) print_data( root-right ); struct BTNode *new_node(int x, struct BTNode *y

17、, struct BTNode *z) struct BTNode *w = new BTNode(); w-value = x; w-left = y; w-right = z; return w;struct BTNode *insert_node(struct BTNode *node, int x) if ( node = NULL ) return new_node(x, NULL, NULL); else if ( x value ) node-left = insert_node(node-left, x); return node; else if ( x node-value

18、 ) node-right = insert_node(node-right, x); return node; else return node; int _tmain() int ch; BTNode *root; root = new_node( 35, NULL, NULL ); insert_node( root, 46 ); insert_node( root, 21 ); insert_node( root, 13 ); insert_node( root, 61 ); insert_node( root, 40 ); insert_node( root, 69 ); print_data( root ); printf( Enter 1,2回押. 終了n); ch = getchar(); ch = getchar(); return 0; 最初