Binary tree concept

  1. The definition of a tree .

    A tree is formed by connecting nodes , The next node connected by each node cannot be connected to each other , Otherwise, the graph is not a tree .

  2. Classification of tree nodes .

    The root node ： The first node of the tree .

    degree ： Connect 2 Nodes , It's Duwei 2, Connect 1 Nodes , It's Duwei 1, Do not connect nodes , It's Duwei 0.

    Leaf nodes ： Nodes that are not connected to nodes are called leaf nodes .

  3. Tree hierarchy .

    The maximum depth of a node in a tree .

  4. Brief description of tree graph ( Example of binary tree ).

  5. The definition of binary tree .

    Each node has at most two subtrees , The order of left and right subtrees .

  6. Five basic forms of binary trees .

    ① Empty binary tree .

    ② Only one root node .

    ③ Only the left sub tree .

    ④ Only the right subtree .

    ⑤ There are both left and right subtrees .

  7. Special case of binary tree .

    ① Oblique tree ： Equivalent to left subtree and right subtree

    ② Full binary tree ： Maximum depth — The lowest depth is equal to 0, And the nonexistence degree is 1 The situation of .

    ③ Balanced subtree ： Maximum depth — The minimum depth is less than or equal to 1 The are .

    ④ Perfect binary tree ：1、 Leaf nodes have only the last two layers .2、 The lowest leaves can only be arranged from left to right .3、 Last but not least 2 layer , If there are leaf nodes , It must be right continuous .4、 If the node degree is 1, It must be connected to the left node .5、 Same node arrangement , The depth of a complete binary tree is the smallest .

  8. Properties of binary trees .

    ① At most per floor 2^(i-1) Nodes .

    ② Depth is k There are at most 2^k-1 Nodes .

    ③ For any binary tree , Degree is 0 The node of ( total N0) Yes, the degree is 2 The node of ( total N2) Of ：N0=N2-1.

    ④ have n The depth of the binary tree of nodes is |log2^n|+1, Such as log2^15+1=4.

    ⑤ For one n A binary tree of nodes , After numbering

    1、 If i=1, Then there is no connection to his previous node . if i>1, Then the node connecting it is |i/2|, Such as 3/2=1.

    2、 If 2i>n, The node i No left child tree , Otherwise, the left subtree is numbered 2i.

    3、 If 2i+1>n, The node i No right subtree , Otherwise, the right subtree is numbered 2i+1.

  9. Traversal of binary tree .

    DFS Depth-first traversal ： abbreviation Shenyou .

    BFS Breadth first traversal ： abbreviation Guangyou .

    The following figure is a binary tree for explanation and analysis .

    D The node value   L The left subtree value of this node   R The right subtree value of this node  

    Shenyou  ①—— The former sequence traversal DLR： Output ABDGHJCEIF

analysis ：A Advanced stack , After coming out , Stack right and left , Put the right and left on the stack after each one , Until it is finished, it is the element output of the preorder traversal .

     Shenyou  ②—— In the sequence traversal LDR： Output GDJHBAEICF

analysis ：A Start turning left All Put nodes on the stack , Each one will be on the left side of the right subtree All Put it on the stack , If there is no right, it will go out .

     Shenyou  ③—— After the sequence traversal LRD： Output GJHDBIEFCA

analysis ：A Begin to Put all the left ones on the stack , At the last moment Judge whether there is a node on the right , Some words Put the left side of the right subtree into the stack one by one , until No more Just one , After going out , Right again There are no nodes in the right subtree of the judgment that is about to be given , Existence continues to stack all the left and right , Until all elements are output .

    Guangyou —— Sequence traversal ( queue )： Output ABCDEFGHIJ

analysis ：A advanced , After coming out, put it in the left and right order , Put each one in the left and right order , Until completion .