- 2021-10-11 09:05
*views 16*- Java
- Binary tree
- Java Data structure and algorithm
- algorithm
- data structure

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

- Java242 blogs
- Python241 blogs
- Vue112 blogs
- algorithm96 blogs
- c language93 blogs
- Flow Chart81 blogs
- MySQL71 blogs
- C++64 blogs
- more...

Daily Recommendation

© ioDraw All rights reserved

It is necessary to work alone ： On embedded modular programming , Importance of drive separation computer network - Difference between router and switch Self made card drawing simulator QFont Quick sort （Quick sort） computer network - Agreement and hierarchy PTA— Read numbers （C language ） Two methods 【 Game summary 】2022 Summary of the 13th Blue Bridge Cup Android development Button Control usage details js of indexOf method