“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

💦 The concept of binary trees

A binary tree is a finite set of nodes: 1, or empty 2, consisting of a root node plus two binary trees separately called left and right subtreesCopy the code

1️ binomial tree there is no node with degree greater than 2

2️ binomial tree has left and right subtrees and the order cannot be reversed, so binomial tree is orderly tree

⚠ Note: For any binary tree, the following conditions are compounded:

❓ does such a binary tree exist in reality ❔

In the case of human intervention must exist, because there is nothing a chainsaw can’t solveOf course, there are also some extraordinary works of nature, pay attention to the difference between ordinary trees

💦 Special binary tree

1️ full binomial tree: a binomial tree, if the number of nodes on each layer reaches the maximum, the binomial tree is full binomial tree. In other words, if a binary tree has K levels, and the total number of nodes is 2 to the K minus 1, it is a full binary tree.

2️ complete binomial tree: The first k-1 layer of a complete binary tree is full, and the KTH layer is not necessarily full (which means that a full binary tree is a complete binary tree, but a complete binary tree is not necessarily a full binary tree), but it must be continuous from left to right from the last layer, that is to say, a complete binary tree has at least 0 nodes of 1, and at most 1. Complete binary tree is a very efficient data structure. Complete binary tree is derived from full binary tree. For the depth of K, a binary tree with n nodes, and each node corresponds to the nodes numbered from 1 to n in the full binary tree with depth of K, is called a complete binary tree. It is important to note that full binary trees are a special kind of complete binary tree.

▶ The number of nodes in a full binary tree is the sum of equal proportions2^0^ + 2^1^ + 2^2^ + 2^(k-1)^

So the number of nodes in a full binary tree is 2 to the k to the minus 1

▶ Number of nodes in the complete binary tree

Maximum: 2^k – 1 This is a full binary tree

At least: 2^(k-1)^ -1 + 1 -> 2^(k-1)^

2 to the k minus 1 to the minus 1 is the number of nodes in the first k minus 1 layer, plus 1 is at least one node in the k layer

💦 Properties of binary trees

1️ if the number of layers of root nodes is 1, there are at most 2^(i-1) nodes on the i-th layer of a non-empty binary tree

2️ if the number of layers of root nodes is 1, the maximum number of nodes in a binary tree with depth of H is 2^ H-1

3️ one of the binocular trees with n₀ as the number of leaf nodes with a degree of 0 and N ₂ as the number of branch nodes with a degree of 2, we will have N ₀ = N ₂+1

4️ if the number of layers of root nodes is 1, the depth of a full binary tree with n nodes is H = log₂(n+1) PS: log₂(n+1) is the logarithm of log base 2, n+1

5️ one for a complete binary tree with N nodes, if all nodes are numbered starting from 0 according to the array sequence from top to bottom and left to right, the node with serial number I can be:

▶ if I >0, parent serial number of node at position I :(i-1)/2; I =0, I is the number of the root node, there is no parent node

▶ if 2i+1<n, left child serial number: 2i+1, 2i+1>=n otherwise, there is no left child

▶ if 2i+2<n, right child serial number: 2i+2, 2I +2>= N Otherwise, no right child

💦 binary tree concept multiple choice questions

1. A binary tree has 399 nodes, including 199 nodes with degree 2, so the number of leaf nodes in the binary tree is ().

A. There is no such binary tree

B. 200

C. 198

D. 199

📝 analysis: The leaf nodes here are nodes with degree 0. Given that there are 199 nodes with degree 2 in the binary tree, nodes with degree 0 are equal to nodes with degree 2 +1, so option B is selected

2, the following data structure is not suitable for the use of sequential storage structure ()

A. Incomplete binary trees

B. the heap

C. the queue

D. the stack

📝 analysis: Sequential structure storage is the use of arrays for storage, it is only suitable for full binary trees, because not full binary trees will have a waste of space. Arrays are only suitable for storing complete or full binary trees.

So that’s choice A

3. In a complete binary tree with 2n nodes, the number of leaf nodes is

A. n

B. n+1

C. n-1

D. n/2

📝 analysis:

Assuming that the number of degrees 0 is x0, the number of degrees 2 is X2, and the number of degrees 1 is x1, then:

▶ x0 + x1 + x2 = 2n

▶ x0 = x2 + 1

So x0 is equal to x2 plus 1, x2 is equal to x0 minus 1

So x0 plus x1 plus x2 is equal to 2n is the same thing as x0 plus x1 plus x0 minus 1 is equal to 2n

Now if you go back and think of a complete binary tree where there are at least zero nodes of 1, at most one node,

So x1 is equal to 0 or 1

So 2×0 + x1-1 = 2n there are two cases:

▶ 2×0 + 0-1 = 2n

▶ 2×0 + 1-1 = 2n

So it’s pretty clear that when x1 is equal to 0, x0 is a decimal, which is obviously impossible; That’s true when x1 is equal to 1, so that’s choice A

4. If the number of nodes in a complete binary tree is 531, the height of the tree is ().

A. 11

B. 10

C. 8

D. 12

📝 analysis:

Assuming that the height of the complete binary tree is H, then: there are at most 2^h-1 nodes; At least 2 to the h minus 1 nodes

▶ H = 11: maximum 2047; At least 2014, so it doesn’t make sense

▶ H = 10: maximum 1023; 512 minimum, so it makes sense

▶ H = 8: maximum 255; Minimum 128, so it doesn’t make sense

▶ H = 12: maximum 4095; Minimum 2048, so it doesn’t make sense

So that’s choice B

5. A complete binary tree with 767 nodes and the number of leaf nodes is

A. 383

B. 384

C. 385

D. 386

📝 Analysis: This question is similar to question 3

Assuming that the number of degrees 0 is x0, the number of degrees 2 is X2, and the number of degrees 1 is x1, then:

▶ x0 + x1 + x2 = 767

▶ x0 = x2 + 1

So x0 is equal to x2 plus 1, x2 is equal to x0 minus 1

So x0 plus x1 plus x2 is equal to 767 is the same thing as x0 plus x1 plus x0 minus 1 is equal to 767 is the same thing as 2×0 plus x1 minus 1 is equal to 767

Now if you go back and think of a complete binary tree where there are at least zero nodes of 1, at most one node,

So x1 is equal to 0 or 1

So 2×0 + x1-1 = 767 there are two cases:

▶ 2×0 + 0-1 = 767

▶ 2×0 + 1-1 = 767

So the answer is clear, when x1 is equal to 0, it satisfies this condition; When x1 is equal to 1, that’s not true, so that’s choice B

💦 Storage structure of binary tree

Binary trees can generally be stored using two types of structure, a sequential structure and a chain structure:.

1️ sequential storage: Sequential structure storage is the use of array to store, it is only suitable for the representation of complete binary tree, because not complete binary tree will have space waste. In reality, only the heap uses arrays for storage. Binary tree sequential storage is physically an array and logically a binary tree. As you can see in the figure below, arrays are only suitable for storing complete or full binary trees.

❓ how to express the relationship between subscript and tree ❔

The subscript is the formula for the parent-child relationship in the tree:

The left child and the right child

Leftchild = parent * 2 + 1

Rightchild = parent * 2 + 2

Fathers (here the formula applies to both left and right children)

Parent = (child-1) / 2

2️ chain storage: the chain storage structure of binary tree refers to the use of linked list to represent a binary tree, that is, linked list to indicate the logical relationship of elements. The usual method is that each node in the linked list consists of three fields, the data field and the left and right pointer field. The left and right Pointers are used to give the storage address of the chain where the left and right children of the node reside respectively. The chain structure is divided into two chains and three chains. At present, we only know two chains in this paper. In the future, when we write about higher-order data structures, such as red-black trees, three chains will be used.

How do ❓ define binary and trigeminal chains ❔

A binary chain can only find the child through the father, similar to a one-way list; A three-pronged chain not only finds the child through the father, but also finds the father through the child, similar to a two-way linked list.

typedef int BTDataType;
/ / binary chain
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pLeft; // Points to the left child of the current node
	struct BinaryTreeNode* _pRight; // Points to the right child of the current node
	BTDataType _data; // The value range of the current node
}

/ / fork chain
struct BinaryTreeNode
{
	struct BinaryTreeNode* _pParent; // Points to the parent of the current node
	struct BinaryTreeNode* _pLeft; // Points to the left child of the current node
	struct BinaryTreeNode* _pRight; // Points to the right child of the current node
	BTDataType _data; // The value range of the current node
}
Copy the code