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

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