There are two ways to implement binary trees, which are: 1. Sequential storage, which refers to using a sequence table to store binary trees, and is only applicable to complete binary trees; 2. Chained storage, when storing binary trees in link mode, each In addition to storing the data of the node itself, a node should also set two pointer fields lchild and rchild.
Binary tree
Five basic forms: empty binary tree, binary tree with only root node, binary tree with only root node Binary tree with node and left subtree TL, binary tree with only root node and right subtree TR, binary tree with root node, left subtree TL and right subtree TR
Other binary trees: skew binary tree, full binary tree, Perfect binary tree
Implementation method: sequential storage, chained storage
Sequential storage of binary trees refers to the use of sequential tables (arrays) to store binary trees. It should be noted that sequential storage only applies to complete binary trees. In other words, only complete binary trees can be stored using sequential tables. Therefore, if we want to store ordinary binary trees sequentially, we need to convert the ordinary binary tree into a complete binary tree in advance.
Each node of a binary tree has at most two children. When storing a binary tree in link mode, in addition to storing the data of the node itself, each node should also set two pointer fields lchild and rchild, pointing to the left child and right child of the node respectively.
The above is the detailed content of There are several ways to implement a binary tree. For more information, please follow other related articles on the PHP Chinese website!