Trees and binary trees: traversal of binary trees

Trees and binary trees ： Traversal of binary tree

The concept of binary tree traversal

Traversal of binary tree It refers to accessing all nodes in the tree in a certain order , also Each node is accessed only once The process of

Traversal is the most basic operation of binary tree , It is the basis of other operations in binary tree

Composition of binary tree ：


1. Preorder traversal process

The first sequence traversal NLR The process of binary tree is ：

• Access the root node ;
• The order traverses the left subtree ;
• The order traverses the right subtree ;

Binary tree preorder traversal demonstration

First, we traverse the sequence ：

A B D G C E F ( Traversal complete )

The first node of the preorder sequence is the root node

2. Middle order traversal process

In the sequence traversal LNR The process of binary tree is ：

• The middle order traverses the left subtree ;
• Access the root node ;
• The middle order traverses the right subtree ;

Binary tree in order to traverse the demonstration

Middle order traversal sequence ：

D G B A E C F ( Traversal complete )

To the left of the root node of the middle order sequence is the node of the left subtree , On the right is the node of the right subtree

3. Post order traversal process

After the sequence traversal LRN The process of binary tree is ：

• The latter traverses the left subtree ;
• The latter traverses the right subtree ;
• Access the root node ;

Binary tree post order traversal demonstration

Post traversal sequence ：

G D B E F C A ( Traversal complete )

The last node in the subsequent sequence is the root node

Example ： If a binary tree's pre order sequence and post order sequence are just opposite . What is the form of the binary tree ？

Binary tree traversal recursive algorithm

From the three traversal processes of binary tree, we get 3 A recursive algorithm

Recursive algorithm of preorder traversal ：

void PreOrder(BTNode *b) {
    
	if(b!=NULL) {
    
		printf("%c",b->data); // Access the root node 
		PreOrder(b->lchild);
		PreOrder(b->rchild);
	}
}

appeal visit Is the direct output node value . actually , The access node can perform various operations on the node , Such as counting , Delete nodes, etc

Recursive algorithm of middle order traversal ：

void InOrder(BTNode *b) {
    
	if(b!=NULL) {
    
		InOrder(b->lchild);
		printf("%c",b->data); // Access the root node 
		InOrder(b->rchild);
	}
}

Recursive algorithm for post order traversal ：

void PostOrder(BTNode *b) {
    
	if(b!=NULL) {
    
		PostOrder(b->lchild);
		PostOrder(b->rchild);
		printf("%c",b->data); // Access the root node 
	}
}

Hierarchical traversal algorithm

Hierarchical traversal process ：

For a binary tree , Start at the root node , Press from top to bottom , Access each node from left to right , Each node is accessed only once

Algorithm design ideas ： Use a queue

1. Queue the root node ;
2. The team does not have a space-time cycle ： Dequeue a node from the queue *p, Visit it ;
   （1） If it has a left child node , Join the left child node in the team
   （2） If it has a right child node , Join the right child node in the team

The corresponding algorithm is as follows ：

void LevelOrder(BTNode *b) {
    
	BTNode *p;
	BTNode *qu[MaxSize]; // Define ring queue , Store the node pointer 
	int front,rear; // Define the head and tail pointers 
	front=rear=0; // Leave the queue empty 
	rear++;
	qu[rear]=b; // The root node pointer enters the queue 
	while(front!=rear) {
     // The queue is not empty loop 
		front=(front+1)%MaxSize;
		p=qu[front]; // Team leader out of line 
		printf("%c",p->data); // Access to the node 
		if(p->lchild!=NULL) {
     // When you have a left child, put it in the team 
			rear=(rear+1)%MaxSize;
			qu[rear]=p->lchild;
		}
		if(p->rchild!=NULL) {
     // When you have a right child, put it in the team 
			rear=(rear+1)%MaxSize;
			qu[rear]=p->rchild;
		}
	}
}

The time complexity of the algorithm is O(n)