数据结构之线索二叉树

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define M 20
typedef char ElemType;
typedef struct node
{
	ElemType data;
	struct node *left,*right;
}BiTree;
typedef struct
{
	BiTree *ptr;
	char tag;
}seqstack;
BiTree *CreateBiTree()
{
	BiTree *t;
	ElemType ch;
	fflush(stdin);//在这里释放缓存，否则会令ch为缓存区第一个数而不是键盘输入的数，键盘输入的数则会放在缓存区末位
	scanf("%c",&ch);
	if(ch!='#')
	{
		//fflush(stdin);这里无需缓存
		t=(BiTree *)malloc(sizeof(BiTree));
		t->data=ch;
		t->left=CreateBiTree();
		t->right=CreateBiTree();
	}else
		t=NULL;
	return t;
}
//先序遍历递归算法
void PreOrder(BiTree *t)
{
	if(t!=NULL)
	{
		printf("%c ",t->data);
		PreOrder(t->left);
		PreOrder(t->right);
	}
}
//中序遍历递归算法
void InOrder(BiTree *t)
{
	if(t!=NULL)
	{
		InOrder(t->left);
		printf("%c ",t->data);
		InOrder(t->right);
	}
}
//后序遍历递归算法
void PostOrder(BiTree *t)
{
	if(t!=NULL)
	{
		PostOrder(t->left);
		PostOrder(t->right);
		printf("%c ",t->data);
	}
}
//二叉树的层次遍历算法
void LevelOrder(BiTree *t)
{
	BiTree *p;
	BiTree *queue[M];
	int front,rear;
	if(t==NULL) return;
	front=rear=0;
	queue[rear]=t;
	rear=(rear+1)%M;
	while(front!=rear)
	{
		p=queue[front];
		front=(front+1)%M;
		printf("%c ",p->data);
		if(p->left!=NULL)
		{
			queue[rear]=p->left;
			rear=(rear+1)%M;
		}
		if(p->right!=NULL)
		{
			queue[rear]=p->right;
			rear=(rear+1)%M;
		}
	}
}
//二叉树的先序遍历非递归算法
void PreOrder_Nonrecursive(BiTree *t)
{
	BiTree *s[M],*p;
	int top=0;
	if(t!=NULL)
	{
		p=t;
		do
		{
			while(p!=NULL)
			{
				printf("%c ",p->data);
				s[top]=p;
				top++;
				p=p->left;
			}
			if(top>0)
			{
				top--;
				p=s[top];
				p=p->right;
			}
		}while(p!=NULL||top>0);
	}
}
//二叉树中序遍历非递归算法
void InOrder_Nonrecursive(BiTree *t)
{
	BiTree *s[M],*p;
	int top=0;
	if(t!=NULL)
	{
		p=t;
		do
		{
			while(p!=NULL)
			{
				s[top]=p;
				top++;
				p=p->left;
			}
			if(top>0)
			{
				top--;
				p=s[top];
				printf("%c ",p->data);
				p=p->right;
			}
		}while(p!=NULL||top>0);
	}
}
//二叉树后序遍历非递归算法
void PostOrder_Norecursive(BiTree *t)
{
	BiTree *p;
    seqstack s[M],q;
	int top=0;
	p=t;
	if(t!=NULL)
		do{
			while(p!=NULL)
			{
				q.ptr=p;
				q.tag='L';
				s[top]=q;
				top++;
				p=p->left;
			}
			top--;
			q=s[top];
			p=q.ptr;
			while(q.tag=='R')
			{
				printf("%c ",p->data);
				if(p==t)
					break;
				if(top>0)
				{
					top--;
					q=s[top];
					p=q.ptr;
				}
			}
			if(q.tag=='L')
			{
				q.ptr=p;
				q.tag='R';
				s[top]=q;
				top++;
				p=p->right;
			}
		}while(top>0);
}
//统计二叉树中叶子结点个数的算法
int CountLeaf(BiTree *t)
{
	BiTree *s[M],*p;
	int top=0,cnt=0;
	if(t!=NULL)
	{
		p=t;
		do
		{
			while(p!=NULL)
			{
				if(p->left==NULL&&p->right==NULL)
					cnt++;
				s[top]=p;
				top++;
				p=p->left;
			}
			if(top>0)
			{
				top--;
				p=s[top];
				p=p->right;
			}
		}while(p!=NULL||top>0);
	}
	return cnt;
}
//求二叉树深度的算法
int TreeDepth(BiTree *t)
{
	int h1,hr,max;
	if(t!=NULL)
	{
		h1=TreeDepth(t->left);
		hr=TreeDepth(t->right);
		max=h1>hr?h1:hr;
		return max+1;
	}
	else 
		return 0;
}
void main()
{
	BiTree *mytree;
	int n,h;
	printf("请输入数据");
	mytree=CreateBiTree();
	printf("创建成功！\n");
	printf("先序遍历为:");
	PreOrder(mytree);
	printf("\n");
	printf("中序遍历为:");
	InOrder(mytree);
	printf("\n");
	printf("后序遍历为:");
	PostOrder(mytree);
	printf("\n");
	printf("层次遍历为:");
	LevelOrder(mytree);
	printf("\n");
	printf("非递归先序遍历为:");
	PreOrder_Nonrecursive(mytree);
	printf("\n");
	printf("非递归中序遍历为:");
	InOrder_Nonrecursive(mytree);
	printf("\n");
	printf("非递归后序遍历为:");
	PostOrder_Norecursive(mytree);
	printf("\n");
	n=CountLeaf(mytree);
    printf("该二叉树的叶子结点个数为%d\n",n);
	h=TreeDepth(mytree);
	printf("该二叉树的深度为%d\n",h);
}