<>10.1 Binary tree
<>10.1.1 Why do you need a tree data structure
* Analysis of array storage mode
advantage ： Accessing elements by subscript , Fast speed . For ordered arrays , Binary search can also be used to improve the retrieval speed .
shortcoming ： If you want to retrieve a specific value , Or insert a value ( In a certain order ) Will move as a whole , Low efficiency [ Sketch Map ]
Draw the operation diagram ：
* Analysis of chain storage mode
advantage ： To a certain extent, the array storage mode is optimized ( such as ： Insert a numeric node , Just insert the into the node , Link to the linked list , Deletion efficiency is also very good ).
shortcoming ： When retrieving , Efficiency is still low , such as ( Retrieve a value , You need to traverse from the beginning node ) 【 Sketch Map 】
Operation diagram ：
* Analysis of tree storage mode
Can improve data storage , Read efficiency , For example, use Binary sort tree (Binary Sort
Tree), It can ensure the data retrieval speed , At the same time, it can also ensure the insertion of data , delete , Speed of modification .
case : [7, 3, 10, 1, 5,9,12]
<>10.1.2 Tree diagram
Common terms for trees ( Understand in combination with schematic diagram ):
* node
* Root node
* Parent node
* Child node
* Leaf node ( Node without child nodes )
* Weight of node ( Node value )
* route ( from root Node finds the route of the node )
* layer
* subtree
* Tree height ( Max layers )
* forest : Multiple subtrees form a forest
<>10.1.3 Concept of binary tree
* There are many kinds of trees , A form in which each node can have at most two child nodes is called a binary tree .
* The child nodes of binary tree are divided into left node and right node
* Sketch Map
* If all leaf nodes of the binary tree are in the last layer , And the total number of nodes = 2^n -1 , n Is the number of layers , Then we call it full binary tree .
* If all leaf nodes of the binary tree are in the last or penultimate layer , And the leaf nodes of the last layer are continuous on the left , The leaf nodes of the penultimate layer are continuous on the right , We call it a complete binary tree .
Technology