[数据结构与算法]二叉树的应用（范文）数据结构

1.编写算法实现二叉树T的按层遍历。（二叉树采用二叉链表存储）

#define OK 1
#define ERROR 0
typedef int Status;
//-------------------二叉链表的存储表示--------------------
typedef struct BiTNode{	
		TElemType data;
			struct BiTNode  *lchile, *rchild;
}BiTNode, *BiTree;
	//-------------------算法描述------------------------------------
		Status LayerTraverse(BiTree  T, Status  (*visit)(TElemType  e)){	//按层遍历二叉链表T。
			if(!T)	return OK;
			InitQueue(Q);
			EnQueue(Q,T);
			while(!QueueEmpty(Q))
			{	
				DeQueue(Q,p);
				if(!(*visit)(p->data))		return ERROR;
				if(p->lchild)	EnQueue(Q,p->lchild);
				if(p->rchild)	EnQueue(Q,p->rchild);
			}
			return OK;
		}//LayTraverse

2.编写算法实现对二叉树T交换左右子树的操作。（二叉树采用二叉链表存储） 参考算法： 符号常量和类型的定义及二叉链表的存储表示如 1题。

Status  Exchange(Bitree  &T)
	{	
		if(!T)	return OK;
		p=T->lchild;	T->lchild=T-rchild;		T->rchild=p;
		Exchange(T->lchild);
		Exchange(T->rchild);
		return OK;
	}//Exchange

3.编写算法实现统计并返回二叉树T的叶子结点的数目的操作。（二叉树采用二叉链表存储） 参考算法： 符号常量和类型的定义及二叉链表的存储表示如第1题。

int Countleaf(Bitree  T)
		{	
			if(!T)	return 0;
			if(T->lchild==NULL&&T->rchild==NULL)		return 1;
			return(Countleaf(T->lchild)+Countleaf(T->rchild));
		}

4.编写算法实现计算并返回二叉树T的深度。（二叉树采用二叉链表存储） 参考算法： 符号常量和类型的定义及二叉链表的存储表示如第1题

int BitreeDepth(BiTree T)
	{	
		if(!T)
			return 0;
		else{
			left=BitreeDepth(T->lchild);
			right=BitreeDepth(T->rchild);
			return( left>right?left+1:right+1);
		}
	}