Learn binary tree like this

   Preface
Trees are the top priority in data structures , Especially in various
Binary tree is the difficulty of learning . all the time , The mastery of trees is ambiguous , Now I hope to write a special series on binary trees . At the same time of learning and summarizing, more in-depth understanding and mastery of binary tree . This series of articles will focus on general binary trees 、 Perfect binary tree 、 Full binary tree 、 Clue binary tree 、 Hoffman tree 、 Binary sort tree 、 Balanced binary trees 、 Red and black trees 、B Trees . I hope all readers can pay attention to the topic , And give corresponding opinions , Through a series of learning, we can have “ Trees ”.

1 Key concepts
1.1 Node concept
Node is the basis of data structure , It is the basic unit of complex data structure .

1.2 Tree node declaration
The nodes mentioned in this series refer to the nodes of trees . for example ： node A It is shown in the figure as ：

2 Trees
2.1 Definition
Trees （Tree） yes n（n>=0) A finite set of nodes .n=0 Time is called empty tree . In any non empty tree ：
1） There is and only one specific one called a root （Root） The node of ;
2） When n>1 when , The rest of the nodes can be divided into m(m>0) A finite set that doesn't intersect each other T1、T2、…、Tn, Each of these sets is itself a tree , And called the root of the subtree .

Besides , The definition of tree also needs to emphasize the following two points ：
1）n>0 When the root node is unique , It is impossible to have multiple root nodes , A tree in a data structure can only have one root node .
2）m>0 when , There is no limit to the number of subtrees , But they must be disjoint .
Sample tree ：
The following picture shows an ordinary tree ：

From the definition of tree, we can see that , The tree is defined recursively . Recursion plays an important role in tree learning , If you don't know much about recursion , It is suggested to look at the recursive algorithm first

2.2 The degree of node
The number of subtrees owned by a node is called the degree of the node .
The degree of each node of the tree shown is marked in the figure .

2.3 Node relations
The root node of the node subtree is the Child node . The corresponding node is called the child node Parents node .
Above picture ,A by B The parent node of ,B by A The child node of .
Children of the same parent node are called each other Brother nodes .
Above picture , node B And nodes C They are brothers and nodes of each other .

2.4 Node level

Starting from the root , The root is the first layer , The child of root is the second layer , And so on .
The following figure shows the hierarchical relationship of the tree shown

2.5 Depth of tree

The maximum number of layers of nodes in a tree is called the depth or height of the tree . The depth of the tree shown in the above figure is 4.

3 Binary tree

3.1 Definition

Binary tree yes n(n>=0) A finite set of nodes , The set is either empty （ It's called an empty binary tree ）, Or by a root node and two mutually disjoint 、 They are called the left subtree and the right subtree of the root node .
chart 3.1 It shows an ordinary binary tree ：

chart 3.1 Binary tree

3.2 Binary tree features
From the definition of binary tree and graphic analysis, it is concluded that binary tree has the following characteristics ：
1） Each node has at most two subtrees , So the nonexistence of binary tree is greater than 2 The node of .
2） The left and right subtrees are ordered , The order cannot be arbitrarily reversed .
3） Even if there is only one subtree at a certain node in the tree , We also need to distinguish whether it is a left or right subtree .

3.3 Binary tree properties

1） On the second of the binary tree i There is a maximum of 2i-1 Nodes .（i>=1）
2） In a binary tree, if the depth is k, So at most 2k-1 Nodes .(k>=1）
3）n0=n2+1 n0 The degree is 0 Of nodes ,n2 The degree is 2 Of nodes .
4） stay Perfect binary tree in , have n The depth of a complete binary tree of nodes is [log2n]+1, among [log2n] It's rounding down .
5） If to contain n A complete binary tree of nodes proceeds from top to bottom and from left to right 1 to n The number of , Then, for any one of the complete binary trees, the number is i The node has the following characteristics

(1) if i=1, Then the node is the root of the binary tree , Unmarried parents , otherwise , The number is [i/2] The node of is its parent node ;
(2) if 2i>n, Then the node has no left child , otherwise , The number is 2i The node of is its left child node ;
(3) if 2i+1>n, Then the node has no right child node , otherwise , The number is 2i+1 The node of is its right child node .

3.4 Oblique tree

Oblique tree ： All nodes have only the binary tree of the left subtree called the left oblique tree . All nodes are binary trees with only right subtrees called right skew trees . Both of them are collectively referred to as inclined trees .

chart 3.2 Left oblique tree

chart 3.3 Right slant tree

3.5 Full binary tree

Full binary tree ： In a binary tree . If all branch nodes have left and right subtrees , And all the leaves are on the same layer , Such a binary tree is called a full binary tree .
Full binary trees are characterized by ：
1） Leaves can only appear on the bottom layer . It's impossible to strike a balance in other layers .
2） The degree of a non leaf node must be 2.
3） In a binary tree of the same depth , The full binary tree has the most nodes , Most leaves .
chart 3.4 Full binary tree
3.6 Perfect binary tree
Perfect binary tree ： For one with n The binary tree of nodes is numbered by layer , If the number is i(1<=i<=n) The node of the tree and the full binary tree of the same depth are numbered i The nodes of are exactly the same in the binary tree , This binary tree is called a complete binary tree .
chart 3.5 Show a complete binary tree
chart 3.5 Perfect binary tree

characteristic ：
1） Leaf nodes can only appear in the lowest and second lower layers .
2） The lowest leaf nodes are concentrated on the left side of the tree .
3） If there are leaf nodes in the penultimate layer , It must be in the right consecutive position .
4） If the node degree is 1, Then this node has only the left child , There is no right subtree .
5） A binary tree with the same number of nodes , The depth of a complete binary tree is the smallest .
notes ： A full binary tree must be a complete binary tree , But it doesn't have to be the other way around .

3.7 Binary tree storage structure

3.7.1 Sequential storage

The sequential storage structure of binary tree is to use one-dimensional array to store nodes in binary tree , And the storage location of the node , It's the subscript index of the array .

chart 3.6
chart 3.6 A complete binary tree shown here is stored in order , Pictured 3.7 Express ：

From the figure 3.7 It can be seen that , When a binary tree is a complete binary tree , The number of nodes just fills the array .
So when a binary tree is not a complete binary tree , How about sequential storage ？ for example ： For Graphs 3.8 Description of the binary tree ：

The light colored node indicates that the node does not exist . Then the figure 3.8 The sequential storage structure of the binary tree shown in Fig 3.9 Shown ：

among ,∧ Indicates that there is no storage node at this position in the array . Now you can see , There has been a waste of space in the sequential storage structure .
So for graphs 3.3 The sequence storage structure corresponding to the extreme case of the right slanted tree is shown in the figure 3.10 Shown ：

From the figure 3.10 It can be seen that , For this extreme case of right slanted trees , Using sequential storage is a waste of space . therefore , Sequential storage is generally applicable to complete binary trees .

3.7.2 Binary list

Since sequential storage can not meet the storage requirements of binary tree , So consider chain storage . From the definition of binary tree, we can see that , Each node of a binary tree has at most two children . therefore , The node data structure can be defined as one data and two pointer fields . The representation is shown in the figure 3.11 Shown ：


chart 3.12 A linked list structure is used to store the binary tree , This list is called a binary list .

3.8 Binary tree traversal

The traversal of binary tree is a key knowledge point .

3.8.1 Definition

The traversal of binary tree means starting from the root node of binary tree , Access all nodes in the binary tree in a certain order , Make each node be visited once , And only visited once .
The access order of binary tree can be divided into four kinds ：

The former sequence traversal In the sequence traversal After the sequence traversal Sequence traversal

3.8.2 The former sequence traversal
Generally speaking, preorder traversal starts from the root node of a binary tree , The node data is output when it reaches the node for the first time , Go left first and then right .

The previous access is as follows

Starting from the root node , Then it reaches the node for the first time A, Therefore, the output A; Continue to visit left , The first time you visit a node B, Therefore, the output B; According to the same rules , Output D, Output H;
When we reach the leaf node H, Back to D, This is the second time we have arrived D, So it's not output D, And then to D Right subtree access ,D The right subtree is not empty , Then visit I, Arrive for the first time I, The output I;
I For leaf nodes , Then go back to D,D The left and right subtrees have been visited , Then go back to B, And then to B Right subtree , Arrive for the first time E, Therefore, the output E; towards E The left subtree , Therefore, the output J;
According to the same access rules , Continue to output C、F、G;

The preorder traversal output of the binary tree is ：
ABDHIEJCFG

3.8.3 In the sequence traversal
The middle order traversal starts from the root node of the binary tree , When it reaches the node for the second time, it outputs the node data , Go left first and then right .

The sequence access in the binary tree is as follows ：

Starting from the root node , Then it reaches the node for the first time A, No output A, Continue to visit left , The first time you visit a node B, No output B; Continue to arrive D,H;
arrive H,H The left subtree is empty , Then go back to H, At this point, the second visit H, Therefore, the output H; H The right subtree is empty , Go back to D, At this point, the second arrival D, Therefore, the output D;
from D Go back to B, A second arrival B, Therefore, the output B; Follow the same rules to continue to visit , Output J、E、A、F、C、G;

The middle order traversal output of the binary tree is ：
HDIBJEAFCG

3.8.4 After the sequence traversal
The post order traversal starts from the root node of the binary tree , When it reaches the node for the third time, it outputs the node data , Go left first and then right .

The post order access of binary tree is as follows ：

Starting from the root node , Then it reaches the node for the first time A, No output A, Continue to visit left , The first time you visit a node B, No output B; Continue to arrive D,H;
arrive H,H The left subtree is empty , Then go back to H, At this point, the second visit H, No output H; H The right subtree is empty , Go back to H, This is the third time we arrive H, Therefore, the output H;
from H Go back to D, A second arrival D, No output D; Continue to visit I,I Left and right subtrees are empty , So the third visit I when , Output I; Go back to D, This is the third time we arrive D, Therefore, the output D;
Follow the same rules to continue to visit , Output J、E、B、F、G、C,A;

The post order traversal output of the binary tree is ：
HIDJEBFGCA

Although the traversal process of binary tree seems tedious , But because a binary tree is a recursively defined structure , So the code of traversing the binary tree recursively is very simple .
If you want to know the implementation code, you can go here to have a look java Realize the of binary tree Node Node definition , Hand tearing 8 Kind of traversal _ silently J The blog of -CSDN Blog _java node

3.8.5 Level traversal
Hierarchical traversal is to traverse the binary tree from top to bottom according to the tree hierarchy . The hierarchical traversal result of the binary tree shown in the above figure is ：
ABCDEFGHIJ
The detailed method of hierarchical traversal can refer to the layer by layer traversal method of binary tree .

3.8.6 Go through the usual exam sites

There is a typical question type for traversing a binary tree .
1） We know the preorder traversal sequence and the middle order traversal sequence , Identify a binary tree .
Example ： If the preorder traversal of a binary tree is ABCDEF, The middle order traversal is CBAEDF, Please draw the binary tree .
analysis ： The first output node of preorder traversal is the root node , so A Is the root node . In the early middle order traversal, the root node is in the middle of the left and right subtree nodes , So the node A In the left subtree of, there are CB, The nodes in the right subtree have EDF.
As shown in the figure ：

In the same way , Yes A To divide the left and right subtrees of , Finally, the form of binary tree is shown in the figure ：

2） We know the sequence of post order traversal and the sequence of middle order traversal , Identify a binary tree .
In the post order traversal, the last visited node is the root node , So you can do the same thing , After finding the root node, it is divided into two subtrees , Then continue to find the root node of the subtree , Step by step, determine the shape of the binary tree .
notes ： We know preorder traversal sequence and postorder ergodic sequence , You can't uniquely identify a binary tree .

4 Conclusion
Through the above introduction , We have a preliminary understanding of binary trees . This article introduces the basic knowledge, hope readers can firmly grasp , And be able to model a binary tree in your mind , Lay a good foundation for the follow-up study .