Basic knowledge of binary tree

Trees and binary trees

A binary tree is an ordered tree , If its left and right subtrees are reversed , It becomes a different binary tree . Even if the node in the tree has only one subtree , We also need to distinguish whether it is a left or right subtree .

Special binary tree ：

1. Full binary tree ： The height of a tree is h, And it contains 2^h-1 A binary tree of nodes becomes a full binary tree , That is, each layer in the tree contains the most nodes .

2. Perfect binary tree ： If the last node removed from the binary tree is a full binary tree , And the nodes of the last layer are distributed from left to right , This binary tree is called a complete binary tree .

• if i < $\lfloor n/2\rfloor$ , The node I For branch nodes , Otherwise, it is a leaf node
• Leaf nodes can only appear on the two largest layers . For the leaf nodes in the largest layer, they are arranged in the leftmost position of the layer
• If there is a degree of 1 The node of , There can only be one , And the node has only left children and no right children
• After numbering by sequence , Once a node appears ( The number is i) For leaf nodes or only left children , The number is greater than i All nodes of are leaf nodes
• if n It's odd , Then each branch node has left child and right child ; if n For the even , Then the largest branch node becomes better ( The number is n/2) Only the left child , No right child , Other branch nodes have left and right children .

3. Binary sort tree ： The keywords of all nodes on the left subtree are smaller than those of the following nodes ; The keywords of all nodes on the right subtree are greater than those of the following nodes ; The left subtree and the right subtree are each a binary sort tree
4. Balanced binary trees ： The depth difference between the left subtree and the right subtree of any node in the tree does not exceed 1

Binary tree storage structure

The sequential storage of binary tree refers to using a group of storage units with continuous addresses from top to bottom , Store node elements on a complete binary tree from left to right , It will be completely numbered as... On the binary tree i The node elements of are stored in a one-dimensional array with the subscript i In the weight of
According to the properties of binary trees , Complete binary tree and full binary tree are more suitable for sequential storage .

Chain store , Use linked list to complete the storage of binary tree .

Traversal of binary tree

Traversal of binary tree refers to accessing each node in the tree according to a certain search path , So that each node is accessed once , And only once .
Common traversal order ： Preface (NLR), Middle preface (LNR), In the following order (LRN)

// The first sequence traversal 
void PreOrder(BiTree T){
    
	if(T != NULL){
    
		visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
// In the sequence traversal 
void InOrder(BiTree T){
    
	if(T != NULL){
    
		InOrder(T->lchild);
		visit(T);
		InOrder(T->rchild);
	}
}

// After the sequence traversal 
void PostOrder(BiTree T){
    
	if(T != NULL){
    
		PostOrder(T->lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

A binary tree can be uniquely determined by the preorder sequence and middle sequence of the binary tree ;
A binary tree can be uniquely determined by the post order sequence and middle order sequence of the binary tree ;

Clue binary tree

effect ： Speed up the traversal of binary tree
Regulations ： If there is no left subtree , Make lchild Point to its precursor node ; If there is no right subtree , Make rchild Point to its successor node .
Add two more flag fields to identify that the pointer field points to the left ( Right ) Children are still pioneers ( The subsequent )