Perfect binary tree, complete binary tree, perfect binary tree

1、 Binary tree （Binary Tree)

1.1 What is a binary tree （Binary Tree)

Each node has at most two subtrees ( That is, there is no greater than in the binary tree 2 The node of ), also , The subtree of a binary tree has left and right branches , The order cannot be reversed arbitrarily .

1.2 Properties of binary trees

1. If the level of binary tree is from 0 Start , It's in the second place of the binary tree i Layer up to have a 2^i Nodes (i>=0).
2. The height is k There are at most 2^(k+1) - 1 Nodes (k>=-1). ( The height of the empty tree is -1)
3. Any binary tree , If its leaf node ( Degree is 0) The number of m, Degree is 2 The node number of is n, be m = n + 1.

2、 Perfect binary tree

One depth is k(>=-1) And there are 2^(k+1) - 1 A binary tree with two nodes is called Perfect binary tree
let me put it another way ： The trees are full , It's still binary
The graph looks like this ：

３、 Perfect binary tree (Complete)

The complete binary tree satisfies the perfect binary tree from the root node to the penultimate layer , The last layer can not be completely filled , Its leaf nodes are aligned to the left

The figure below shows No A tree is completely (Complete) Binary tree

If you will number 11(K) Node number 6(E) The position of the left son of moves to the number 5(E) The right son of , It becomes a complete tree (Complete) Binary tree .

• Actually , Understand completely (Complete) A binary tree can be constructed by means of a stack (stack) Thought . for example , Make the first picture perfect (Perfect) All nodes of the binary tree are numbered 1, 2, 3, …, 15 Stack in turn (push). that , Every time the stack goes out (pop) After the operation , In the stack Saved node set Corresponding to the graph, there is a complete tree (Complete) Binary tree

４、 Complete binary tree

The degree of all non leaf nodes is 2
let me put it another way ： As long as you have children , You must have Two children .

Reference blog ：
Perfect binary tree , Complete binary tree and perfect binary tree

---

example ：
One has 767 A complete binary tree of nodes , The number of leaf nodes is ____
A . 383
B . 384
C . 385
D . 386

n = n2+n1+no
n0 = n2 + 1

We can get the equation ：n0= (768-n1) / 2, Because the node of complete binary number is １ The number of is not １ Otherwise 0, So choose Ｂ.

• n： Total nodes
• n2： Degree is ２ Of nodes
• n1： Degree is １ Node book of
• n0： Degree is ０ Number of nodes