二叉树

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100

typedef char ElemType;
typedef struct Node{
	ElemType data;
	struct Node *lchild;
	struct Node *rchild;
} BTree;

/**
*由括号表示法创建链式二叉树
*例如：A(B(D(,G)),C(E,F))
*      创建结点A，A为根结点；A压栈，k=1；创建B，B为A的左孩子；B压栈，k=1；
*      创建D，D为B的左孩子；D压栈，k=1；k=2；G为D的右孩子；D出栈；B出栈；k=2；
* C为A的右孩子；C压栈，k=1；创建E，E为C的左孩子；k=2；F为C的右孩子；C出栈；A出栈
*/
void CreateBTree(BTree *&b,char *str){
	BTree *st[MaxSize]; int top=-1;  //st作为栈，其元素为BTree *，st存储树节点
	int k;                           //k标记是左孩子还是右孩子  
	int i=0; char ch=str[i];          //ch为遍历元素str所处的元素，i为对应位置
	b=NULL;	
	BTree *p=NULL;
	while (ch!='\0'){
   	   	switch(ch) {
	      	case '(':top++;st[top]=p;k=1; break;//接下来创建左孩子，父亲压栈
		    case ')':top--;break;               //右孩子创建完毕，父亲出栈
	    	case ',':k=2; break;                //左孩子创建完毕，接下来创建右孩子
		    default:
				p=(BTree *)malloc(sizeof(BTree));
		     	p->data=ch;p->lchild=p->rchild=NULL;
		         	if (b==NULL)                 //还没有创建根结点
						b=p;
					else
						k==1?st[top]->lchild=p:st[top]->rchild=p;
		}
		ch=str[++i];
	}
}

/**
*查找结点，返回指向该节点的指针
*/
BTree *Find(BTree *b,ElemType x){
	BTree *p;
	if (b==NULL)
	     return NULL;
    if (b->data==x)
	     return b;
	p=Find(b->lchild,x);
		if (p==NULL) 
			return Find(b->rchild,x);
		return NULL;
}

/**
*求二叉树的深度
*/
int BTreeDepth(BTree *b){
   	int l,r;
   	if (b==NULL) 
		return 0; 	
    return 1+((l=BTreeDepth(b->lchild))>(r=BTreeDepth(b->rchild))?l:r);
}

/**
*用括号表示法输出二叉树
*/
void Display(BTree *b){
	if (b!=NULL){
		printf("%c",b->data);
		if (b->lchild!=NULL || b->rchild!=NULL){
			printf("(");
			Display(b->lchild);
			if (b->rchild!=NULL) 
				printf(",");
			Display(b->rchild);
			printf(")");
		}
	}
}

/**
*先序遍历二叉树
*/
void Order(BTree *b){
	if(b!=NULL){
		printf("%c ",b->data);    //若中序遍历，此句放在倒数第二行；若后序，放最后一行
		Order(b->lchild);
		Order(b->rchild);
	}
}

/**先序遍历二叉树（非递归）
*这里用一个栈来存储父节点
*例如：A(B(D(,G)),C(E,F))，操作过程依次是：
*      A进栈（循环之前），top=0；A出栈，C、B入栈，top=1；B出栈，D入栈，top=1；
*      D出栈，G入栈，top=1；G出栈，top=0；C出栈，F、E入栈，top=1；
*      E出栈，top=0；F出栈，top=-1；
*/
void Order1(BTree *b){
	BTree *st[MaxSize]; int top=-1; 
	BTree *p=NULL;
	if(b!=NULL){
		top++;st[top]=b;
	}
	while(top!=-1){
		p=st[top];top--;
		if(p->rchild!=NULL){
			st[++top]=p->rchild;
		}
		if(p->lchild!=NULL){
			st[++top]=p->lchild;
		}
		printf("%c ",p->data);
	}
}

void InOrder(BTree *b)
{
	BTree *St[MaxSize],*p;
	int top=-1;
	if (b!=NULL)
	{
		p=b;
		while (top>-1 || p!=NULL)
		{
			while (p!=NULL)
			{
				top++;
				St[top]=p;
				p=p->lchild;
			}
			if (top>-1)
			{
				p=St[top];
				top--;
				printf("%c ",p->data);
				p=p->rchild;
			}
		}
		printf("\n");
	}
}

void PostOrder(BTree *b)
{
	BTree *St[MaxSize];
	BTree *p;
	int flag,top=-1;						//栈指针置初值
	if (b!=NULL)
	{
		do
		{
			while (b!=NULL)					//将t的所有左结点入栈
			{
				top++;
				St[top]=b;
				b=b->lchild;
			}
			p=NULL;							//p指向当前结点的前一个已访问的结点
			flag=1;	
			while (top!=-1 && flag)
			{
				b=St[top];					//取出当前的栈顶元素
				if (b->rchild==p)			//右子树不存在或已被访问,访问之
				{
					printf("%c ",b->data);	//访问*b结点
					top--;
					p=b;					//p指向则被访问的结点
				}
				else
				{
					b=b->rchild;			//t指向右子树
					flag=0;	
				}
			}
		} while (top!=-1);
		printf("\n");
	} 
}

void TravLevel(BTree *b)
{
	BTree *Qu[MaxSize];				//定义循环队列
	int front,rear;						//定义队首和队尾指针
	front=rear=0;						//置队列为空队列
    if (b!=NULL) 
		printf("%c ",b->data);
    rear++;								//结点指针进入队列
	Qu[rear]=b;
    while (rear!=front)					//队列不为空
    {
		front=(front+1)%MaxSize;
		b=Qu[front];					//队头出队列
		if (b->lchild!=NULL)			//输出左孩子,并入队列
		{
			printf("%c ",b->lchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=b->lchild;
		}
		if (b->rchild!=NULL)			//输出右孩子,并入队列
		{
			printf("%c ",b->rchild->data);
			rear=(rear+1)%MaxSize;
			Qu[rear]=b->rchild;
		}
	} 
	printf("\n");
}

void main()
{
	BTree *b;
	CreateBTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); 
	printf("       二叉树:");Display(b);
	printf("\n\n");
	printf(" 层次遍历序列:");
	TravLevel(b);printf("\n");
	printf(" 先序遍历序列:\n");
	printf("     递归算法:");Order(b);printf("\n");
	printf("   非递归算法:");Order1(b);printf("\n\n");
	printf(" 中序遍历序列:\n");
	printf("   非递归算法:");InOrder(b);printf("\n");
	printf(" 后序遍历序列:\n");
	printf("   非递归算法:");PostOrder(b);printf("\n");
	printf("     树的深度:");
	int d=BTreeDepth(b);printf("%d\n",d);
}

 运行结果：

       二叉树:A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))

 层次遍历序列:A B C D E F G H I J K L M N

 先序遍历序列:
     递归算法:A B D E H J K L M N C F G I
   非递归算法:A B D E H J K L M N C F G I

 中序遍历序列:
   非递归算法:D B J H L K M N E A F C G I

 后序遍历序列:
   非递归算法:D J L N M K H E B F I G C A

     树的深度:7