The concept of tree

1

The root node level is 1, Increase in descending order

 

The level of the deepest node in the tree is called the height of the tree

Special form of binary tree

Every node of the binary tree reaches the maximum value , It's called a full binary tree .

 

Binary tree except the last layer , The nodes of each layer reach the maximum , And the last layer of nodes are located on the left , It's called a complete binary tree . 

A full binary tree also belongs to a complete binary tree .

Storage form of binary tree

  Because the structure of complete binary tree is continuous , There are traces to follow , Sequential storage can be adopted .

From left to right , Store the nodes in the array from top to bottom .

Incomplete binary tree , Node does not exist and can be used null Placeholder in array , But it's a waste of space .

Ordinary binary tree has irregular structure , Sequential storage is not suitable , To record the relationship between nodes , Chain storage can be used .

Each node passes through value Indicated value ,left、right, Represents the left and right child nodes .

1