bitree.cpp

数据结构课程设计,表达式,用C语言实现,难度系数较高

#include <stdio.h>
#include <stdlib.h>
#include "../header/bitree.h"
#include "../header/queue.h"
#include "../header/stack.h"
#include "../header/expr.h"

 
Status CreateBiTree( BiTree & T)  
//操作结果：构造二叉树T。
//先序输入二叉树
{   
    char ch;   
    scanf( "%c", &ch );
    if( ch == ' ' )   
        T = NULL;   
    else   
	{   
		if( ! ( T = ( BiTree  )malloc( sizeof( BiTNode ) ) ) )
			return ERROR;   
		T->data = ch;   
		CreateBiTree( T->lchild );   
		CreateBiTree( T->rchild );  
	}
	return OK;
}

Status ArrayCreate( BiTree &T, char *ch, int &i )
//用字符数组构造二叉树
{   
//int i = 0;
	if( !ch[i] ) return OK;
	if( ch[i] == ' ' )   
        T = NULL;
	else
	{
		if( ! ( T = ( BiTree  )malloc( sizeof( BiTNode ) ) ) )
			return ERROR;   
		T->data = ch[i];
		//if( T->data == '+' || T->data == '-' || T->data == '*' || T->data == '/' || T->data == '^' )

			ArrayCreate( T->lchild, ch, ++i ); 
				ArrayCreate( T->rchild, ch, ++i ); 
	}
	return OK;
}

Status Create( BiTree &T )
///初始条件：二叉树T存在，e是T中某个结点。
//操作结果：有提醒文字的创建树
{
	printf("请以先序顺序输入您要建立的二叉树(空孩子用空格表示):\n");
	if( CreateBiTree( T ) )
	{
		PrintBiTree( T );
		return OK;
	}
	return FALSE;
}

void PrintBiTree( BiTree T )
//初始条件：二叉树T存在，e是T中某个结点。
//操作结果：有文字说明的,前序输出
{
	printf("前序输出: "); 
	PreOrderTraverse( T, Visit );  
	printf("\n\n");
}

Status InitBiTree(BiTree & T)
//操作结果：构造空二叉树。
{
	T = NULL;
	return OK;
}

Status BiTreeEmpty(BiTree & T )
//初始条件：二叉树T存在。
//操作结果：若T为空二叉树，则返回TRUE，否则FALSE。
{
	return T == NULL;
}

Status ClearBiTree(BiTree &T)
//初始条件：二叉树T存在。
//操作结果：将T清为空二叉树，成功则返回TRUE，否则FALSE
{
	if( T )
	{
		ClearBiTree( T->lchild );
		ClearBiTree( T->rchild );
		T->lchild=NULL;
		T->rchild=NULL;
		T->data=0;
		return OK;
	}
	return ERROR;
}

Status DestroyBiTree( BiTree &T )
//初始条件：二叉树T存在。
//操作结果：销毁二叉树T。
{   
	if( T )   
	{     
		if( DestroyBiTree( T->lchild ) )
			if( DestroyBiTree( T->rchild ) )   
			{
				free( T );
				T = NULL;
				return OK;
			}
		return ERROR;
	}
	return OK;
}

Status BTValue( BiTree T, BiTNode E, TElemType &e )
//初始条件：二叉树T存在，E是T中某个结点。
//操作结果：返回E的值。
{
	if( T )
	{
		e = E.data;
		return OK;
	}
	else
		return FALSE;
}

Status BTAssign( BiTree &T, TElemType &e, TElemType value ) 
//初始条件：二叉树T存在，e是T中某个结点。
//操作结果：结点e赋值为value。
{
	if( T )
	{
		if( T->data == e )
		{
			T->data = value;
			return OK;		//找到了
		}
		if( !BTAssign( T->lchild, e, value ) )			//在T的左孩子找不到
			if( !BTAssign( T->rchild, e, value ) )		//在T的右孩子找不到
				return FALSE;
		return OK;
	}
	return FALSE;//是空树
}

BiTree Root( BiTree T)
//初始条件：二叉树T存在。
//操作结果：返回T的根。
{
	return T;
}

int BiTreeDepth( BiTree T )
//初始条件：二叉树T存在。
//操作结果：返回T的深度。
{ 
	int ldep,rdep;
    if( !T ) return 0;							//空树的高度为0
    else
	{
		ldep = BiTreeDepth( T->lchild );		//求左子树的高度
		rdep = BiTreeDepth( T->rchild );		//求右子树的高度
		return ( ldep > rdep ) ? ( ldep + 1 ) : ( rdep + 1 );
	}
}

int Counter( BiTree T )
//初始条件：二叉树T存在。
//操作结果：返回T的结点的个数
{
    if( !T ) 
		return 0;
    else 
		return Counter( T->lchild ) + Counter( T->rchild ) + 1;
}

int NumLeaf( BiTree T )
//初始条件：二叉树T存在。
//操作结果：返回T的叶子个数
{
	if( !T )
		return 0;
	else if( !T->lchild && !T->rchild )		//T是叶子
		return 1;
	else
		return  NumLeaf( T->lchild ) + NumLeaf( T->rchild );
}

int BiTreeWidth( BiTree T )
//初始条件：二叉树T存在。
//操作结果：返回T的的宽度
//宽度：具有结点数最多的那一层上的结点个数
{
	struct
	{
		int l;							//结点层次编号
		BiTree p;						//结点指针
	}Que[MAXSIZE];
	int  front = 0, rear = 0 ;
	int num ,max,i,n;
	if( T )
	{
		rear++;
		Que[rear].p = T;
		Que[rear].l = 1;
		while(rear!=front)
		{
			front++;
			T = Que[front].p;
			num = Que[front].l;
			if( T->lchild )
			{
				rear++;
				Que[rear].p = T->lchild;
				Que[rear].l = num +1;
			}
			if( T->rchild )
			{
				rear++;
				Que[rear].p = T->rchild;
				Que[rear].l = num + 1;
			}
		}
		max = 0;
		num = 1;
		i = 1;
		while( i <= rear )
		{
			n=0;
			while( i <= rear && Que[i].l == num )
			{
				n++;
				i++;
			}
			num = Que[i].l;
			if( n > max )  
				max = n;
		}
		return max;
	}
	else
		return 0;
}

int CountDegree2( BiTree T )
//初始条件：二叉树T存在。
//操作结果：返回T中度为2的结点数
//递归算法实现
{
	if( !T )	return 0;
	int num1 = CountDegree2( T->lchild );
	int num2 = CountDegree2( T->rchild );
	if( T->lchild && T->rchild )
		return ( num1 + num2 + 1 );
	else
		return ( num1 + num2 );
}

BiTree Parent( BiTree T, TElemType e )
//初始条件：二叉树T存在，e是T中某个结点。
//操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。
{
	BiTree bt;
	if( T )
	{
		if ( ( T->lchild )&& ( T->lchild->data == e ) || ( T->rchild ) && ( T->rchild->data == e ) )
			return T;
		if( ! ( bt = Parent( T->lchild, e ) ) )			//在T的左孩子中找不到
			if( ! ( bt = Parent( T->rchild, e ) ) )		//在T的右孩子找不到
				return NULL;
		return bt;
	}
	return NULL;	
}

BiTree LeftChild( BiTree T, TElemType e )
//初始条件：二叉树T存在，e是T中某个结点。
//操作结果：返回e的左孩子。若e无左孩子，则返回“空”。
{
	BiTree bt;
	if( T )
	{
		if ( T->data == e )
			return T->lchild;
		if( !( bt = LeftChild( T->lchild, e ) ) )			//在T的左孩子中找不到
			if( !( bt = LeftChild( T->rchild, e ) ) )		//在T的右孩子找不到
				return NULL;
		return bt;
	}
	return NULL;	
}

BiTree RightChild( BiTree T, TElemType e )
//初始条件：二叉树T存在，e是T中某个结点。
//操作结果：返回e的右孩子。若e无左孩子，则返回“空”。
{
	BiTree bt;
	if( T )
	{
		if ( T->data == e )
			return T->rchild;
		if( !( bt = RightChild( T->lchild, e ) ) )			//在T的左孩子中找不到
			if( !( bt = RightChild( T->rchild, e ) ) )		//在T的右孩子找不到
				return NULL;
		return bt;
	}
	return NULL;	
}

BiTree LeftSibling( BiTree T, TElemType e )
//初始条件：二叉树T存在，e是T中某个结点。
//操作结果：返回e的左兄弟。若e 是T的左孩子或无左兄弟，则返回“空”。
{
	BiTree bt;
	if( T )
	{
		if ( ( T->rchild ) && ( T->rchild->data == e ) )
			return T->lchild;
		if( !( bt = LeftSibling( T->lchild, e ) ) )			//在T的左孩子中找不到
			if( !( bt = LeftSibling( T->rchild, e ) ) )		//在T的右孩子找不到
				return NULL;
		return bt;
	}
	return NULL;	
}

BiTree RightSibling( BiTree T, TElemType e )
//初始条件：二叉树T存在，e是T中某个结点。
//操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。
{
	BiTree bt;
	if( T )
	{
		if ( ( T->lchild ) && ( T->lchild->data == e ) )
			return T->rchild;
		if( !( bt = RightSibling( T->lchild, e ) ) )		//在T的左孩子中找不到
			if( !( bt = RightSibling( T->rchild, e ) ) )	//在T的右孩子中找不到
				return NULL;
		return bt;
	}
	return NULL;	
}

Status Visit( TElemType e )
//输出e
{
	
	printf("%c ", e );
	return OK;
}

BiTree FindNode(BiTree T, TElemType x)    //返回data域为x结点的指针 
{
	BiTree p;
	if( !T )	return NULL ;
	else if( T->data == x )		return T;
	else
	{
		p = FindNode( T->lchild, x );           //在左子树中找
		if( !p )							//在左子树中找不到
			p = FindNode( T->rchild, x );   //在右子树中找
		return	p;
	}
}


Status PreOrderTraverse( BiTree T, Status ( * Visit )( TElemType e ) )//前序遍历的递归算法   
{   
	if(T)   
	{     
		if( Visit( T->data ) )
			if( PreOrderTraverse( T->lchild, Visit ) )   
				if( PreOrderTraverse( T->rchild,Visit ) )
					return OK;
		return ERROR;
	}
	else
		return OK;
}

Status InOrderTraverse( BiTree T, Status ( * Visit )( TElemType e ) )//中序遍历的递归算法
{   
	if(T)   
	{     
		if( InOrderTraverse( T->lchild, Visit ) )
			if( Visit( T->data ) )   
				if( InOrderTraverse( T->rchild,Visit ) )
					return OK;
		return ERROR;
	}
	else
		return OK;
}

Status PostOrderTraverse( BiTree T, Status ( * Visit )( TElemType e ) )//后序遍历的递归算法
{   
	if( T )   
	{     
		if( PostOrderTraverse( T->lchild, Visit ) )
			if( PostOrderTraverse( T->rchild,Visit ) )   
				if(  Visit( T->data ) )
					return OK;
		return ERROR;
	}
	else
		return OK;
}

Status LevelOrdeTraverse( BiTree T, Status ( * Visit )( TElemType e ) )//层序遍历的非递归算法
{
   TElemType q[20];
   int i = -1, j = -1;
   BiTree t = T;
   if( t )
	   q[++i] = t->data;   
	while( j < i )
	{
		t = FindNode( T, q[++j] );
		if( t->lchild )
			q[++i] = t->lchild->data;		 
		if( t->rchild ) 
			q[++i] = t->rchild->data;
		
	} 
	for( j = 0; j <= i; j++ )
		Visit( q[j] );
	return OK;
}

Status PreOrder( BiTree T, Status( * Visit )( TElemType e ) )
//前序遍历的非递归算法
{
	SqStack S;
	InitStack( S );
	BiTree p;
	if( T )
	{
		Push( S, T );					//根结点入栈
		while( !StackEmpty( S ) )		//栈不为空时循环
		{
			Pop( S, p );
			Visit( p->data );
			if( p->rchild )
				Push( S, p->rchild );
			if( p->lchild )
				Push( S, p->lchild );
		}
		return OK;
	}
	return FALSE;
}

Status InOrder( BiTree T, Status( * Visit )( TElemType e ) )
//中序遍历的非递归算法
{
	SqStack S;
	InitStack( S );
	BiTree p;
	if( T )
	{
		p = T;
		while ( ! StackEmpty( S ) || p )
		{
			while( p )					//扫描*p的所有左孩子结点并进栈
			{
				Push( S, p );
				p = p->lchild;
			}
			if( ! StackEmpty( S ) )
			{
				Pop( S, p );
				Visit( p->data );
				p = p->rchild;			//扫描*p的所有右孩子结点
			}
		}
		return OK;
	}
	return FALSE;
}

/*书上的
Status InOrder( BiTree T, Status( * Visit )( TElemType e ) )
//中序遍历的非递归算法
{
	SqStack S;
	InitStack( S );
	BiTree p = T;
	while( p || !StackEmpty( S ) )
	{
		if( p )
		{
			Push( S,p );
			p = p->lchild;
		}
		else
		{
			Pop( S, p );
			if( !Visit( p->data ) )
				return ERROR;
			p = p->rchild;
		}
	}
	return OK;
}
*/

Status PostOrder( BiTree T, Status ( * Visit )( TElemType e ) )
//后序遍历的非递归算法
{
	SqStack S;
	InitStack( S );
	BiTree p;
	int flag;
	if( T )
	{
		do
		{
			while( T )						//将T所有左结点进栈
			{
				Push( S, T );
				T = T->lchild;
			}
			p = NULL;						//p指向栈顶结点的前一个已访问的结点
			flag = 1;						//设置T的访问标记为已访问
			while( ! StackEmpty( S ) && flag )
			{
				GetTop( S, T );
				if( T->rchild == p )		//右孩子不存在或右孩子已被访问
				{
					Visit( T->data );
					Pop( S, p );
				}
				else
				{
					T = T->rchild;
					flag = 0;				//设置未被访问的标记
				}
			}
		}while( !StackEmpty( S ) );
		return OK;
	}
	return FALSE;
}
		
/*
void MidTravelBiTree(BiTree T)   //中序遍历的递归算法
{   
	if(T!=NULL)   
	{     
		MidTravelBiTree(T->lchild);   //递归访问左子树
		Visit(T->data);//printf("d%cd",T->data);   //访问根结点
		MidTravelBiTree(T->rchild);   //递归访问右子树
	}   
}
*/

void WriteExpr( BiTree T )
//用带括号的中序表示式输出
{
	if( T )
	{
		printf("%c", T->data );
		if( T->lchild || T->rchild )
		{
			printf( "(" );
			WriteExpr( T->lchild );
			if( T->rchild ) 
				printf( "," );
			WriteExpr( T->rchild );
			printf( ")" );
		}
	}
}

/*
Status Exchange( BiTree T )//完成调试
//交换左右孩子
{
	BiTree p;
	if( T )
	{
		p = T->lchild;				//交换T的左右孩子
		T->lchild = T->rchild;
		T->rchild = p;
		if( Exchange( T->lchild ) )
			if( Exchange( T->rchild ) )
				return OK;
		return FALSE;
	}
	return OK;
}*/

Status IsCompleteBit( BiTree T )
//判定T是不是完全二叉树，是，返回TRUE，否则，返回FALSE
//要用到队列
{
	int flag = 0;
	if( !T )	return TRUE;	//空树是完全二叉树
	Queue Q;
	InitQueue( Q );				
	EnQueue( Q, T );
	BiTree p;
	while( !QueueEmpty( Q ) )
	{
		DeQueue( Q,p );
		if( p->lchild && !flag )
			EnQueue( Q, p->lchild );
		else 
			if( p->lchild )
				return FALSE;
			else
				flag = 1;
		if( T->rchild && !flag )
			EnQueue( Q, p->rchild );
		else 
			if( p->rchild )
				return FALSE;
			else
				flag = 1;
	}
	return TRUE;
}

Status IsLikeBit( BiTree S,BiTree T )
{//判断S和T是否相似
	if( !S && !T )//都为空
		return TRUE;
	else if( S&& T )//都不为空
		return ( IsLikeBit ( S->lchild, T->lchild ) 
			  && IsLikeBit ( S->rchild, T->rchild ) );
	else 
		return FALSE;
}



Status InserChild( BiTree T, BiTree p, int LR, BiTree c)
//初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。
//操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。
//          p所指结点的原有左或右子树则成为c的右子树。
{
	if( T )
		if( p )
		{
			if ( !LR )
			{
				c->rchild = p->lchild; 
				p->lchild = c;
			}
			else 
			{
				c->rchild = p->rchild; 
				p->rchild = c;
			}
			return OK;
		}
	return ERROR;
}

Status DeleteChild( BiTree T, BiTree p, int LR )
//初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。
//操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。
{
	if( T )
		if ( p )
		{
			if ( !LR ) 
			{
				DestroyBiTree ( p->lchild );
				p->lchild = NULL;
			}
			else 
			{
				DestroyBiTree ( p->rchild );
				p->rchild = NULL;
			}
			return OK;
		}
	return ERROR;
}