二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于2。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。二叉树详细请看本文：二叉树

所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

代码如下：

#include<iostream>
#include<cstdlib>
using namespace std;
typedef char ElemType;
typedef struct Node
{
	ElemType data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode,*BiTree;
int LeafCount;
int Depth;

void Visit(ElemType T)//用于遍历的输出
{
	cout<<T;
}

//1.建立二叉树
void CreateBiTree(BiTree *bt)
{
	char ch; 
	ch = getchar();
	if(ch=='.') *bt=NULL;
	else 
	{
		*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
		(*bt)->data=http://www.mamicode.com/ch;>
附带二叉树遍历的非递归算法：
/* 中后非递归遍历二叉树，作为遍历方法的参考*/

//8.中序遍历二叉树非递归算法(三个)

/*算法a*/
void inorder(BiTree root);
{
	int top=0; p=bt;
L1: if (p!=NULL)       /* 遍历左子树 */       
	{ 
		top=top+2;    
		if(top>m) return;       /*栈满溢出处理*/
		s[top-1]=p;            /* 本层参数进栈 */    
		s[top]=L2;             /* 返回地址进栈 */
		p=p->LChild;           /* 给下层参数赋值 */
		goto L1;               /* 转向开始 */
L2:  Visit(p->data);     /* 访问根 */
     top=top+2;
     if(top>m) return;       /*栈满溢出处理*/;
     s[top-1]=p;            /* 遍历右子树 */
     s[top]=L3;
     p=p->RChild;
     goto L1;
	}
L3: if(top!=0)      
	{ 
		addr=s[top];
		p=s[top-1];            /* 取出返回地址 */
		top=top-2;             /* 退出本层参数 */
		goto addr;
	}
}

/*算法b*/
void inorder(BiTree root)   /* 中序遍历二叉树，root为二叉树的根结点 */
{
	int top=0; 
	BiTree p;
	BiTree s[Stack_Size];
	int m;
	m = Stack_Size-1;
	p = root;
	do
	{
		while(p!=NULL)
		{ 
			if (top>m) return;
			top=top+1;  
			s[top]=p;
			p=p->LChild;
		};  /* 遍历左子树 */
		if(top!=0)
		{ 
			p=s[top];
			top=top-1;
			Visit(p->data);  /* 访问根结点 */
			p=p->RChild;  /* 遍历右子树 */
		}   
	}
	while(p!=NULL || top!=0);
}


/*算法c*/
void  InOrder(BiTree root) /* 中序遍历二叉树的非递归算法 */
{
	SeqStack S;
	BiTree p;
	InitStack (&S);
	p=root;
	while(p!=NULL || !IsEmpty(&S))
	{ 
		if (p!=NULL)  /* 根指针进栈，遍历左子树 */
		{
			Push(&S,p);
			p=p->LChild;
		}
		else
		{  /*根指针退栈，访问根结点，遍历右子树*/
			Pop(&S,&p); 
			Visit(p->data);  
			p=p->RChild;
		}
	}
}


//9.后序遍历二叉树的非递归算法

void PostOrder(BiTree root)
{
	BiTNode *p,*q;
	BiTNode **s;
	int top=0;
	q=NULL;
	p=root;
	s=(BiTNode**)malloc(sizeof(BiTNode*)*NUM);
	/* NUM为预定义的常数 */
	while(p!=NULL || top!=0)
	{
		while(p!=NULL)
		{
			top++; 
			s[top]=p; 
			p=p->LChild; 
		}  /*遍历左子树*/
		if(top>0) 
		{	
			p=s[top];
			if((p->RChild==NULL) ||(p->RChild==q))	/* 无右孩子，或右孩子已遍历过 */
			{
				visit(p->data);        /* 访问根结点*/
				q=p;            	/* 保存到q，为下一次已处理结点前驱 */
				top--;
				p=NULL;
			} 
			else	
				p=p->RChild;
		}
	}
	free(s);
}




二叉树的遍历，深度求解以及竖向打印详析