Binary Tree and Traversal

📝📓 record binary tree and trevsersal

Introduction

Tree represents the nodes connected by edges. We will discuss binary tree or binary search tree specifically.

Binary Tree is a special data structure used for data storage purpose. A binary tree has s a special condition that each node can have a maximum of two children. A binary tree has the benefits of both an ordered arrat and a linked list as search is is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

We first define a tree struct as follows:

struct Node{
	int data;
	struct Node * left_child;
	struct Node * right_child;
};

struct Tree{
	struct Node * root;
};

binary_tree

1. build a binary tree(recursion)

Creating a binary tree can be implemented by insertion operation, also, two conditions can be followed as: building a normal binary tree or building a binary search tree, and we only talk about normal binary tree. When constructing a normal binary tree, we need a principle that can locate the position node to be inserted, here, we usually use Pre-Order traversal to complete the insertion operation.

pseudocode in C:

struct Node * construct_tree(struct Node * node){
	int data;
	printf("please input the data: ");
	scanf("%d", &data);
	if(data == -1)
		return NULL;
	else{
		node = (struct Node *)malloc(sizeof(struct Node));
		node->data = data;
		node->left_child = construct_tree(node->left_child);
		node->right_child = construct_tree(node->right_child);
	}
	return node;

void construct(struct Tree * t){
	t->root = construct_tree(t->root);
}

2. Pre-Order traversal(recursion)

traverse the root node of a binary tree first, then left child node and right child node at last.

pseudocode in C:

void pre(struct Node * node){
	if(node != NULL){
		printf("%d ", node->data);
		pre(node->left_child);
		pre(node->right_child);
	}
}

void pre_order(struct Tree *){
	pre(t->root);
}

3. In-Order traversal(recursion)

traverse the left child node of a binary tree first, then root node and right child node at last.

pseudocode in C：

void in(struct Node * node){
	if(node != NULL){
		in(node->left_child);
		printf("%d ", node->data);
		in(node->right_child);
	}
}

void in_order(struct Tree * t){
	in(t->root);
}

4. Post_Order traversal(recursion)

traverse the left child node of a binary tree first, then right child node and root node at last.

pseudocode in C:

void post(struct Node * node){
	i(node != NULL){
		post(node->left_child);
		post(node->right_child);
		printf("%d ", node->data);
	}
}

void post_order(struct Tree * t){
	post(t->root);
}

5. level traversal(using Queue)

traverse a binary tree level by level, we can store the nodes those have benn visited with the help of Queue structure. In able to implement the queue efficiently, we use Circle Queue

first, define a Queue, code in C:

#define MAX_QUEUE 20
struct Queue{
	struct Node **base;
	int front;
	int rear;
};

bool isEmpty(struct Queue * q){
	if(q->front == q->rear)
		return true;
	else
		return false;
}

bool isFull(struct Queue * q){
	if((q->rear + 1) / MAX_QUEUE == q->front)		return true;
	else
		return false;
}	

void enqueue(struct Queue * q, struct Node * node){
	if(isFull(q))
		return;
	else{
		if(isEmpty(q))
			q->base[q->rear] = node;
		else{
			q->rear = (q->rear + 1) / MAX_QUEUE;
			q->base[q->rear] = node;
		}
	}
}

struct Node * dequeue(struct Queue * q){
	if(!isEmpty(q)){
		struct Node * tmp = q->base[q->front];
		q->front = (q->front + 1) / MAX_QUEUE;
		return tmp;
	}
	else
		exit(-1);
}

next, we can implement the level traversal

void level_traverse(struct Tree * t){
	struct Queue * q = (struct Queue *)malloc(siezof(struct Queue));
	q->base = (struct Node **)malloc(sizeof(struct Node *));
	q->front = 0;
	q->rear = 0;
	enqueue(q, t->root);
	struct Node * tmp;
	while(!isEmpty(q)){
		tmp = dequeue(q);
		printf("%d ", tmp->data);
		if(tmp->left_child)
		
			enqueue(q, tmp->left_child);
		if(tmp->right_child)
			enqueue(q, tmp->right_child);
	}
}

Non-recursion traversal(using Stack)

1. Pre-Order traversal

the procedure of algorithms:

push the root node to stack;
if the stack is not empty, pop the top element of stack;
(1) push it's right child node to stack if exists;
(2) push it's left child node to stack if exists;
repeat step 2 until stack is empty

pseudocode in C:

void pre_order(struct Tree * tree){
	struct Stack * stack = (struct Stack *)malloc(sizeof(struct Stack));
	init_stack(stack);
	push(stack, tree->root);
	struct Node * tmp;
	while(!isEmpty(stack)){
		tmp = pop(stack);
		printf("%d ", tmp->data);
		if(tmp->right_child)
			push(stack, tmp->right_child);
		if(tmp->left_child)
			push(stack, tmp->left_child);
	}
	printf("\n");
}

2. Post_Order traversal

push the root node to stack;
if the stack is not empty, get the top element of stack(not pop);
(1) if it's left child node has been visited or null and right child node has been visited or null, pop the top element of stack and print.
(2) if it's right child node is not null and unvisited, push it into the stack and set it as visited;
(3) if it's left child node is not null and unvisited, push it into the stack and set it as visited;
repeat step 2 until stack is empty

pseudocode in C:

void post_order(struct Tree * tree){
	struct Stack * stack = (struct Stack *)malloc(sizeof(struct Stack));
	init_stack(stack);
	struct Node * tmp;
	push(stack ,tree->root);
	while(!isEmpty(stack)){
		tmp = get_top(stack);
		if(tmp->left_child == NULL || tmp->left_child->visited == 1) && (tmp->right_child == NULL || tmp->right->visited == 1){
			tmp = pop(stack);
			printf("%d ", tmp->data);
		}
		if(tmp->right_child && tmp->right_child->visited == 0){
			push(stack, tmp->right_child);
			tmp->right_child->visited = 1;
		}
		if(tmp->left_child && tmp->left_child->visited == 0){
			push(stack, tmp->left_child);
			tmp->left_child->visited = 1;
		}
	}
	printf("\n");
}

3. In-Order traversal

set it'visited equals to 1 push the root node to stack;
if the stack is not empty, get the top element of stack(not pop)
(1) if it's visited equals to 2, pop the top element of stack and print. continue
(2) if it's left child and right child are all null, pop the top element of tack and print; continue

(3) pop itself from top of stack;
(4) if it's right child node is not null, set visited as 1 and push it into stack;
(5) set visited as 2 push itself into stack;
(6) if it's left child node is not null, set visited as 1 push it into stack;
repeat step 2 until stack is empty

pseudocode in C:

void in_order(struct Tree * tree){
	struct Stack * stack = (struct Stack *)malloc(sizeof(struct Stack));
	init_stack(stack);
	tree->root->visited = 1;
	push(stack, tree->root);
	struct Node * tmp
	while(!isEmpty(stack)){
		tmp = get(stack);
		if(tmp->visited == 2){
			tmp = pop(stack);
			printf("%d ", tmp->data);
			continue;
		}
		if(tmp->left_child == NULL && tmp->right_child == NULL){
			tmp = pop(stack);
			printf("%d ", tmp->data);
			continue;
		}
		tmp = pop(stack);
		if(tmp->right_child){
			tmp->right_child->visited = 1;
			push(stack, tmp->right_child);
		}
		tmp->visited = 2;
		push(stack, tmp);
		if(tmp->left_child){
			tmp->left_child->visited = 1;
			push(stack, tmp->left_child);
		}
	}
	printf("\n");
}

blog