c languege 9.1 - struct node {int key; double value; *lchild; *rchild;} - Implement the modified_search() algorithm
Question:
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
Introduction to Java Programming, Comprehensive Version
ISBN: 978-0133761313
10th Edition
Authors: Y. Daniel Liang