一、二叉树的实现

二叉树是计算机一个重要的结构，许多复杂算法都是由二叉树演变而来，其具有的性质和树相类似，但注意：二叉树和树不是同一个概念，他的孩子有左右之分。在二叉树的代码实现中，可以利用栈来实现，递归可以快速地生成二叉树，并且代码较简洁，但许多公司的面试题会考到二叉树的非递归实现方法，下面我用栈这个数据结构实现二叉树的构建，先序、中序、后序遍历以及销毁。这里需要C语言的指针掌握。

二、二叉树利用到的数据结构：

1.二叉树数据结构：

typedef struct TNode
{
	ElemType data;  //数据域
	struct TNode *lchild;  //左孩子指针
	struct TNode *rchild;  //右孩子指针
}BinaryTree,*BiTreePoint;

2.链栈数据结构：

typedef struct SNode
{
	BiTreePoint *data;
	struct SNode *next;
}StackNode,*StackPoint; //栈结点数据结构，注意这里的数据域我们用到一个二维指针，用来保存二叉树的结点指针

typedef struct
{
	int StackSize;
	StackPoint base;
	StackPoint top;
}StackHead,*StackHeadPoint; //栈头信息数据结构

3.队列数据结构：

typedef struct QNode
{
	BiTreePoint *data;
	struct QNode *next;
}QueueNode,*QueuePoint;

typedef struct
{
	int QueueSize;
	QueuePoint front;
	QueuePoint rear;
}QueueHead,*QueueHeadPoint;

三、二叉树的方法

1.二叉树的构建：

这里我们利用栈的数据结构先序构造二叉树，使用时注意指针的传递

BiTreePoint CreatBiTree()  //非递归先序构造二叉树
{
	BiTreePoint *temp,T;
	ElemType ch;
	StackHeadPoint Head=InitStack();
	temp=&T;
	do
	{
		ch=getchar();
		getchar();
		if(ch=='^')
			(*temp)=NULL;
		else
		{
			(*temp)=(BiTreePoint)malloc(sizeof(BinaryTree));
			if(*temp==NULL)
			{
				printf("对不起,系统内存不足,子树构造失败,请扩容!\n");
				system("pause");
			}
			(*temp)->data=ch;
			StackPush(&Head,&(*temp)->rchild);
			StackPush(&Head,&(*temp)->lchild);
		}
		temp=getTop(&Head);
	}while(!StackEmpty(Head) && StackPop(&Head));
	StackDelete(&Head);
	return T;
}

2.二叉树的遍历：

其中，先序遍历和中序遍历结构较为类似，而后序遍历则比较难操作，以下采用两种方法。当然，方法不一，网上还有另解。后序遍历方法1则是利用一个标记flag，代码逻辑如下：

if Point!=NULL ^ Point not visit
	visit Point.left;
else
	if Point is Point.parent.left
		Point=Point.parent.right;
	else
		do:
			Point=stack.pop;
			visit Point;
		loop until Point is Point.parent.left;

而后序遍历的方法2则是每次把孩子指针进栈，用一个before指针记录之前操作完的结点，即可以将它理解为前一步操作完的子树的根(root)，每次什么时候可以输出呢？即你发现叶子结点，或者你发现栈顶结点的所有孩子结点操作完之后。接着按层遍历使用到队列，先进先出的特性就可以一层一层地扫描二叉树。

Status PreOrderTraverse(BiTreePoint T) //非递归先序遍历方法
{
	BiTreePoint *temp;
	StackHeadPoint Head=InitStack();
	temp=&T;
	while(*temp || !StackEmpty(Head))
	{
		if(*temp)
		{
			printf("%c",(*temp)->data);
			if(!StackPush(&Head,temp))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
			temp=&(*temp)->lchild;
		}
		else
		{
			temp=getTop(&Head);
			StackPop(&Head);
			temp=&(*temp)->rchild;
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status InOrderTraverse(BiTreePoint T) //非递归中序遍历方法
{
	BiTreePoint *temp;
	StackHeadPoint Head=InitStack();
	temp=&T;
	while(*temp || !StackEmpty(Head))
	{
		if(*temp)
		{
			if(!StackPush(&Head,temp))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
			temp=&(*temp)->lchild;
		}
		else
		{
   			temp=getTop(&Head);
			printf("%c",(*temp)->data);
  			StackPop(&Head);
			temp=&(*temp)->rchild;
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status PostOrderTraverse(BiTreePoint T)  //非递归后序遍历方法
{
	BiTreePoint *temp;
	Status flag=1;
	StackHeadPoint Head=InitStack();
	if(T==NULL || !StackPush(&Head,&T))
	{
		printf("\n");
		return OK;
	}
	temp=&T->lchild;
	while(!StackEmpty(Head))
	{
		if(*temp && flag)
		{
  			if(!StackPush(&Head,temp))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
			temp=&(*temp)->lchild;
		}
		else if(temp==&(*(getTop(&Head)))->lchild)
		{
			temp=&(*(getTop(&Head)))->rchild;
			flag=1;
		}
		else
		{
			temp=getTop(&Head);
			StackPop(&Head);
			printf("%c",(*temp)->data);
			while(temp!=&T && temp==&(*(getTop(&Head)))->rchild)
			{
				temp=getTop(&Head);
				StackPop(&Head);
				printf("%c",(*temp)->data);
			}
			flag=0;
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status PostOrderTraverse2(BiTreePoint T) //非递归后序遍历方法2
{
	BiTreePoint *temp,*before;
	StackHeadPoint Head=InitStack();
	if(T==NULL || !StackPush(&Head,&T))
	{
		printf("\n");
		return OK;
	}
	before=NULL;
	while(!StackEmpty(Head))
	{
		temp=getTop(&Head);
		if( (*temp)->lchild==NULL && (*temp)->rchild==NULL || before && (before==&(*temp)->lchild || before==&(*temp)->rchild) )
		{
			printf("%c",(*temp)->data);
			StackPop(&Head);
			before=temp;
		}
		else
		{
			if((*temp)->rchild)
			{
				if(!StackPush(&Head,&(*temp)->rchild))
				{
					printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
					return NO;
				}
			}
			if((*temp)->lchild)
			{
				if(!StackPush(&Head,&(*temp)->lchild))
				{
					printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
					return NO;
				}
			}
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status LevelOrderTraverse(BiTreePoint T) //按层遍历方法
{
	BiTreePoint *temp;
	QueueHeadPoint Head=InitQueue();
	if(T==NULL || !QueuePush(&Head,&T))
	{
		printf("\n");
		return OK;
	}
	while(!QueueEmpty(Head))
	{
		temp=getFront(&Head);
		QueuePop(&Head);
		printf("%c",(*temp)->data);
		if((*temp)->lchild)
		{
			if(!QueuePush(&Head,&(*temp)->lchild))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
					return NO;
			}
		}
		if((*temp)->rchild)
		{
			if(!QueuePush(&Head,&(*temp)->rchild))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
		}
	}
	QueueDelete(&Head);
	printf("\n");
	return OK;
}

具体实现代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<windows.h>

//******宏定义参数******
#define NO 0
#define OK 1
#define EORRO 0

//******定义数据类型别名******
typedef char ElemType;
typedef int Status;

//******声明数据结构******
typedef struct TNode
{
	ElemType data;
	struct TNode *lchild;
	struct TNode *rchild;
}BinaryTree,*BiTreePoint;

typedef struct SNode
{
	BiTreePoint *data;
	struct SNode *next;
}StackNode,*StackPoint;

typedef struct
{
	int StackSize;
	StackPoint base;
	StackPoint top;
}StackHead,*StackHeadPoint;

typedef struct QNode
{
	BiTreePoint *data;
	struct QNode *next;
}QueueNode,*QueuePoint;

typedef struct
{
	int QueueSize;
	QueuePoint front;
	QueuePoint rear;
}QueueHead,*QueueHeadPoint;

//******以下为链栈的数据结构操作******
StackHeadPoint InitStack()
{
	StackHeadPoint Head=(StackHeadPoint)malloc(sizeof(StackHead));
	Head->StackSize=0;
	Head->base=Head->top=(StackPoint)malloc(sizeof(StackNode));
	return Head;
}

Status StackEmpty(StackHeadPoint Head)
{
	if(Head->base == Head->top)
		return OK;
	return NO;
}

BiTreePoint* getTop(StackHeadPoint *Head)
{
	if(StackEmpty(*Head))
		return NULL;
	return (*Head)->top->next->data;
}

Status StackPush(StackHeadPoint *Head,BiTreePoint *data)
{
	StackPoint p=(StackPoint)malloc(sizeof(StackNode));
	if(p==NULL)
	{
		printf("对不起，系统内存不足!入栈失败!\n");
		return NO;
	}
	(*Head)->top->data=data;
	p->next=(*Head)->top;
	(*Head)->top=p;
	(*Head)->StackSize++;
	return OK;
}

Status StackPop(StackHeadPoint *Head)
{
	StackPoint p=(*Head)->top;
	if(StackEmpty(*Head))
		return NO;
	(*Head)->top=p->next;
	(*Head)->StackSize--;
	free(p);
	return OK;
}

Status StackDelete(StackHeadPoint *Head)
{
	while(!StackEmpty(*Head))
		StackPop(Head);
	free((*Head)->base);
	return OK;
}
//******以上为链栈数据结构操作******

//******以下为链队列数据结构操作******
QueueHeadPoint InitQueue()
{
	QueueHeadPoint Head=(QueueHeadPoint)malloc(sizeof(QueueHead));
	Head->QueueSize=0;
	Head->front=Head->rear=(QueuePoint)malloc(sizeof(QueueNode));
	Head->rear->next=NULL;
	return Head;
}

Status QueueEmpty(QueueHeadPoint Head)
{
	if(Head->front == Head->rear)
		return OK;
	return NO;
}

BiTreePoint* getFront(QueueHeadPoint *Head)
{
	if(QueueEmpty(*Head))
		return NULL;
	return (*Head)->front->next->data;
}

Status QueuePush(QueueHeadPoint *Head,BiTreePoint *data)
{
	QueuePoint p=(QueuePoint)malloc(sizeof(QueueNode));
	if(p==NULL)
	{
		printf("对不起，系统内存不足!入栈失败!\n");
		return NO;
	}
	p->data=data;
	p->next=(*Head)->rear->next;
	(*Head)->rear->next=p;
	(*Head)->rear=p;
	(*Head)->QueueSize++;
	return OK;
}

Status QueuePop(QueueHeadPoint *Head)
{
	QueuePoint p=(*Head)->front;
	if(QueueEmpty(*Head))
		return NO;
	(*Head)->front=p->next;
	(*Head)->QueueSize--;
	free(p);
	return OK;
}

Status QueueDelete(QueueHeadPoint *Head)
{
	while(!QueueEmpty(*Head))
		QueuePop(Head);
	free((*Head)->front);
	return OK;
}
//******以上为链队列数据结构操作******

//******以下为二叉树数据结构操作******
BiTreePoint InitBiTree()
{
	return NULL;
}

Status BiTreeEmpty(BiTreePoint T)
{
	if(T==NULL)
		return OK;
	return NO;
}

void DestroyBiTree(BiTreePoint* T) //非递归销毁二叉树
{
	StackHeadPoint Head=InitStack();
	BiTreePoint *temp;
	if(BiTreeEmpty(*T))
	{
		printf("该二叉树已空!\n");
		return ;
	}
	StackPush(&Head,T);
	while(!StackEmpty(Head))
	{
		temp=getTop(&Head);
		StackPop(&Head);
		if(!BiTreeEmpty((*temp)->lchild)) StackPush(&Head,&(*temp)->lchild);
		if(!BiTreeEmpty((*temp)->rchild)) StackPush(&Head,&(*temp)->rchild);
		free(*temp);
	}
	StackDelete(&Head);
	return ;
}

BiTreePoint CreatBiTree()  //非递归先序构造二叉树
{
	BiTreePoint *temp,T;
	ElemType ch;
	StackHeadPoint Head=InitStack();
	temp=&T;
	do
	{
		ch=getchar();
		getchar();
		if(ch=='^')
			(*temp)=NULL;
		else
		{
			(*temp)=(BiTreePoint)malloc(sizeof(BinaryTree));
			if(*temp==NULL)
			{
				printf("对不起,系统内存不足,子树构造失败,请扩容!\n");
				system("pause");
			}
			(*temp)->data=ch;
			StackPush(&Head,&(*temp)->rchild);
			StackPush(&Head,&(*temp)->lchild);
		}
		temp=getTop(&Head);
	}while(!StackEmpty(Head) && StackPop(&Head));
	StackDelete(&Head);
	return T;
}

Status PreOrderTraverse(BiTreePoint T) //非递归先序遍历方法
{
	BiTreePoint *temp;
	StackHeadPoint Head=InitStack();
	temp=&T;
	while(*temp || !StackEmpty(Head))
	{
		if(*temp)
		{
			printf("%c",(*temp)->data);
			if(!StackPush(&Head,temp))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
			temp=&(*temp)->lchild;
		}
		else
		{
			temp=getTop(&Head);
			StackPop(&Head);
			temp=&(*temp)->rchild;
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status InOrderTraverse(BiTreePoint T) //非递归中序遍历方法
{
	BiTreePoint *temp;
	StackHeadPoint Head=InitStack();
	temp=&T;
	while(*temp || !StackEmpty(Head))
	{
		if(*temp)
		{
			if(!StackPush(&Head,temp))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
			temp=&(*temp)->lchild;
		}
		else
		{
   			temp=getTop(&Head);
			printf("%c",(*temp)->data);
  			StackPop(&Head);
			temp=&(*temp)->rchild;
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status PostOrderTraverse(BiTreePoint T)  //非递归后序遍历方法
{
	BiTreePoint *temp;
	Status flag=1;
	StackHeadPoint Head=InitStack();
	if(T==NULL || !StackPush(&Head,&T))
	{
		printf("\n");
		return OK;
	}
	temp=&T->lchild;
	while(!StackEmpty(Head))
	{
		if(*temp && flag)
		{
  			if(!StackPush(&Head,temp))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
			temp=&(*temp)->lchild;
		}
		else if(temp==&(*(getTop(&Head)))->lchild)
		{
			temp=&(*(getTop(&Head)))->rchild;
			flag=1;
		}
		else
		{
			temp=getTop(&Head);
			StackPop(&Head);
			printf("%c",(*temp)->data);
			while(temp!=&T && temp==&(*(getTop(&Head)))->rchild)
			{
				temp=getTop(&Head);
				StackPop(&Head);
				printf("%c",(*temp)->data);
			}
			flag=0;
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status PostOrderTraverse2(BiTreePoint T) //非递归后序遍历方法2
{
	BiTreePoint *temp,*before;
	StackHeadPoint Head=InitStack();
	if(T==NULL || !StackPush(&Head,&T))
	{
		printf("\n");
		return OK;
	}
	before=NULL;
	while(!StackEmpty(Head))
	{
		temp=getTop(&Head);
		if( (*temp)->lchild==NULL && (*temp)->rchild==NULL || before && (before==&(*temp)->lchild || before==&(*temp)->rchild) )
		{
			printf("%c",(*temp)->data);
			StackPop(&Head);
			before=temp;
		}
		else
		{
			if((*temp)->rchild)
			{
				if(!StackPush(&Head,&(*temp)->rchild))
				{
					printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
					return NO;
				}
			}
			if((*temp)->lchild)
			{
				if(!StackPush(&Head,&(*temp)->lchild))
				{
					printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
					return NO;
				}
			}
		}
	}
	StackDelete(&Head);
	printf("\n");
	return OK;
}

Status LevelOrderTraverse(BiTreePoint T) //按层遍历方法
{
	BiTreePoint *temp;
	QueueHeadPoint Head=InitQueue();
	if(T==NULL || !QueuePush(&Head,&T))
	{
		printf("\n");
		return OK;
	}
	while(!QueueEmpty(Head))
	{
		temp=getFront(&Head);
		QueuePop(&Head);
		printf("%c",(*temp)->data);
		if((*temp)->lchild)
		{
			if(!QueuePush(&Head,&(*temp)->lchild))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
					return NO;
			}
		}
		if((*temp)->rchild)
		{
			if(!QueuePush(&Head,&(*temp)->rchild))
			{
				printf("对不起,当前系统内存不足,二叉树遍历失败!\n");
				return NO;
			}
		}
	}
	QueueDelete(&Head);
	printf("\n");
	return OK;
}

//******以上为二叉树数据结构操作******

int main()
{
	BiTreePoint T;
	printf("请先序构建二叉树(^:表示空,换行表示结点一个输入完毕!):\n");
	T=CreatBiTree();
    printf("该树的先序遍历为:\n");
	PreOrderTraverse(T);
	printf("该树的中序遍历为:\n");
	InOrderTraverse(T);
	printf("该树的后序遍历为:\n");
	PostOrderTraverse(T);
	printf("该树的后序序遍历2为:\n");
	PostOrderTraverse2(T);
	printf("该树的按层遍历为:\n");
	LevelOrderTraverse(T);
	DestroyBiTree(&T);
	printf("二叉树销毁成功!\n");
	return 0;
}

总结：

二叉树的C语言实现考察了之前的链表、栈、队列，以及基础的指针方法，在C++的STL中有封装好的类使用。其理论思想是今后深度优先搜索，广度优先搜索，以及图的一些东西的基础。可以利用其实现哈弗曼树、线索二叉树等等。