Data structure binary tree definition, properties, storage structure

This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

Data structure binary tree definition, properties, storage structure

6.5 Definition of binary trees

Now let’s play a game. I have written a positive integer number less than 100 on a piece of paper. Please try to guess which one I have written. Note that you must not guess more than seven numbers. My answer will only tell you that it is “bigger” or “smaller”.

This game is often used on TV shows to guess the price of something. I have seen some people add up the numbers bit by bit, such as 5, 10, 15, 20, such a guess strategy is too low, obviously not learned data structure and algorithm talent to do.

This is actually a classic split search algorithm. If we use figure 6-5-1 (the next three layers of omission) method, we must be able to guess the result within 7 times.

Figure 6-5-1

Since this is a positive integer within 100, we first guessed 50 (half of 100) and were told “big”, so we guessed 25 (half of 50) and were told “small”, so we guessed 37 (the middle number between 25 and 50) and were told “small”, so we guessed 43 (big, 40, big, 38, small, 39), exactly right. Table 6-5-1 shows the process.

Table 6-5-1

And what we found is that if you do it this way, it’s not a little bit more efficient. For a detailed explanation of half-searching, we will talk about it later in the chapter. But for situations where there are two outcomes at a certain stage, like on and off, 0 and 1, true and false, up and down, right and wrong, heads and tails, all of these are suitable for modeling with a tree, and this tree is a very special kind of tree called a binary tree.

A Binary Tree is a finite set of n (n≥0) nodes, which is either an empty set (called an empty Binary Tree), or consists of a root node and two disjoint Binary trees of left and right subtrees called roots, respectively.

Figure 6-5-2 is a binary tree. The tree in Figure 6-2-1, because D has three subtrees, is not a binary tree.

Figure 6-5-2

6.5.1 Features of binary trees

The characteristics of binary trees are:

■ Each node has at most two subtrees, so there is no node greater than 2 in a binary tree. Notice that it’s not just two subtrees, it’s at most. It’s ok to have no subtree or to have one subtree.

■ The left subtree and the right subtree are ordered, and the order cannot be reversed arbitrarily. Like people are hands, feet, but obviously left hand, left foot and right hand, right foot is not the same, the right hand wearing left glove, right foot wearing left shoe will be extremely uncomfortable and uncomfortable.

■ Even if a node has only one subtree in the tree, it must be distinguished as a left subtree or a right subtree. In Figure 6-5-3, tree 1 and tree 2 are the same tree, but they are different binary trees. It’s like if you accidentally fall and hurt your hand, whether it’s your left hand or your right hand, the impact on your life is completely different.

Figure 6-5-3

There are five basic forms of binary trees:

1. Empty binary tree.

2. There’s only one root.

3. The root has only the left subtree.

4. The root has only the right subtree.

5. The root has both left and right subtrees.

I should say these five forms are pretty easy to understand, so let me ask you, if I have a tree with three nodes, how many forms do I have? If I have a binary tree with three nodes, let’s think about it, how many forms can I have?

In terms of morphology, there are only two cases of tree with three nodes, that is, tree 1 with two layers and any of the last four with three layers in FIG. 6-5-4. However, for binary tree, due to the need to distinguish between left and right, it has evolved into five forms. Tree 2, tree 3, tree 4 and tree 5 respectively represent different binary trees.

Figure 6-5-4

6.5.2 Special binary trees

Let’s introduce some special binary trees. These trees may not make sense to you for a while, but learn about them and you’ll get to their practical uses later.

1. Inclined tree

As the name implies, the inclined tree must be inclined, but to which oblique or pay attention to. A binary tree in which all nodes have only left subtrees is called a left-slant tree. A binary tree in which all nodes have only a right subtree is called a right slant tree. These two are collectively called oblique trees. Tree 2 in Figure 6-5-4 is the left-leaning tree and tree 5 is the right-leaning tree. The obvious characteristic of the oblique tree is that each layer has only one node, and the number of nodes is the same as the depth of the binary tree.

You might think, well, this is a tree, just like our linear table structure. Right. In fact, the linear table structure can be thought of as a very special representation of a tree.

2. Full binary tree

Su Dongpo once had a word: “people have joys and sorrows, the moon has waxing and waning, this matter is difficult to complete in ancient times.” It means that perfection is ideal, and imperfection is life. Our usual examples are also high left and low right, jagged binary trees. Is there a perfect binary tree?

Well, some of you are already pointing in the air. Yes, there are perfect binary trees.

In a binary tree, if all branches have left and right subtrees, and all leaves are on the same level, such a tree is called a full binary tree.

Figure 6-5-5 is a full binary tree, which looks perfect.

Figure 6-5-5

Just because every node has left and right subtrees, it can’t be called a full binary tree, and all the leaves must be on the same level, so that the whole tree is balanced. Therefore, the characteristics of full binary trees are:

(1) Leaves can only appear at the bottom layer. It is impossible to achieve balance in other layers.

(2) The degree of non-leaves must be 2. Otherwise, you’re missing an arm and a leg.

(3) In the binary tree with the same depth, the number of nodes and leaves in the full binary tree are the most.

3. Perfect binary tree

A binary tree with N nodes is numbered in sequence. If the node numbered I (1≤ I ≤ N) is in exactly the same position as the node numbered I in a full binary tree of the same depth, then the binary tree is called a complete binary tree, as shown in Figure 6-5-6.

Figure 6-5-6

This is a special binary tree that’s a little hard to understand.

First of all, literally, the difference between perfect and full, a full binary tree must be a perfect binary tree, but a perfect binary tree doesn’t have to be full.

Secondly, all nodes of a complete binary tree correspond to a full binary tree of the same depth, which numbers the same nodes in sequence. The key word here is sequence numbering, like tree 1 in Figure 6-5-7, because node 5 has no left subtree, but a right subtree, which leaves the 10th sequence number empty. In the same way, tree 2 in Figure 6-5-7 has no subtree at node 3, so the number 6 and 7 are empty. Tree 3 in Figure 6-5-7 again leaves the 10th and 11th positions empty because there is no subtree under number 5. Only the tree in Figure 6-5-6, although it is not a full binary tree, is numbered continuously, so it is a complete binary tree.

Figure 6-5-7

From here I can also derive some characteristics of a complete binary tree:

(1) Leaf nodes can only appear at the bottom two levels.

(2) The lowest leaves must be concentrated in a continuous position on the left.

(3) The reciprocal layer, if there are leaf nodes, they must all be in the continuous position on the right.

(4) If the node degree is 1, then the node has only the left child, that is, there is no case of only the right subtree.

(5) The depth of the complete binary tree with the same node number is the smallest.

From the above example, it also gives us a way to judge whether a binary tree is a complete binary tree, that is, looking at the diagram of the tree, silently number each node according to the structure of the full binary tree layer by layer, if there is a gap in the number, it is not a complete binary tree, otherwise. —

6.5 Definition of binary trees

This is actually a classic split search algorithm. If we use figure 6-5-1 (the next three layers of omission) method, we must be able to guess the result within 7 times.

Figure 6-5-1

Table 6-5-1

Figure 6-5-2 is a binary tree. The tree in Figure 6-2-1, because D has three subtrees, is not a binary tree.

Figure 6-5-2

6.5.1 Features of binary trees

The characteristics of binary trees are:

Figure 6-5-3

There are five basic forms of binary trees:

1. Empty binary tree.

2. There’s only one root.

3. The root has only the left subtree.

4. The root has only the right subtree.

5. The root has both left and right subtrees.

Figure 6-5-4

6.5.2 Special binary trees

Let’s introduce some special binary trees. These trees may not make sense to you for a while, but learn about them and you’ll get to their practical uses later.

1. Inclined tree

You might think, well, this is a tree, just like our linear table structure. Right. In fact, the linear table structure can be thought of as a very special representation of a tree.

2. Full binary tree

Well, some of you are already pointing in the air. Yes, there are perfect binary trees.

In a binary tree, if all branches have left and right subtrees, and all leaves are on the same level, such a tree is called a full binary tree.

Figure 6-5-5 is a full binary tree, which looks perfect.

Figure 6-5-5

(1) Leaves can only appear at the bottom layer. It is impossible to achieve balance in other layers.

(2) The degree of non-leaves must be 2. Otherwise, you’re missing an arm and a leg.

(3) In the binary tree with the same depth, the number of nodes and leaves in the full binary tree are the most.

3. Perfect binary tree

Figure 6-5-6

This is a special binary tree that’s a little hard to understand.

First of all, literally, the difference between perfect and full, a full binary tree must be a perfect binary tree, but a perfect binary tree doesn’t have to be full.

Figure 6-5-7

From here I can also derive some characteristics of a complete binary tree:

(1) Leaf nodes can only appear at the bottom two levels.

(2) The lowest leaves must be concentrated in a continuous position on the left.

(3) The reciprocal layer, if there are leaf nodes, they must all be in the continuous position on the right.

(4) If the node degree is 1, then the node has only the left child, that is, there is no case of only the right subtree.

(5) The depth of the complete binary tree with the same node number is the smallest.

6.6 Properties of binary trees

Binary trees have some features to understand and keep in mind so that we can use them better.

6.6.1 Binary tree property 1

Property 1: There are at most 2i-1 nodes (I ≥1) on the ith level of a binary tree.

That’s a good property to remember, but look at the figure 6-5-5.

The first level is the root, there’s only one, so 21 minus 1=20=1.

The second layer has two. 22 minus 1 is 21 is 2.

There are four in the third layer. 23 minus 1 is 22 is 4.

There are eight on the fourth floor. 24 minus 1 is 23 is 8.

Through the argument of data induction, it can be easily concluded that there are at most 2i-1 nodes (I ≥1) on the ith level of the binary tree.

6.6.2 Binary tree properties 2

Property 2: A binary tree of depth k has at most 2 k-1 nodes (k≥1).

And notice that this is 2k minus 1, not 2k minus 1. A lot of you didn’t quite understand it before, and when you try to memorize it, you tend to confuse property 2 with property 1.

Depth k means a binary tree with k layers, so let’s do the easy one first.

If you have one level, at most 1=20-1 nodes.

If you have two layers, at most 1+2=3=22-1 nodes.

If you have three levels, at most 1+2+4=7=23-1 nodes.

If you have four levels, at most 1+2+4+8=15=24-1 nodes.

Through the argument of data induction, it can be concluded that if there are k layers, this binary tree has at most 2K-1 nodes.

6.6.3 Binary tree properties 3

Property 3: for any binary tree T, if the number of terminal nodes is n 0 and the number of nodes with degree 2 is n 2, then n 0 =n 2 +1.

The number of terminal nodes is actually the number of leaf nodes, and a binary tree, in addition to the leaves, all that’s left are the number of nodes of degree one or two, so let’s say n1 is the number of nodes of degree one. Then the total number of nodes in the tree T is n=n0+n1+n2.

For example, in Figure 6-6-1, the total number of nodes is 10, which is composed of A, B, C, and D with equal degree of 2, F, G, H, I, and J with equal degree of 0 and E with degree of 1. The sum is 4+1+5=10.

Figure 6-6-1

Let’s look at it another way and count the number of connections, because the root only branches out, not in, so the total number of branches is the total number of nodes minus one. Figure 6-6-1 shows the nine branches. For nodes A, B, C, and D, they all have two branches going out, and for nodes E there is only one branch going out. So the total number of feeder lines is 4×2+1×1=9.

Algebraic notation is the number of branches equals n minus 1 equals n1 plus 2n2. Since we just had the equation n=n0+n1+n2, it follows that n0+n1+n2-1= n1+2n2. The conclusion is that n0 is equal to n2 plus 1.

6.6.4 Binary tree properties 4

Property 4: The depth of a complete binary tree with n nodes is ⌊log 2 n⌋+1 (⌊x⌋ indicates the maximum integer not greater than x).

From the definition of a full binary tree, we know that the number of nodes n of a full binary tree of depth k must be 2k minus 1. Because that’s the maximum number of nodes. So for n=2k minus 1, if you go backwards, you get a full binary tree with degree k=log2(n+1), or a full binary tree with 15 nodes, degree 4.

A complete binary tree, as we’ve mentioned before, is a binary tree with n nodes, and it’s a complete binary tree if the nodes are numbered in the same order as the nodes in a full binary tree of the same depth. In other words, its leaves will only appear at the bottom two levels.

Its number of nodes must be less than or equal to 2k-1 of the full binary tree of the same degree, but must be more than 2K – 1-1. That is, 2k-1-1 < n≤ 2K -1. Since the number of nodes n is an integer, n≤2k-1 means n<2k, n > 2K-1-1 means n≥2k-1, so 2k-1≤n < 2K, take the logarithm of both sides of the inequality, we get k-1≤log2n < k, and k is also an integer as degrees, so k=⌊log2n⌋+1.

6.6.5 Binary tree properties 5

Property 5: If nodes in a complete binary tree with n nodes (whose depth is ⌊log 2 n⌋+1) are numbered in sequence (from layer 1 to layer ⌊log 2 n⌋+1, each layer from left to right), for any node I (1≤ I ≤n), there are:

1. If I =1, the node I is the root of the binary tree and has no parents; If I >1, the parent is the node ⌊ I /2⌋.

2. If 2i>n, node I has no left child (node I is a leaf); Otherwise its left child is node 2i.

3. If 2i+1>n, node I has no right child; Otherwise its right child is the node 2i+1.

Let’s take figure 6-6-2 to understand this property. This is a complete binary tree, degree 4, and the total number of nodes is 10.

Figure 6-6-2

It’s obvious for the first one, I equals one is the root. When I >1, for example, the parent of node 7 is ⌊7/2⌋=3, and the parent of node 9 is ⌊9/2⌋=4.

The second one, for example, is node 6, because 2 times 6 is 12, which is more than the total number of nodes, so node 6 has no left child, it’s a leaf. Similarly, node 5, because 2 times 5 is 10 is the total number of nodes, so its left child is node 10.

The third one, like node 5, has no right child because 2×5+1=11, which is greater than the total number of nodes 10. And node 3, because 2 times 3 plus 1 is 7 is less than 10, so its right child is node 7.

6.7 Binary tree Storage Structure

6.7.1 Binary tree sequential storage structure

We’ve already talked about the tree storage structure, and that the one-to-many structure of the tree is difficult to implement with sequential storage. But binary tree is a special kind of tree, because of its particularity, makes use of sequential storage structure can also be implemented.

The sequential storage structure of binary tree is to store nodes in binary tree with one-dimensional array, and the storage location of nodes, that is, the subscript of the array should be able to reflect the logical relationship between nodes, such as the relationship between parents and children, the relationship between left and right brothers.

Let’s first look at the sequential storage of a complete binary tree. A complete binary tree is shown in Figure 6-7-1.

Figure 6-7-1

The binary tree is stored in the array with the corresponding subscript corresponding to its same location, as shown in Figure 6-7-2.

Figure 6-7-2

So here’s the advantage of a perfect binary tree. Because of its strict definition, it is possible to express the structure of binary trees with the sequential structure.

Of course, for the general binary tree, although the sequence number does not reflect the logical relationship, it can be numbered as a full binary tree, except that the non-existent nodes are set to “∧”. As shown in Figure 6-7-3, note that the light-colored nodes are not present.

Figure 6-7-3

In an extreme case, a right-slant tree with a depth of K has only K nodes, but 2K-1 storage unit space needs to be allocated, which is obviously a waste of storage space, as shown in Figure 6-7-4. Therefore, the sequential storage structure is generally only used for complete binary trees.

Figure 6-7-4

6.7.2 Binary Linked List

Since sequential storage is not very applicable, we should consider chained storage structure. A binary tree has at most two children per node, so it is a natural idea to design a data field and two pointer fields for it. We call such a list a binary list. Table 6-7- shows the node structure.

Table 6-7-1

Where data is the data field, lChild and rChild are pointer fields, respectively, to the left child and the right child Pointers.

Here is the nodal structure definition code for our binary list.

/* struct BiTNode /* struct BiTNode */ {TElemType data; Struct BiTNode * lChild, * rChild; /* BiTNode, *BiTree;Copy the code

The structure diagram is shown in FIG. 6-7-5.

Figure 6-7-5

As discussed in the storage structure of the tree, an additional field of Pointers to its parent can be added if needed, and this is called a trigeminal list. Since the storage structure is similar to that of a tree, I won’t go into detail here.

Data structure binary tree definition, properties, storage structure