Properties and traversal of binary trees

Form of binary tree ：

// The form of binary tree nodes ： Construct a binary tree with a structure similar to a linked list node 
struct node {
	int data;
	node* lchild,rchild;
}; 

Construction of binary tree nodes ：
 

// Construct a binary tree node ： Use custom functions ;
node* newNode(int w){//w Is the weight  
	node* Node=new  node;// You can also write node *Node=(node*)malloc(sizeof(node)), The function is to open up space for nodes ;
	Node->data=w;
	Node->lchild=NULL;
	Node->rchild=NUll;
	return Node; 
}

Search and modify binary tree ：

// Search and modify binary tree ;
// Using recursive functions , Recursive function == Recursive boundary + Recursive ; 
void search(node* root,int x,int newdata){//x Is the value to look for ,newdata Is the value to modify ;
	if(root==NULL){// Recursive boundary  
		return ;
	} 
	if(root->data==x){
		root->data=newdata;
	}
	search(root->lchild,x,newdata);// Recursive ; 
	search(root->rchild,x,newdata);
} 

The insertion of a binary tree ：
 

// Insertion of binary tree nodes 
// Where the node search fails is where the binary tree node can be inserted ;
// Also use recursive functions ; 

void insert(node* &root,int x){// Need to use reference , Because new nodes are created here , It affects the structure of the whole binary tree , In particular, the impact of the new node on the parent node ; 
	if(root==NULL){// Recursive boundary ; 
		// Find the location and create the node '; 
		root=newNode(x);// The creation weight is x The new node , Use custom functions newNode; 
		return ;
	}
	if( By the properties of binary trees ,x It should be inserted in the left subtree ){
		insert(root->lchild,x);// Recursive ; 
	}else {
		insert(root->rchild,x);
	}
}

The establishment of binary tree ：
 

// The creation of binary tree 
node* Create(int data[ ],int n){
	node* root=NULL;
	for(int i=0;i<n;i++){
		insert(root,data[i]);
	}
	return root;// Return the address of the root node ; 
} 

// Traversal of binary tree ：
The traversal of binary tree has 4 Methods , They are the first order , Middle preface , Backward traversal and hierarchical traversal , Among them " First, middle and then refers to the location where the root node traverses ", And the traversal of the left subtree is always in front of the right subtree ; 
The first three use DFS, The latter is to use BFS 
According to the recursive definition of binary tree ： The traversal of the tree can be decomposed into root nodes , The left subtree , Traversal of these three parts of the right subtree ;

Three traversals with depth first search ：

// The first sequence traversal ： The access order is access root -> Enter left subtree -> Enter the right number ; 
void preorder(node* root){//perorder The first sequence traversal ; 
	if(root==NULL){// Recursive boundary , When the tree is empty （ There are no nodes in the tree , The root node is NULL）; 
		return ;
	}
	printf("%d",root->data);
	preorder(root->lchild);
	preorder(root->rchild);
} 

// In the sequence traversal ： Access order: , Left -> root -> Right ;
void inorder(node* root){
	if(root==NULL)return ;
	inorder(root->lchild);
	printf("%d\n",root->data);// The root is the node to operate ; 
	inorder(root->rchild);	
} 

// Subsequent traversal ： Access order: ： Left -> Right -> root ;
void postorder(node* root){
	if(root==NULL)return ;
	postorder(root->lchild);
	postorder(root->rchild);
	printf("%d",root->data);
} 

// You can determine a tree by accessing the order of nodes , Preface （ The first is the root node ） And after that （ The last one is the root node ） Traversal can only determine the root node , Only middle order traversal can separate the left and right subtrees
// The method is ： Confirm the root node from one of the two traversal sequences , Thus traversing the left and right subtrees of the root node from the middle order , Then according to the comparison and ergodic properties, we can find the binary tree ;

Sequence traversal ：

// Sequence traversal （ Breadth first search ）
// Sequence traversal , Start from the root node and traverse layer by layer from top to bottom , The same layer follows the traversal from left to right , From top to bottom , From left to right ;
// This left to right access sequence is like a team , And every time you visit a team leader element, its left and right children will be put into ;

void layerOrder(node* root){
	queue<node*> Q;// Notice the pointer queue , Because the data under this address may need to be modified , So what is needed is node Address , instead of node copy ; 
	Q.push(root);
	while(!Q.empty()){
		node* top=Q.front();
		Q.pop();
		printf("%d",top->data);
		if(top->lchild!=NULL)Q.push(top->lchild);
		if(top->lchild!=NULL)Q.push(top->lchild);
	}
} 
 

// We know how to reconstruct the binary tree by preorder traversal sequence and middle order traversal sequence
// The preorder interval is [preL,preR], Intermediate sequence interval [inL,inR], Return root node address ;
// The main process is to find the root node , Establish root node , Divide the left and right trees , Then find the root node in the left and right trees and create a recursive process ; 

node* create(int preL,int preR,int int inL,int inR){
	if(preL>preR)return NULL;// The subtree has no nodes , Embodied in the sequence is preL>preR; 
	
	node* root=new node;// The root node of a tree or subtree , Open up new space , Return the address of the space ;
	root->data=pre[preL];// The first node of the preorder sequence is the root node ; 
	int k;
	for(k=inL;k<=inR;k++){// Traversal middle order traversal sequence , Find the location of the root node ; 
		if(in[k]==root->data){
			break;
		}
	} 
	// Found the location of the root node , The two sides of the root node traversed by the middle order are the sequence of left and right subtrees ;
	int numleft=k-inL;// The number of nodes in the left subtree ;
	root->lchild=create(preL+1,preL+numleft,inL,k-1); // Traverse left subtree ;
	root->rchild=create(PreL+numleft+1,preR,k+1,inR);
	return root;// Return the root node address ; 
}
 

Middle order traversal sequence can be followed by preorder traversal , Post order traversal and hierarchical traversal sequence to build a unique binary tree , The latter two pairs or three together cannot build a unique binary tree , The reason is that the main function of these three traversals is to provide root nodes , The left and right subtrees must be distinguished by the middle order .

Perfect binary tree ：

① The definition of a complete binary tree ： A complete binary tree is a tree that is completely populated , But the bottom layer may be excluded , The bottom layer is filled from left to right .

② The storage of complete binary tree can be stored by more convenient array besides binary linked list , from 1 Start （ Root subscript ,1 The number must be stored in the root node ）, To n, Subscript is the number of its node , The value is weight .

So there is ： Any node in a complete binary tree is numbered x, Then the left node must be 2x, The number of the right node must be 2x+1

Divide by , The storage order of the elements in the array is exactly the sequence traversal sequence of the complete binary tree .