Shulou(Shulou.com)06/01 Report--

Today, I will talk to you about how to analyze the binary tree. Many people may not know much about it. In order to let you know more, Xiaobian summarized the following contents for you. I hope you can gain something according to this article.

Binary tree:

A binary tree is a tree structure with at most two subtrees per node. The subtrees are usually called "left subtrees" and "right subtrees." Binary trees are often used to implement binary search trees and binary heaps. His structure looks like this:

A is the root node of the binary tree, B and E are the child nodes of A, CD is the child node of B, and F is the child node of E. Doesn't it look like a fallen tree? Each node divides into two branches, hence the name binary tree.

Binary tree is divided into full binary tree, complete binary tree and balanced binary tree (AVL tree).

Balanced binary tree is a binary tree data structure based on dichotomy strategy to improve the speed of data search; in this article, I will not introduce more, and I will have a chance to open a separate chapter to explain.

Full binary tree and complete binary tree:

A binary tree with depth k and 2^k-1 nodes is called a full binary tree. This tree is characterized by the maximum number of nodes at each level. In a binary tree, except for the last layer, if the remaining layers are full, and either the last layer is full, or there are several consecutive nodes missing on the right, then the binary tree is completely binary. A complete binary tree with n nodes has a depth of floor(log2n)+1. A complete binary tree of depth k with at least 2k-1 leaf nodes and at most 2k-1 nodes. See below:

Some beginners may see the above introduction with a circle, so I summarize it in popular words:

A full binary tree is one in which every node except the leaf node (the lowest level) has two children.

A complete binary tree is a leaf node (the bottom layer) nodes must be connected from the left, can not be broken, and remove the last layer, if a full binary tree, two conditions are indispensable.

After reading the above, do you have any further understanding of how to analyze binary trees? If you still want to know more knowledge or related content, please pay attention to the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.