Common properties and traversal of trees and binary trees

• degree

How many degrees does a node have , Just look at how many branches this node has , Such as A The degree of the node is 2,B The degree of the node is 1, and D The degree of the node is 3.

• The degree of a tree

The degree of the tree is the degree of the node with the largest degree of the tree , For example, in the figure above , The degree of the tree is 3（ Depending on D Degree of node ）.

• Leaf nodes and non leaf nodes

Degree is 0 The node of is a leaf node , Dufei 0 The node of is a non leaf node , Such as G,H,I It's a leaf node . and C,D,E It's not a leaf node .

• Parent node

A child node, a parent node , In a tree , Except for the root node , All other nodes have a unique parent node

• Ancestral node
  Recurse all parent nodes in turn , for example , node H The ancestor nodes of are DBA,E The ancestor nodes of are CA

• Next generation nodes

Recurse all degree nodes in turn , for example C The descendant nodes of have EFJ,E The descendant nodes of have J.

• Brother node

A node with a common parent node becomes a sibling node , for example B,C,E And F Be brothers to each other

• Cousin node

Nodes at the same level are cousins ,D,E,F Each other's cousins .

• The height of the tree

It means the hierarchy of the tree , There are several floors , The trees above share 4 layer .

• distinguish Degree is m Trees and m Fork tree

Degree is m The tree of indicates that there is at least one node in the tree , And there are m Branches , and m A fork tree indicates that the degree of each node is less than or equal to m. set up m be equal to 3, Then the degree is 3 The trees of at least 4 Nodes , and 3 Fork trees can have 0 Nodes , You can also have any number of nodes , But the degree of each node cannot exceed 3, Can be equal to 3.

Properties of trees

• The total number of nodes of a tree is equal to the total number of degrees of the tree +1

The total degree is the sum of the degrees of all nodes

• Degree is m The tree of , The first i There are at most m ^(i-1) Nodes
  Degree is 5 The tree of , The first 3 There are at most 5² Nodes .
  That is to say, if the degree is 5, The second floor has at most 5 Nodes ,
  Each node in the second layer can have at most 5 Nodes , All the third layer is 5*5 = 25 Nodes .

• The height is h Of m Fork trees have at most m^h-1/m-1 Nodes

The height is 3 Of 5 Fork trees have at most 5*5 + 5 + 1 = 31 individual , Bring in the formula to calculate 5³ - 1 / 4 = 31 It's the same .

• The height is h Of m Fork trees have at least h Nodes

It's easy to understand , the reason being that m Fork tree , So only one node at a time is allowed , Then the height is h Of m If there is only one node in each layer of a fork tree , Then at least there will be h Nodes .

• The height is h, Degree is m There are at least (h + m) - 1 Nodes

First degree is m There are at least m+1 Nodes , You need to add at least one node without adding a layer , therefore h Layers need to be added h Nodes , Subtract the root node sum and degree to m The node of the layer Namely (h+m + 1) - 2 = h + m - 1. For example, the height is 3, Degree is 3 At least 5 Nodes .
The root node , There can be a node under the root node , This node needs to have 3 Nodes , At this time, the degree of satisfaction is 3, The height is 3.

• n Of nodes m The minimum height of the fork tree should be [log_m(n*(m-1)+1)].

15 Of nodes 2 The minimum height of the fork tree is equal to [log₂(15*(2-1)+1) ]= 4.

The result of this height calculation needs to be rounded up .

Properties of full binary tree

• Only the degree of leaf node is 0, The degree of other nodes is 2 That is to say, in a full binary tree , The degree of the node is either 2, Or 0

• If we follow the sequence from top to bottom , From left to right 1 Numbered starting , Is the first i The left child of nodes is 2i, The first i The right child node of nodes is 2i+1, The first i The parent node of nodes is [i/2], Rounding down , for example , The parent node of the third node is 3/2 Rounding down equals to 1.

The properties of complete binary tree

• If a binary tree is not a full binary tree , It should be except that the last floor is not full , Other layers must be full
  In other words, it is not allowed to have non end layers that are not full of binary trees , besides , The nodes of the last layer should be sorted from left to right ,
  There should be no space between .

• In a complete binary tree , Only the last two layers can have leaf nodes

• At most one degree is 1 The node of

• Calculate the position of the parent node and the position of the child node in a complete binary tree

• If one contains n A complete binary tree of nodes , Less than be equal to [n/2] The node of is a branch node , Greater than n/2 The node of is a leaf node .

13 Nodes ,13/2 Rounding down is 6, That is to say, before 6 Nodes are branch nodes , after 7 Nodes are branch nodes .

Binary sort tree

• All child nodes of the left subtree are smaller than the base point , All child nodes of the right subtree are larger than the root node

Balanced binary trees

• The height difference of any subtree cannot exceed 1, That's the red black tree , This algorithm is to avoid the too narrow height of a tree , Make the tree as wide and short as possible , Can be in log₂n Within the time complexity of .

Be careful ： A binary tree is not the same as a full binary tree or a complete binary tree , Full binary tree and complete binary tree are two special binary trees , The degree of binary tree is allowed to be 0,1,2, The degree of full binary tree is allowed to be 0,2, The degree of a complete binary tree is allowed to be 0,1,2, But at most, it can only exist 1 The individual degree is 1 The node of

Binary tree CK nature

• Degree is 0 The point ratio of is 2 A little more （n0 = n2+1）.

Let the total node tree of a binary tree be n individual , Degree is 0 The number of nodes of is n0 individual , Degree is 1 The number of nodes of is n1 individual , Degree is 2 The number of nodes of is n2 individual , be

1. n = n0 + n1 + n2
2. n = n1 + 2n2 + 1

The calculation process of the second formula ： The total number of nodes of a binary tree is the total degree +1,（ Except for the root node , Every other node has a parent node ）.

So in the second formula , n1+2n2 Is the total degree ？ why ？ Because the degree is 1 The node of contributed 1 Degree , Degree is 2 The node of contributed 2 Degree , So the degree is 2 The degree of the node of is multiplied by 2. Finally, add 1, Represents the total number of nodes .

Then use 2 type -1 The formula gives （n0 = n2+1）.

• The height is h Full binary tree Altogether 2²-1 Nodes

• The height is h The full binary tree of i Layer has a 2^i-1 Nodes

Perfect binary tree CK nature

• have n The height of a complete binary tree of nodes is Round up [log₂(n+1)],

or Round down ( [log₂n] + 1 ) .
for example 16 The height of a complete binary tree of nodes is equal to [log₂17], Rounding up is 5.

• Know the number of nodes of a complete binary tree , It can be found that n0,n1,n2

n1 It's Duwei 1 Number of numbers , That's in a full binary tree , At most 0 Or 1 The individual degree is 1 The node of , therefore n1 = 0 or n1 = 1, According to the properties of binary tree n0 = n2 + 1.

n0 + n2 = (n2 + n2 + 1) = 2n2 + 1( It must be odd , The sum of the number of leaf nodes and double branch nodes , It must be odd ), It can be concluded that

1. If a complete binary tree has an even number of nodes , because n0 + n2 It must be odd , therefore n1 be equal to 1, There is a degree 1 The node of . if n0 by k, be n2 by k-1.
2. If a complete binary tree has an odd number of nodes , because n0+n2 Must be an even number , therefore n1 be equal to 0, Yes 0 The individual degree is 1 The node of , if n0 by k, be n2 by k-1.

Sequential storage method to achieve binary tree

Here, in order to number each node according to the previous , So a binary tree needs to be a full binary tree or a complete binary tree .

The first i The left child of nodes is 2i
The first i The right child node of nodes is 2i+1
The first i The parent node of nodes is i/2 Rounding down
The first i Whether the nodes are leaf nodes i > n / 2

Chain storage method to achieve binary tree

Usually , If we use chained storage to realize binary tree , Then the structure needs to contain two pointers , One is the pointer of the left child node , One is the pointer to the right child node . So it can be concluded that . A node is n Two fork tree , share 2n A pointer to the （ Because a node has 2 A pointer to the , All in all 2n A pointer to the ）, Non null pointer n-1 individual （ A non null pointer means that the left and right nodes of the root node do not point to null The node of , Now suppose , Binary trees have n Nodes , At this time, except for the root node , Any other node must have a pointer to it , So there is n-1 Valid pointers ）, Then invalid pointers naturally exist n+1 individual （ That is to point null The pointer to ）.

The traversal of binary tree

The traversal of binary tree mainly includes 4 Ergodic ways
1. In the sequence traversal （ Middle root traversal , Left root right traversal ）：
First traverse the left node , Then traverse the root node , Then traverse the right node , That is to say, for every tree and every sub tree , The root node must be on the left and behind , At the same time, it must be in front of the left node
2. The former sequence traversal （ Front root traversal , Root traversal ）：
Let's go through the root node , Traverse left node again , Then traverse the right node , That is to say, for every tree and every sub tree , The root node must be in front of the left node , The left node must be in front of the right node
3. After the sequence traversal （ Back root traversal , Left and right root traversal ）：
First traverse the left node , Then traverse the right node , Then traverse the root node , That is to say, for every tree and every sub tree , The left node must be behind the right node , The root node must be behind the right node
4. Sequence traversal
This traversal method is from top to bottom , Traverse the tree from left to right , A secondary queue is needed to complete .

For the first three traversal methods, recursive algorithm is needed .

similarly , If you want to calculate the height of the tree , You also need to use recursive algorithms , The height of the tree is equal to the largest height of the left subtree and the right subtree + 1.

The algorithm for calculating the height of the tree is as follows ：

int getTreeHeight(Tree tree) {
    
    if(tree == NULL){
    
        return 0;
    }
    // Calculate the height of the left subtree 
    int leftChildTreeHeight = getTreeHeight(tree->left);
    // Calculate the height of the right subtree 
    int rightChildTreeHeight = getTreeHeight(tree->right);
    return leftChildTreeHeight > rightChildTreeHeight ? leftChildTreeHeight + 1 : rightChildTreeHeight + 1;
}

Construct a binary tree according to the traversal sequence

According to binary tree and some traversal rules , The only traversal order can be obtained , But give a traversal order , It is not necessarily possible to deduce the only binary tree structure . If we can determine the unique binary tree structure , Then there must be at least two ways of traversal , Of these two traversal methods , There must be intermediate traversal

• Before the order + In the sequence traversal

If the preorder traversal is ADBCE
Postorder traversal is BDCAE

Because the first step of preorder traversal is the root node of traversal , So the root node is A, And in the middle order traversal ,A It's No 4 A place , Because the middle order traversal follows the rule of left root right , shows BDC yes A The left child of , and E yes A Right child of , Empathy , Recursion above , You can tick out the only binary tree .

• In the following order + In the sequence traversal

The rules of post order traversal are left and right roots , So the root node must be the last , The left node must be in front of the right node .

Post traversal sequence ： EFAHCIGBD
Middle order traversal sequence ：EAFDHCBGI

The last node of post order traversal must be the root node , The penultimate node must be the root node of the right subtree , Just as the first node of the preorder traversal must be the root node , The second node must be the root node of the left subtree . Then we can determine D Root node ,EAF Is the node of the left subtree ,HCBGD Is the node of the right subtree . because EAF Is a middle order traversal , And the right three nodes , that A The node must be the root node ,E The node is the left child node ,F The node is the right child node . According to the penultimate node of post order traversal B Is the root node of the right node , According to the middle order traversal HC by B Get the left subtree ,GI by B The right subtree . and HC and GI It's both nodes , Who is the parent node is hard to determine , Middle order traversal and post order traversal are both first traversal H Re traversal C, It must not be C Parent node , Because if H Is the parent node , Then post order traversal must be the last traversal H, Now we need to make sure H yes C The left child node or the right child node of , hypothesis H yes C Right child of , Then the middle order traversal should be CH, This is not in line with , So you can be sure H by C The left child of . Similarly, we can determine GI The location of .

• sequence + Middle preface

The first step of sequence traversal is the root node , So we can get the position of the root node in the middle order traversal

Sequence sequence ：DABEFCGHI
Middle order sequence ：EAFDHCBGI

According to sequence sequence ,D Root node , that EAF yes D The left subtree , because A It appears in the second of sequence traversal , therefore A Is the root node of the left subtree ,E yes A The left child of ,F yes A Right child of . stay HCBGI in , According to the sequence traversal ,B Root node , And sequence traversal , First traverse C,C yes H Parent node , According to the middle order traversal H yes C The left child of , and GI First appeared in sequence traversal G, explain G yes I Parent node , And because the middle order traversal is GI, explain I yes G Right child of .