# Binary tree of data structure

2020-11-10 14:46:10

### 1 Key concepts

#### 1.1 Node concept

A binary tree is a finite set of nodes , The set is either empty , Or a root node plus two left and right subtrees
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 ：
chart 2.1 For an ordinary tree ： chart 2.1 Common 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's suggested to have a look at [ A recursive algorithm ][Link 4]

#### 2.2 The degree of node

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

##### 2.3 Node relations

The root node of the node subtree is the child node of the node . The corresponding node is called the parent node of the child node .
chart 2.2 in ,A by B The parent node of ,B by A The child node of .
The child nodes of the same parent node are called brother nodes .
chart 2.2 in , 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 .
chart 2.3 It shows the picture 2.1 The hierarchical relationship of the tree shown chart 2.3 Layer diagram

##### 2.5 Depth of tree

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

### 3 Binary tree

#### 3.1 Definition

The binary tree is 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） In a complete binary tree , 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 ： chart 3.7 Sequential storage

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 ： chart 3.8.png

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 ： chart 3.9

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 ： chart 3.10

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.11

Define node code ：

``````typedef struct BiTNode{
TElemType data;// data  struct BiTNode *lchild, *rchild;// Left and right child pointer  } BiTNode, *BiTree;
``````

Plan 3.6 The binary tree shown here can use graph 3.12 Express . chart 3.12

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 . 3.13

chart 3.13 The binary tree access shown 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;

be 3.13 The output of the preorder traversal of the binary tree shown 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 .

chart 3.13 The binary tree is shown 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;

be 3.13 The output of the middle order traversal 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 .

chart 3.13 The binary tree is shown 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;

Plan 3.13 The output of the post order traversal of the binary tree shown 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 .

##### 3.8.5 Level traversal

Hierarchical traversal is to traverse the binary tree from top to bottom according to the tree hierarchy . For Graphs 3.13 The hierarchical traversal result of the binary tree shown is ：
ABCDEFGHIJ

##### 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.
Pictured 3.14 Shown ： chart 3.14

In the same way , Yes A To divide the left and right subtrees of , Finally, the shape of binary tree is shown in the figure 3.15 Shown ： chart 3.15.png

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 summary

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 .

Official account :java Treasure 