c languege

9.1

- struct node {int key; double value; *lchild; *rchild;}

- Implement the modified_search() algorithm

- The modified_search is searched using the key

- a functional circle : treePointer modified_search(treePointer tree, int key)

- The main function generates 12 (key, value) pairs and adds them to the binary search tree

- Output (key, value) pairs while traversing binary search trees using inorder traversal algorithms

9.2

- Implement a search algorithm that receives a key and finds the corresponding value

- After receiving the key from the user in the main, call the search algorithm to check the execution result

9.3

Take n as a factor, n

- key: (rand() / (0x7fff * 1.0) ) * 100,000,000

- value: 1.0 / key

- Create a function A = make_bst(intn) to add pairs to the binary navigation tree

- Function circle: treePointer make_bst(intn)

- Observe the execution time of make_bst while varying the size of n (n: 100 to 1,000,000)

- Outputs the number of nodes, height (depth), and terminal nodes of the tree automatically generated by the make_bst() function

- Function circle:

int count_node(treePointer ptr)

int count_depth(treePointer ptr)

int count_leaf(treePointer ptr)

result

9.1. Create a binary search tree by creating 12 (key, value) pairs

Created

9.2. Search using key values in the generated binary search tree

Enter the key value you want to find. : 2

count : 4, key: 2의 value: 0.500000

Enter the key value you want to find. : 4

key: There are no 4 nodes.

Enter the key value you want to find. : 6

count : 2, key: 6의 value: 0.166667

Enter the key value you want to find. : 8

count : 3, key: 8의 value: 0.125000

Enter the key value you want to find. : 10

count : 1, key: 10의 value: 0.100000

Enter the key value you want to find. : 12

count : 3, key: 12의 value: 0.083333

Enter the key value you want to find. : 14

count : 4, key: 14의 value: 0.071429

Enter the key value you want to find. : 16

key: 16 nodes not found.

Enter the key value you want to find. : 18

count : 3, key: 18의 value: 0.055556

Enter the key value you want to find. : 20

count : 4, key: 20의 value: 0.050000

Enter the key value you want to find. : -1

9.3. Time of binary tree creation with n nodes, number of nodes, height (depth), and terminal node count observation

Create a binary search tree with n nodes (n): 100

Binary search tree B:

( key, value)

( 125125, 0.000008)

( 466933, 0.000002)

......

(98998992, 0.000000)

(99679555, 0.000000)

(99969481, 0.000000)

Binary search tree B generation time: 0.000

Number of nodes in binary search tree B: 100

Height of binary search tree B (depth): 12

Number of terminal nodes in binary search tree B: 36

Create a binary search tree with n nodes (n): 1000

Binary search tree B:

( key, value)

( 85451, 0.000012)

( 161748, 0.000006)

......

(99801629, 0.000000)

(99874874, 0.000000)

(99932859, 0.000000)

Generation time of binary search tree B: 0.001

Number of nodes in binary search tree B: 985

Height of binary search tree B (depth): 23

Number of terminal nodes in binary search tree B: 338

Create a binary search tree with n nodes (n): 10000

Binary search tree B:

( key, value)

( 9155, 0.000109)

( 12207, 0.000082)

......

(99975585, 0.000000)

(99990844, 0.000000)

(99993896, 0.000000)

Binary search tree B generation time: 0.002

Number of nodes in binary search tree B: 8630

Height of binary search tree B (depth): 30

Number of terminal nodes in binary search tree B: 2897

Create a binary search tree with n nodes (n): 100000

Binary search tree B:

( key, value)

( 3051, 0.000328)

( 6103, 0.000164)

......

(99993896, 0.000000)

(99996948, 0.000000)

(100000000, 0.000000)

Binary search tree B generation time: 0.019

Number of nodes in binary search tree B: 31164

Height of binary search tree B (depth): 35

Number of terminal nodes in binary search tree B: 10456

Create a binary search tree with n nodes (n): 1000000

Binary search tree B:

( key, value)

( 3051, 0.000328)

( 9155, 0.000109)

(99993896, 0.000000)

(99996948, 0.000000)

(100000000, 0.000000)

Binary search tree B generation time: 0.019

Number of nodes in binary search tree B: 31164

Height of binary search tree B (depth): 35

Number of terminal nodes in binary search tree B: 10456

Create a binary search tree with n nodes (n): -1