//#include“stdafx.h“
#include
#include
#include??
#define?OVERFLOW?-2
#define?MAX?100
#define?maxsize?100

typedef?struct?bitnode
{
	char?data;
	struct?bitnode?*lch*rch;
}bitnode*bitree;

typedef?struct?queuenode
{
????bitree?ch[maxsize];
????int?front;
????int?rear;
}queuenode;

int?m=0;

void?creat（bitree?&T）
//?創(chuàng)建二叉樹
{
	char?ch;

	scanf（“%c“&ch）;
	if（ch==‘*‘）
		T=NULL;
	else
	{
	T=（bitree）malloc（sizeof（bitnode））;
	if（T==NULL）
		exit（OVERFLOW）;
	T->data=ch;?
	creat（T->lch）;
	creat（T->rch）;
	}
}

void?perorder?（bitree?T）?
//先序遍歷????
{

????if?（T）?
	{
???????printf（“%c?“T->data）;??
???????perorder（T->lch）;
???????perorder（T->rch）;
	}
}


void?incorder（bitree?T）????????
?//中序非遞歸遍歷
{

	bitree?p;
	int?top;
	bitree?s[MAX];
	bool?boolean;
	p=T;
	top=0;
	boolean=1;
		do
		{
			while（p）
			{
				if（（p->rch==NULL&&p->lch!=NULL）||（p->rch!=NULL&&p->lch==NULL））
					m++;
				s[top]=p;
				top++;
				p=p->lch;
			}
			if（top==0）
				boolean=0;
			else
			{
				top--;
				p=s[top];
				printf（“%c?“p->data）;
				p=p->rch;
			}
		}while（boolean）;
}

void?postorder（bitree?T）??
?//后序遍歷
{??
	
	if（T）?
	{?
		postorder（T->lch）;
		postorder?（T->rch）;
	????printf（“%c?“T->data）;
????}
}


void?initqueue（queuenode?&q）
//初始化一個帶頭結點的隊列
{
	q.front=q.rear=0;
}


int?enqueue（queuenode?&qbitree?T）
//入隊列
{
	if（（q.rear+1）%maxsize==q.front）
	{
???????printf（“隊列滿!!!\n“）;
???????return?0;
	}
????q.ch[q.rear]=T;
????q.rear=（q.rear+1）%maxsize;
????return?1;
}


void?dequeue（queuenode?&qbitree?&T）
//出隊列
{
????T=q.ch[q.front];
????q.front=（q.front+1）%maxsize;
????char?data;
????data=T->data;
????printf（“%c?“data）;
}?


int?queueempty（queuenode?q）
//判斷隊列是否為空
{
????if（q.front==q.rear）
????return?1;
????return?0;
}


void?traverse（bitree?T）
//按層次遍歷樹中結點
{
	queuenode?q;
	bitree?p;
?	initqueue（q）;
?	p=T;
?	enqueue（qp）;
?	while（queueempty（q）!=1）
	{?????
????????dequeue（qp）;
????????if（p->lch!=NULL）
????????if（enqueue（qp->lch）==0）
	???????return;
????????if（p->rch!=NULL）
????????if（enqueue（qp->rch）==0）
	???????return;
	}
????printf（“\n“）;
}

int?depth（bitree?T）
//求樹深
{
	if（!T）?return?0;
????int?d1;
????d1=?depth（T->lch）;
????int?d2;
????d2=?depth（T->rch）;
????return?（d1>d2?d1:d2）+1;
}


void?main（）
{
	char?i;
	bitree?A;
	printf（“先序遍歷算法建立二叉樹，請輸入節(jié)點值（空用用*表示）：\n“）;

	creat（A）;
	putchar（‘\n‘）;
	printf（“先序遍歷:“）;
	perorder（A）;
	putchar（‘\n‘）;
	printf（“中序遍歷:“）;
	incorder（A）;
	putchar（‘\n‘）;
	printf（“后序遍歷:“）;
	postorder（A）;
	putchar（‘\n‘）;
	printf（“層次遍歷:“）;
	traverse（A）;
	printf（“\n度為1的節(jié)點個數(shù)為：m=%d\n“m）;
	putchar（‘\n‘）;
	printf（“樹的深度為:%d\n\n“depth（A））;
	printf（“是否再次進行二叉樹操作（Y/N）?\n“）;
	scanf（“%s“&i）;
	if（i==‘Y‘）
	main（）;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????33792??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug\vc60.idb

?????文件??????53248??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug\vc60.pdb

?????文件?????184384??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug\二叉樹.exe

?????文件?????185492??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug\二叉樹.ilk

?????文件??????13114??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug\二叉樹.obj

?????文件?????222676??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug\二叉樹.pch

?????文件?????427008??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug\二叉樹.pdb

?????文件???????2985??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\二叉樹.cpp

?????文件???????3403??2009-06-30?13:03??數(shù)據(jù)結構二叉樹實驗\二叉樹.dsp

?????文件????????537??2009-06-30?14:07??數(shù)據(jù)結構二叉樹實驗\二叉樹.dsw

?????文件??????50176??2009-12-03?12:43??數(shù)據(jù)結構二叉樹實驗\二叉樹.ncb

?????文件??????48640??2009-12-03?12:43??數(shù)據(jù)結構二叉樹實驗\二叉樹.opt

?????文件????????750??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\二叉樹.plg

?????目錄??????????0??2009-12-03?12:38??數(shù)據(jù)結構二叉樹實驗\Debug

?????目錄??????????0??2009-12-07?09:29??數(shù)據(jù)結構二叉樹實驗

-----------?---------??----------?-----??----

??????????????1226205????????????????????15