Implementation of Binary Tree Related Algorithms

no_mkd

Preface:

Binary trees are a relatively simple data structure. Understanding and proficiently mastering their related algorithms is greatly beneficial for learning complex data structures.

1. Creating a Binary Tree

[Skip if you don't like theory >>]

The so-called creation of a binary tree is essentially having the computer store this special data structure (special in what way? Special in that it's our own custom definition).

First, computer internal storage is linear, while our tree structure is hierarchical. Computers obviously cannot understand this. The original data types that computers can accept cannot meet our needs.

Therefore, we have to customize a data structure to represent hierarchical relationships.

Actually, we need to define structure + operations. The structure serves the operations. For example, if we want to simulate a ticket purchasing process and existing data structures cannot meet our needs (don't mention arrays...), the operations we might need are:

1. Get the person at the front of the ticket queue; 2. Remove the person who has bought a ticket from the queue; 3. After the first person buys a ticket, everyone behind them should "consciously" move forward.

After clarifying these three operations, we define the structure based on the operations, and finally we get a queue (array/linked list + corresponding functions).

Binary trees are the same. What the computer sees is structure + operations. The structure is a Node collection (binary linked list), and the operations are functions for creation, traversal, search, etc.

Node:

struct bt
{
	char data;
	struct bt *left;
	struct bt *right;
};

A node is like a bucket with two hands (the bucket holds data, the two hands reach out to grab left and right children).

Operations:

//createBT();
//printBT();
//deleteNode(Node node);
//...

-Above is the understanding of binary trees, below is the specific implementation of creating a binary tree-

The binary tree creation process is actually a traversal process (here referring to recursive method). We know that any traversal method of a binary tree can linearize the tree structure (simply put, a set of traversal results can uniquely represent a binary tree). Therefore, we can restore a binary tree based on traversal results.

Specific approach for recursive tree building with preorder traversal:

1. Read the data of the current root node; 2. If it's a space, set the current root to NULL, otherwise allocate a new node and store the data; 3. Recursively call using the left and right pointers of the current root node to create left and right subtrees.

The language description might be hard to understand. Here's the code:

struct bt
{
	char data;
	struct bt *left;
	struct bt *right;
};
void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;//If space, set to NULL
else
{
*root=(struct bt *)malloc(sizeof(struct bt));//Allocate new node
(*root)->data=c;//Store data
createBT(&((*root)->left));//Build left subtree of current node
createBT(&((*root)->right));//Build right subtree of current node
}
}

For example, if we want to build a binary tree a(b, c), we just need to input its preorder traversal result ab××c×× (× represents space). The other two tree-building methods are similar and won't be described in detail. As for non-recursive tree-building methods, see the non-recursive traversal below; they're very similar.

2. Traversal

Traversal has two implementation methods: recursive and non-recursive. The so-called non-recursive is actually converted from recursive (manually maintaining a stack). In terms of overhead (memory/time), non-recursive might be better, after all, the OS stack maintains more information, and the overhead of saving and restoring context is greater.

In terms of traversal order, there are 3 methods: 1. Preorder traversal (root-left-right); 2. Inorder traversal (left-root-right); 3. Postorder traversal (left-right-root).

For example, the three traversal results of binary tree a(b, c(d, e)) are: 1. abcde; 2. badce; 3. bdeca.

-Below we'll look at recursive and non-recursive implementations of postorder traversal; the others are similar-

Postorder traversal recursive:

void postOrder(struct bt * root)
{
	if(root == NULL)return;
	else
	{
		postOrder(root->left);
		postOrder(root->right);
		putchar(root->data);
	}
}

Postorder traversal non-recursive:

void postOrder(struct st* root)
{
	struct st* stack[100];//Declare node stack
	int top=-1;//Stack top index
	struct bt* p=root;//Current node (present)
	struct bt* q=NULL;//Previously processed node
	while(p!=NULL||top!=-1)
	{
		for(;p!=NULL;p=p->left)stack[++top]=p;//Traverse left subtree
		if(top!=-1)
		{
			p=stack[top];
			if(p->right==NULL||p->right==q)//No right child, or right child already traversed
			{
				putchar(p->data);//Output root node
				q=p;
				p=stack[top];
				top--;
				p=NULL;
			}
			else p=p->right;//Traverse right subtree
		}
	}
}

To describe more clearly, stack operations are directly implemented above. Of course, a more standardized approach is to encapsulate the stack as an independent data structure and call the operation functions provided by the stack in our functions to perform related operations.

3. Output Leaf Nodes

A series of operations for searching specific nodes are based on traversal. Outputting leaf nodes is an example. Leaf nodes satisfy the condition that both left and right children are NULL. We just need to add such a judgment condition in the traversal.

//Preorder traversal is used here
void printLeaves(struct bt* root)
{
	if(root == NULL)return;
	else
	{
		if(root->left == NULL&&root->right == NULL)putchar(root->data);
		else
		{
			printLeaves(root->left);
			printLeaves(root->right);
		}
	}
}

Similar operations include: outputting nodes in a binary tree that satisfy certain conditions, deleting specified nodes, adding nodes (subtrees) at specified positions... all are additional operations based on traversal.

4. Calculating Tree Depth

There are multiple ways to calculate tree depth, for example: 1. Calculate the height of left and right subtrees under the root separately; the larger one is the tree depth; 2. The maximum recursion depth is the tree depth...

We adopt the first method; it's clearer.

int btDepth(struct bt* root)
{
	int rd,ld;
	if(root==NULL)return 0;//Empty tree depth is 0
	else
	{
		ld=1+btDepth(root->left);//Recursive level increment, depth plus 1
		rd=1+btDepth(root->right);//Recursive level increment, depth plus 1
		return ld > rd ? ld : rd;//Return maximum value
	}
}

5. Tree-Shaped Output

The so-called tree-shaped output means rotating the naturally represented binary tree 90 degrees counterclockwise. Actually, it's still recording the recursion level during traversal to determine the output result.

//depth represents recursion depth, initial value is 0
void btOutput(struct bt* root,int depth)
{
	int k;
	if(root==NULL)return;
	else
	{
		btOutput(root->right,depth+1);//Traverse right subtree
		for(k=0;k<depth;k++)
			printf(" ");//Recursion level determines number of spaces (indentation)
		putchar(root->data);printf("\n");
		btOutput(root->left,depth+1);//Traverse left subtree
	}
}
//The traversal order "right-middle-left" is called "reverse inorder" traversal. This order is adopted to conform to output rules (90 degrees counterclockwise).

6. Indented Output by Level

Indented output by level is like automatic indentation in code editors, indenting level by level from the root node. It can be achieved with slight modifications to the code above.

//k still represents recursion depth, initial value is 0
void indOutput(struct bt* root,int k)
{
	int i;
	if(root!=NULL)
	{
		for(i=1;i<=k;i++)
			putchar(' ');
		putchar(root->data);putchar('\n');
		indOutput(root->left,k+1);
		indOutput(root->right,k+1);
	}
	else return;
}
//The only difference between indented output by level and tree-shaped output is the traversal method; the former is preorder traversal, the latter is reverse inorder traversal.

7. Sequential Output by Level

Sequential output by level appears similar to the two output methods mentioned earlier, but is actually very different. At the very least, we cannot simply apply any traversal process to accomplish this goal. Therefore, we must maintain a queue to control traversal order.

void layerPrint(struct bt* root)
{
	struct bt* queue[100];//Declare node queue
	struct bt* p;//Current node
	int amount=0,head,tail,j,k;//Queue related attributes (element count, head, tail index)
	queue[0]=root;
	head=0;
	tail=1;
	amount++;
	while(1)
	{
		j=0;
		for(k=0;k<amount;k++)
		{
			p=queue[head++];//Get head element
			if(p->left!=NULL)
			{
				queue[tail++]=p->left;//Record left child if exists
				j++;
			}
			if(p->right!=NULL)
			{
				queue[tail++]=p->right;//Record right child if exists
				j++;
			}
			putchar(p->data);//Output current node value
		}
		amount=j;//Update counter
		if(amount==0)break;
	}
}

8. Calculating Path from Root to Specified Node

To record paths, the recursive method is naturally not suitable. Here we adopt the non-recursive implementation of postorder traversal. Why choose postorder traversal?

Because in this traversal method, the nodes existing in the stack at any moment happen to be the path from the root node to the current node (from stack bottom to stack top). Strictly speaking, a queue should be used to save the path at this point, because the stack doesn't support pop operations from bottom to top (let's ignore such small details...).

//Parameter c is the specified node value
void printPath(struct bt* root,char c)
{
	struct st* stack[100];//Declare node stack
	int top=-1;//Stack top index
	int i;
	struct bt* p=root;//Current node
	struct bt* q=NULL;//Previously processed node
	while(p!=NULL||top!=-1)
	{
		for(;p!=NULL;p=p->left)stack[++top]=p;//Traverse left subtree
		if(top!=-1)
		{
			p=stack[top];//Get stack top element
			if(p->right==NULL||p->right==q)//If current node has no right child or right child was just visited
			{
				if(p->data==c)//If found, output path
				{
					for(i=0;i<=top;i++)
					{
						p=stack[i];
						putchar(p->data);
					}
					printf("\n");
					//Don't break out of loop here, because there may be non-unique node values; traverse the entire tree to find all paths
				}
				q=p;
				p=stack[top];
				top--;
				p=NULL;
			}
			else p=p->right;//Traverse right subtree
		}
	}
}

9. Complete Source Code and Screenshot Examples

Source code:

#include<stdio.h>
struct bt
{
char data;
struct bt *left;
struct bt *right;
};
void createBT(struct bt ** root)
{
char c;
c=getchar();
if(c == ' ')*root=NULL;
else
{
*root=(struct bt *)malloc(sizeof(struct bt));
(*root)->data=c;
createBT(&((*root)->left));
createBT(&((*root)->right));
}
}
void preOrder(struct bt * root)
{
if(root == NULL)return;
else
{
putchar(root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(struct bt * root)
{
if(root == NULL)return;
else
{
inOrder(root->left);
putchar(root->data);
inOrder(root->right);
}
}
void printLeaves(struct bt* root)
{
if(root == NULL)return;
else
{
if(root->left == NULL&&root->right == NULL)putchar(root->data);
else
{
printLeaves(root->left);
printLeaves(root->right);
}
}
}
int btDepth(struct bt* root)
{
int rd,ld;
if(root==NULL)return 0;
else
{
ld=1+btDepth(root->left);
rd=1+btDepth(root->right);
return ld > rd ? ld : rd;
}
}
void btOutput(struct bt* root,int depth)
{
int k;
if(root==NULL)return;
else
{
btOutput(root->right,depth+1);
for(k=0;k<depth;k++)
printf(" ");
putchar(root->data);printf("\n");
btOutput(root->left,depth+1);
}
}
void postOrder(struct st* root)
{
struct st* stack[100];
int top=-1;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
putchar(p->data);
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}
void printPath(struct bt* root,char c)
{
struct st* stack[100];
int top=-1;
int i;
struct bt* p=root;
struct bt* q=NULL;
while(p!=NULL||top!=-1)
{
for(;p!=NULL;p=p->left)stack[++top]=p;
if(top!=-1)
{
p=stack[top];
if(p->right==NULL||p->right==q)
{
if(p->data==c)
{
for(i=0;i<=top;i++)
{
p=stack[i];
putchar(p->data);
}
printf("\n");
}
q=p;
p=stack[top];
top--;
p=NULL;
}
else p=p->right;
}
}
}
void layerPrint(struct bt* root)
{
struct bt* queue[100];
struct bt* p;
int amount=0,head,tail,j,k;
queue[0]=root;
head=0;
tail=1;
amount++;
while(1)
{
j=0;
for(k=0;k<amount;k++)
{
p=queue[head++];
if(p->left!=NULL)
{
queue[tail++]=p->left;
j++;
}
if(p->right!=NULL)
{
queue[tail++]=p->right;
j++;
}
putchar(p->data);
}
amount=j;
if(amount==0)break;
}
}
void indOutput(struct bt* root,int k)
{
int i;
if(root!=NULL)
{
for(i=1;i<=k;i++)
putchar(' ');
putchar(root->data);putchar('\n');
indOutput(root->left,k+1);
indOutput(root->right,k+1);
}
else return;
}
void main()
{
char c;
struct bt * root;
printf("Please enter preorder traversal result: ");
createBT(&root);
printf("Preorder traversal(preOrder)[recursive]: \n");
preOrder(root);
printf("\nInorder traversal(inOrder)[recursive]: \n");
inOrder(root);
printf("\nPostorder traversal(postOrder)[non-recursive]: \n");
postOrder(root);
printf("\nLeaf nodes(leaves): \n");
printLeaves(root);
printf("\nDepth(depth): \n");
printf("%d\n",btDepth(root));
printf("Tree output(tree output): \n");
btOutput(root,0);
printf("Indentation output(indentation output): \n");
indOutput(root,0);
printf("Please enter target node(target node): ");
getchar();
c=getchar();
printf("Path(path): \n");
printPath(root,c);
printf("Layer output(layerPrint): \n");
layerPrint(root);
printf("\n");
}

Screenshot examples:

A relatively complex binary tree:

Its preorder traversal result is: ABD××EG×××C×FH××I×× (× represents empty; replace × with spaces when inputting)

Change D to H and try again (there are duplicate elements now; there should be two paths to H)