二叉链表树的遍历

题目：

        使用二叉链表树创建算法Status CreatBiTree(BiTree &T)和其他代码

二叉树的遍历有三种：

前序遍历：先访问根节点，再遍历左子树，最后遍历右子树；

中序遍历：先遍历左子树，再访问根节点，最后遍历右子树；

后序遍历：先遍历左子树，再遍历右子树，最后访问根节点；

代码：

#include <iostream>
#include <stdlib.h> 
#include <string.h> 
#include <math.h>
using namespace std;
typedef char ElemType;   //定义结点数据为字符型 
typedef int Status;       //定义函数类型为int型 
#define ERROR 0  
#define OK 1   

int leafNum=0;

typedef struct BiTNode{        //定义结构体  
	ElemType        data;     //结点数值  
	struct BiTNode   *lchild;  //左孩子指针  
	struct BiTNode   *rchild;  //右孩子指针    
}BiTNode, *BiTree; 

void Visit(ElemType e)
{
	cout << e;
}

Status CreatBiTree(BiTree &T)//用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点 
{   
	ElemType ch;   
	cin>>ch;    
	if(ch=='#')
		T=NULL;  
	else  
	{     
		T=(BiTNode*)malloc(sizeof(BiTNode));//申请一段关于该节点类型的存储空间     
		T->data=ch;                     //生成根结点     
		CreatBiTree(T->lchild);         //构造左子树      
		CreatBiTree(T->rchild);         //构造右子树  
	}   
	return OK;
}

Status PreOrder(BiTree T)  //按先序次序(递归)访问二叉树 
{    
	if(T==NULL) 
		return ERROR;
	Visit(T->data);
	PreOrder(T->lchild);         //构造左子树      
	PreOrder(T->rchild);         //构造右子树
	return OK;  
}

Status InOrder(BiTree T)  //按中序次序(递归)访问二叉树 
{  
	if(T==NULL) 
		return ERROR;
	InOrder(T->lchild);         //构造左子树      
	Visit(T->data);
	InOrder(T->rchild);         //构造右子树
	return OK;  
}

Status PostOrder(BiTree T)  //按后序次序(递归)访问二叉树 
{  
	if(T==NULL) 
		return ERROR;
	PostOrder(T->lchild);         //构造左子树      
	PostOrder(T->rchild);         //构造右子树
	Visit(T->data);
	return OK;  
}

Status PrePrintLeaf(BiTree T)  //按先序次序(递归)输出叶子结点
{
	if(T==NULL) 
		return ERROR;
	if(T->lchild==NULL && T->rchild==NULL)
		Visit(T->data);
	PrePrintLeaf(T->lchild);         //构造左子树      
	PrePrintLeaf(T->rchild);         //构造右子树
	return OK;    
}

Status CountLeafNum(BiTree T)  //统计叶子结点的个数
{
	if(T==NULL) 
		return ERROR;
	if(T->lchild==NULL && T->rchild==NULL)
		leafNum++;
	CountLeafNum(T->lchild);         //构造左子树      
	CountLeafNum(T->rchild);         //构造右子树
	return OK;  
}

Status PostPrintNode(BiTree T)  //按后序次序(递归)输出度为2的结点
{ 
	if(T==NULL) 
		return ERROR;
	if(T->lchild!=NULL && T->rchild!=NULL)
	Visit(T->data);
	PostPrintNode(T->lchild);         //构造左子树      
	PostPrintNode(T->rchild);         //构造右子树
	return OK;  
}

int PostTreeDepth(BiTree T)  //获取二叉树高度 
{  
	int right=0,left=0,max=0;
	if(T==NULL)
		return 0;
	right = PostTreeDepth(T->lchild);         //构造左子树      
	left = PostTreeDepth(T->rchild);         //构造右子树
	max = right>left?right:left;
	return max+1;
}

效果图：