C Programming Binary sort tree lookup

<> the first number as the root node, divide the next number into those larger than 30 and smaller than 30, the small number is placed on the left, the large number is placed on the right, and then in the order in which the numbers appear, one by one, the larger than the root node is placed on the right, and the small one is placed on the left.

30 below left, 15 right, 43

15 below left, 8 right, 25

43 below right 49

8 below right 13

25 below left, 20 right, 28

49 below left, 46 right, 55

13 below the left 10

Select D, first find 46 nodes: 46>35, so go to the left subtree of 46 nodes and continue to search: 36>35, continue to 36 nodes left subtree search:

18<35, to the right subtree of node 18: 28<35, to node 28 of the right subtree search: 35=35, end.

The rest of the answers are incorrect. For example, in B, after finding 36 nodes, you should go to the left subtree of 36 to find them, so all subsequent nodes should be smaller than 36, but 46 is not possible after 36 nodes.

The lookup comparison path for option a is like this28

46 35 This option, if it is said to be an ascending sort tree, 18 is on the right subtree, and if it is said to be a descending sort tree, it is clearly not.

The lookup comparison path for option b is like this18

46 35 Here we are looking at a sub-tree with 36 as its root, and the reason for discarding it is the same as above. 36 has both 28 and 28 on the right left subtree.

The lookup comparison path for option c is 48 like this

36 35 is a subtree with 28 as its root, and it has both 18 and 18 on its left subtree. So discarded.

The lookup comparison path for option D is as follows46

28 35 fits perfectly, so the correct option is d.

This should be the choice B. As far as the binary sorting tree is concerned, it has three characteristics: (1) if the left subtree is not empty, the value of all nodes on the left subtree is less than the value of its root node; (2) If the right subtree is not empty, the value of all nodes on the right subtree is greater than the value of its root node; (3) The left and right subtrees are also binary sorting trees, respectively. ACD can be excluded based on this feature. For example, if the number of a is 28 for the first time, but the keyword is 35, then the right subtree of 28 should be traversed (it is easy to know that 28 is the root node), then the number to be traversed next, or the number to be compared should be larger than 28 (according to the second feature of the binary sorting tree), but 18 appears after the A option, so A is wrong.

The same is true for the cd option, which is also wrong. Only option b is correct.

Binary sort tree.

The construction process: according to the given sequence, the nodes are inserted into the binary sorting tree, and a new node is inserted into the binary sorting tree, and the inserted binary tree must be ensured.

It still meets the definition of a binary sort tree.

Insertion process: If the binary sorting tree is empty, the node *s to be inserted is inserted into the empty tree as the root node.

>>If s->key = t->key, it does not need to be inserted, if s->key < t->key, it is inserted into the left subtree of the root, and if s->key > t->key, it is inserted into the right subtree of the root. The insertion process in the subtree is the same as in the tree, and so on until the node *s is inserted into the binary sorted tree as a new leaf, or until the tree already has nodes with the same keyword.

Description: Each insertion of a new node is a new leaf node on the binary sort tree.

From the sequence of keywords in different orders, different binary sorting trees will be obtained.

Constructing a binary sorting tree for an arbitrary keyword sequence essentially sorts keywords.

The process of finding is similar, starting with the root node and comparing it on the left subtree if it is smaller than the root node, and on the right subtree if it is larger than the root node, and so on until the search is successful or unsuccessful (compare to the leaf node).

5.Deletion of binary sort trees:

Assuming that the deleted node is *p and its parents are *f, it is not lost in general, and *p is the left child of *f, which is discussed in three situations below:

If the node *p is a leaf node, you only need to modify the pointer of its parent node *f.

If node *p has only the left subtree pl or only the right subtree pr, then it is sufficient to make pl or pr the left subtree of its parental node.

If the left and right subtrees of node *p are not empty, first find the median forward node *s of *p (note that *s is the bottom right node in the left subtree of *p, and its right chain domain is empty), and then there are two ways:

Let the left subtree of *p be directly linked to the left chain of *p's parental node *f, and the right subtree of *p should be chained to the right chain of *p's mid-order forward node *s.

Replace *p with the median forward node *s of *p (i.e., copy the data of *s to *p), and chain the left subtree of *s to the left (or right) chain of *s's parental node *q.

6.Delete Algorithm Demo:

7.Binary sort tree lookup:

The process of finding in a binary sort tree is similar to a binary search, and it is also a process of gradually narrowing down the search. If the search is successful, it is a path from the root node to the node to be checked. If the search fails, the path from a root node to a leaf node is taken. Therefore, the number of times the lookup process and the keyword are compared does not exceed the depth of the tree.

Since binary sorted trees with n nodes are not unique, the shape and depth may be different. Therefore, the average search length of a binary sorted tree with n nodes is related to the morphology of the tree.

In the best-case scenario, the binary sort tree and the binary decision tree are in the same shape.

Worst-case scenario: The binary sorted tree is a single-branched tree, where the average lookup length is the same as the sequential lookup.

Worst-case example.

In terms of average performance, the lookup on the binary sort tree is not much different from the binary search, and the insertion and deletion of nodes on the binary sort tree is very convenient, without the need to move a large number of nodes.