数据结构13：二叉树及其遍历

摘要： 二叉树是树的特例，即每一个元素最多只能有两个分支。二叉树是十分重要的，一般的树都可以由二叉树转换过去并且一一对应。所以在我们熟练掌握二叉树之后，才能对一般的树进行操作。

今天我们会讲到二叉树的深度遍历、用层次遍历录入元素和用层次遍历输出元素。

一.代码块
1）创建

对于二叉树，我们一般都是用链式存储，顺序存储的话会造成很多空间的浪费

#define MAXSIZE 5

//对于二叉树，我们一般都是用链式存储，顺序存储的话会造成很多空间的浪费 
typedef struct BTNode
{
	char element;
	//指向左孩子的指针
	struct BTNode *left;
	//指向右孩子的指针
	struct BTNode *right;
}*BTNodePtr;

这里为了方便我们进行层次遍历，要创建一个循环队列，需要注意的是，这个1队列存储的元素都是一个个指向树结点的地址。

typedef struct BTNodeQueue
{
	
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}*BTNodeQueuePtr;

2）队列的初始化

BTNodeQueuePtr BTNodeQueueInit()
{
	BTNodeQueuePtr resultPtr = (BTNodeQueuePtr)malloc(sizeof(struct BTNodeQueue)); 
	//不要忘记给动态数组malloc哦 
	resultPtr->nodePtrs = (BTNodePtr*)malloc(MAXSIZE * sizeof(struct BTNode));
	 
	
	resultPtr->front = 0;
	resultPtr->rear = 0;
	
	return resultPtr; 
}

3）出队及入队

循环队列的操作等在我前面的文章有着详细的叙述，这里就不赘述了

void enqueue(BTNodeQueuePtr paraQueuePtr,BTNodePtr paraPtr)
{
	if((paraQueuePtr->rear+1) % MAXSIZE == (paraQueuePtr->front) % MAXSIZE)
	{
		printf("队列满了，无法入队n");
		return ;
	}
	
	paraQueuePtr->nodePtrs[paraQueuePtr->rear % MAXSIZE] = paraPtr;
	paraQueuePtr->rear = (paraQueuePtr->rear+1) % MAXSIZE;
}

BTNodePtr dequeue(BTNodeQueuePtr paraQueuePtr)
{
	if(paraQueuePtr->front == paraQueuePtr->rear)
	{
		printf("队列为空，无法出队n");
		return ; 
	}
	BTNodePtr tempPtr = paraQueuePtr->nodePtrs[paraQueuePtr->front % MAXSIZE];
	paraQueuePtr->front = (paraQueuePtr->front+1) % MAXSIZE;
	
	return tempPtr;
}

4）创建树结点

这里是将传入的字符创建为一个树结点，其左孩子和后孩子默认为NULL

BTNodePtr constructNode(char paraChar)
{
	BTNodePtr tempPtr = (BTNodePtr)malloc(sizeof(struct BTNode));
	
	tempPtr->element = paraChar;
	tempPtr->left = NULL;
	tempPtr->right = NULL;
	
	return tempPtr;
}

5）将字符串转化为二叉树

层次遍历很好的运用了队列先进先出，后进后出的性质，读入一个元素，就创建一个树结点，并将其入队。出队一个结点就作为父结点，接下来两个元素分别为其左孩子和右孩子。

BTNodePtr stringToBT(char *paraString)
{
	int i = 0;
	char ch;
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr headerPtr,tempParent,leftChild,rightChild;
	
	ch = paraString[i];
	i ++;
	
	headerPtr = constructNode(ch);
	enqueue(resultQueuePtr,headerPtr);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempParent = dequeue(resultQueuePtr);
		
		//1.下一个字符为左孩子
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->left = NULL;
		} 
		else
		{
			leftChild = constructNode(ch);
			tempParent->left = leftChild;
			enqueue(resultQueuePtr,leftChild);
		}
		
		//2.下一个字符为右孩子 
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->right = NULL;
		} 
		else
		{
			rightChild = constructNode(ch);
			tempParent->right  = rightChild;
			enqueue(resultQueuePtr,rightChild);
		}
	}
	
	return headerPtr;
}

6）层次遍历

用一个字符串记录每个结点的元素，出队一个就记录一个，出队的元素要将其左孩子和右孩子先后入队

void levelwise(BTNodePtr paraHeader)
{
	int i = 0;
	char ch;
	char tempString[100];
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr tempNodePtr;	

	enqueue(resultQueuePtr,paraHeader);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempNodePtr = dequeue(resultQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i++;
		
		if (tempNodePtr->left != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->left);
		}
		
		if (tempNodePtr->right != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->right);
		}
	}
	
	tempString[i] = '';
	printf("%s",tempString);
	
}

7）先序（中左右）遍历

这里用递归实现了先序遍历，用到了系统建的栈 ，所以代码非常的简洁。实际上这三种深度遍历我觉得和之前的的汉诺塔的递归算法有着非常大的相似之处。

void preorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	printf("%c",paraHeader->element);
	preorder(paraHeader->left);
	preorder(paraHeader->right);
}

8）中序（左中右）遍历

void inorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	inorder(paraHeader->left);
	printf("%c",paraHeader->element);
	inorder(paraHeader->right);
}

8）后序（左右中）遍历

void postorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	postorder(paraHeader->left);
	postorder(paraHeader->right);
	printf("%c",paraHeader->element);
}

8）主函数

int main(){
	BTNodePtr tempHeader;
	tempHeader = constructNode('c');
	printf("There is only one node. Preorder visit: ");
	preorder(tempHeader);
	printf("rn");

	char* tempString = "acde#bf######";
	tempHeader = stringToBT(tempString);
	printf("Preorder: ");
	preorder(tempHeader);
	printf("rn");
	printf("Inorder: ");
	inorder(tempHeader);
	printf("rn");
	printf("Postorder: ");
	postorder(tempHeader);
	printf("rn");
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("rn");

	return 0;
}

三.运行结果

There is only one node. Preorder visit: c
Preorder: acedbf
Inorder: ecabdf
Postorder: ecbfda
Levelwise: acdebf

四.全部代码

#include 
#include 
#include 

#define MAXSIZE 5

//对于二叉树，我们一般都是用链式存储，顺序存储的话会造成很多空间的浪费 
typedef struct BTNode
{
	char element;
	struct BTNode *left;
	struct BTNode *right;
}*BTNodePtr;

//这里队列就用的是顺序循环存储啦 
typedef struct BTNodeQueue
{
	
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}*BTNodeQueuePtr;

BTNodeQueuePtr BTNodeQueueInit()
{
	BTNodeQueuePtr resultPtr = (BTNodeQueuePtr)malloc(sizeof(struct BTNodeQueue)); 
	//不要忘记给动态数组malloc哦 
	resultPtr->nodePtrs = (BTNodePtr*)malloc(MAXSIZE * sizeof(struct BTNode));
	 
	
	resultPtr->front = 0;
	resultPtr->rear = 0;
	
	return resultPtr; 
}

BTNodePtr constructNode(char paraChar)
{
	BTNodePtr tempPtr = (BTNodePtr)malloc(sizeof(struct BTNode));
	
	tempPtr->element = paraChar;
	tempPtr->left = NULL;
	tempPtr->right = NULL;
	
	return tempPtr;
}

void enqueue(BTNodeQueuePtr paraQueuePtr,BTNodePtr paraPtr)
{
	if((paraQueuePtr->rear+1) % MAXSIZE == (paraQueuePtr->front) % MAXSIZE)
	{
		printf("队列满了，无法入队n");
		return ;
	}
	
	paraQueuePtr->nodePtrs[paraQueuePtr->rear % MAXSIZE] = paraPtr;
	paraQueuePtr->rear = (paraQueuePtr->rear+1) % MAXSIZE;
}

BTNodePtr dequeue(BTNodeQueuePtr paraQueuePtr)
{
	if(paraQueuePtr->front == paraQueuePtr->rear)
	{
		printf("队列为空，无法出队n");
		return ; 
	}
	BTNodePtr tempPtr = paraQueuePtr->nodePtrs[paraQueuePtr->front % MAXSIZE];
	paraQueuePtr->front = (paraQueuePtr->front+1) % MAXSIZE;
	
	return tempPtr;
}

BTNodePtr stringToBT(char *paraString)
{
	int i = 0;
	char ch;
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr headerPtr,tempParent,leftChild,rightChild;
	
	ch = paraString[i];
	i ++;
	
	headerPtr = constructNode(ch);
	enqueue(resultQueuePtr,headerPtr);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempParent = dequeue(resultQueuePtr);
		
		//1.下一个字符为左孩子
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->left = NULL;
		} 
		else
		{
			leftChild = constructNode(ch);
			tempParent->left = leftChild;
			enqueue(resultQueuePtr,leftChild);
		}
		
		//2.下一个字符为右孩子 
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->right = NULL;
		} 
		else
		{
			rightChild = constructNode(ch);
			tempParent->right  = rightChild;
			enqueue(resultQueuePtr,rightChild);
		}
	}
	
	return headerPtr;
}

void levelwise(BTNodePtr paraHeader)
{
	int i = 0;
	char ch;
	char tempString[100];
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr tempNodePtr;	

	enqueue(resultQueuePtr,paraHeader);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempNodePtr = dequeue(resultQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i++;
		
		if (tempNodePtr->left != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->left);
		}
		
		if (tempNodePtr->right != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->right);
		}
	}
	
	tempString[i] = '';
	printf("%s",tempString);
	
}

void preorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	printf("%c",paraHeader->element);
	preorder(paraHeader->left);
	preorder(paraHeader->right);
}

void inorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	inorder(paraHeader->left);
	printf("%c",paraHeader->element);
	inorder(paraHeader->right);
}

void postorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	postorder(paraHeader->left);
	postorder(paraHeader->right);
	printf("%c",paraHeader->element);
}

int main(){
	BTNodePtr tempHeader;
	tempHeader = constructNode('c');
	printf("There is only one node. Preorder visit: ");
	preorder(tempHeader);
	printf("rn");

	char* tempString = "acde#bf######";
	tempHeader = stringToBT(tempString);
	printf("Preorder: ");
	preorder(tempHeader);
	printf("rn");
	printf("Inorder: ");
	inorder(tempHeader);
	printf("rn");
	printf("Postorder: ");
	postorder(tempHeader);
	printf("rn");
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("rn");

	return 0;
}