二叉树，与单链表，栈，队列，差别较大。

二叉树是树的一种。

树：

树是n个节点的有限集，若n=0时，则为空树。

1，树的定义运用了递归算法，树的定义中运用了自身

2，树的根节点没有前驱，除了根节点以外，其他节点只有一个前驱。

3，树的节点可以有0个/多个后驱。

二叉树：

1，一种特殊的树结构

2，每个节点至多有2个子树，左子树和右子树。

遍历方式：

前序，中序，后序的三种遍历方式

1，前序：根->左->右

2，中序：左->根->右

3，后序：左->右->根

实现功能：

1，二叉树的建立

2，二叉树的遍历

实现代码：

建立结构体：

//定义结构体TreeNode
typedef struct TreeNode{
	char data;//数据域
	struct TreeNode* lchild;//指针域 ,左子树 
	struct TreeNode* rchild;//指针域 ,右子树 
}TreeNode; //为结构体起名字TreeNode

1，二叉树的建立：

//建立树，建立过程中需要改变TreeNode里面的值 
//因为需要改变T的值，所以TreeNode *T传入形参，并不能改变T的值，所以应该使用二级指针
//采用递归算法 
void createTree(TreeNode **T,char *m,int *index){//m指针类数组，index为数组索引值 
	char mm;
	mm=m[*index];//给mm赋值字符串 
	*index+=1;//改变索引index的值
	 
	if(mm == '#'){//#时，树的节点为空节点时 
		*T=NULL;// 
	}else{//树的节点 不为空节点时  
		*T =(TreeNode*)malloc(sizeof(TreeNode));//为*T建立空间
		(*T)->data= mm;//给 *T->data 赋值字符串 mm，插入树的一个节点 
		//采用前序，插入树 
		createTree(& ((*T)->lchild),m,index);//采用递归算法 //建立左子树 
		createTree(& ((*T)->rchild),m,index);//采用递归算法 //建立右子树 
	}
}

 2，二叉树的遍历

采用3种方式，前序，中序，后序的三种遍历方式。

//遍历二叉树，并且使用前序法，输出
//采用递归算法 
void preprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		printf("%c ",T->data);//输出，一个节点 
		preprintl(T->lchild);//采用递归算法,输出左子树
		preprintl(T->rchild);//采用递归算法,输出右子树
	}
} 

//遍历二叉树，并且使用中序法，输出
//采用递归算法 
void inprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		inprintl(T->lchild);//采用递归算法,输出左子树
		printf("%c ",T->data);//输出，一个节点 
		inprintl(T->rchild);//采用递归算法,输出右子树
	}
} 

//遍历二叉树，并且使用后序法，输出
//采用递归算法 
void postprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		postprintl(T->lchild);//采用递归算法,输出左子树
		postprintl(T->rchild);//采用递归算法,输出右子树
		printf("%c ",T->data);//输出，一个节点 
	}
} 

总代码：

#include<stdio.h>
#include<stdlib.h>		//开辟空间所需要的头文件 

//定义结构体TreeNode
typedef struct TreeNode{
	char data;//数据域
	struct TreeNode* lchild;//指针域 ,左子树 
	struct TreeNode* rchild;//指针域 ,右子树 
}TreeNode; //为结构体起名字TreeNode

//建立树，建立过程中需要改变TreeNode里面的值 
//因为需要改变T的值，所以TreeNode *T传入形参，并不能改变T的值，所以应该使用二级指针
//采用递归算法 
void createTree(TreeNode **T,char *m,int *index){//m指针类数组，index为数组索引值 
	char mm;
	mm=m[*index];//给mm赋值字符串 
	*index+=1;//改变索引index的值
	 
	if(mm == '#'){//#时，树的节点为空节点时 
		*T=NULL;// 
	}else{//树的节点 不为空节点时  
		*T =(TreeNode*)malloc(sizeof(TreeNode));//为*T建立空间
		(*T)->data= mm;//给 *T->data 赋值字符串 mm，插入树的一个节点 
		//采用前序，插入树 
		createTree(& ((*T)->lchild),m,index);//采用递归算法 //建立左子树 
		createTree(& ((*T)->rchild),m,index);//采用递归算法 //建立右子树 
	}
}

//遍历二叉树，并且使用前序法，输出
//采用递归算法 
void preprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		printf("%c ",T->data);//输出，一个节点 
		preprintl(T->lchild);//采用递归算法,输出左子树
		preprintl(T->rchild);//采用递归算法,输出右子树
	}
} 

//遍历二叉树，并且使用中序法，输出
//采用递归算法 
void inprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		inprintl(T->lchild);//采用递归算法,输出左子树
		printf("%c ",T->data);//输出，一个节点 
		inprintl(T->rchild);//采用递归算法,输出右子树
	}
} 

//遍历二叉树，并且使用后序法，输出
//采用递归算法 
void postprintl(TreeNode *T){//此时，并不需要改变T的值，故不用双重指针 
	if(T==NULL){//如果T为空时 
		return; 
	}else{//如果T不为空时 
		postprintl(T->lchild);//采用递归算法,输出左子树
		postprintl(T->rchild);//采用递归算法,输出右子树
		printf("%c ",T->data);//输出，一个节点 
	}
} 

//主函数
int main(){
	TreeNode *T;
	int index=0;//设置索引为0
	char *m="AB##C##"; 
	char *n="ABD##E##CF##G##";
	createTree(&T,n,&index);
	preprintl(T);//遍历二叉树，并且使用前序法，输出
	printf("\n");
	inprintl(T);//遍历二叉树，并且使用中序法，输出
	printf("\n");
	postprintl(T);//遍历二叉树，并且使用后序法，输出
	printf("\n");
}