tree.h

这个程序是用来实现二叉树的一些最基本的操作。如前序

#include"stdio.h"
#include"malloc.h"

typedef struct BNode
{
	DataTypeT data;
	struct BNode *left;
	struct BNode *right;
}BiTreeNode;

#define MaxQueueSize   100
typedef BiTreeNode* DataTypeQ;
#include"SeqQueue.h"

#define MaxStackSize   100
typedef BiTreeNode* DataTypeS;
#include"SeqStack.h"

void Destroy(BiTreeNode **root);


void Initiate( BiTreeNode **root )
{
	*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
	if( *root == NULL )
	{
		printf("\nThe memory is shortage!\n");
		return;
	}

	(*root)->left = NULL;
	(*root)->right = NULL;
}

BiTreeNode *CreateBiTreeNode(DataTypeT x)
{
	BiTreeNode *p = NULL;
	if( NULL == ( p = (BiTreeNode*)malloc( sizeof(BiTreeNode) ) ) )
	{
		printf("\nWrong when call the CreateBiTreeNode():the memory is shortage!\n");
		return NULL;
	}

	p->data = x;
	p->left = NULL;
	p->right = NULL;

	return p;

}


BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataTypeT x)
{
	BiTreeNode *s;

	if( NULL == curr )
		return NULL;

	if( NULL == (s = (BiTreeNode *)malloc( sizeof(BiTreeNode) ) ) )
	{
		printf("\nThe memory is shortage!\n");
		return NULL;
	}

	s->data = x;
	s->left = curr->left;
	s->right = NULL;

	curr->left = s;

	return s;
}




BiTreeNode *InsertRightNode(BiTreeNode *curr, DataTypeT x)
{
	BiTreeNode *s;

	if( NULL == curr )
		return NULL;

	if( NULL == (s = (BiTreeNode *)malloc( sizeof(BiTreeNode) ) ) )
	{
		printf("\nThe memory is shortage!\n");
		return NULL;
	}

	s->data = x;
	s->left = NULL;
	s->right = curr->right;

	curr->right = s;

	return s;
}


BiTreeNode *InsertLeftTree( BiTreeNode *curr,BiTreeNode *t )
{
	BiTreeNode *p,*q;

	p = curr->left;
	q = t->left;

	if( q != NULL )
	{
		while(q->left != NULL)
			q = q->left;
	}

	curr->left = t;
	q->left = p;

	return q;

}



BiTreeNode *InsertRightTree( BiTreeNode *curr,BiTreeNode *t )
{
	BiTreeNode *p,*q;

	p = curr->right;
	q = t->right;

	if( q != NULL )
	{
		while(q->right != NULL)
			q = q->right;
	}

	curr->right = t;
	q->right = p;

	return q;

}


BiTreeNode *DeleteLeftTree(BiTreeNode* curr)
{
	if( NULL == curr || NULL == curr->left )
		return NULL;

	Destroy( &curr->left );

	curr->left = NULL;

	return curr;

}


BiTreeNode *DeleteRightTree(BiTreeNode* curr)
{
	if( NULL == curr || NULL == curr->right )
		return NULL;

	Destroy( &curr->right );

	curr->right = NULL;

	return curr;

}

/***************************************************
 *
 * NOTE:
 *	对不同的应用问题，二叉树遍历操作时进行的操作不同的，
 *为了设计出通用的前序遍历二叉树 PreOrder(),把访问操作
 *操作设计成前序遍历二叉树的一个函数虚参数 Visit()。
 *
 *	以后类同！
 *
 ****************************************************/

void PreOrder( BiTreeNode *t, void Visit(BiTreeNode *t) )
{
	if( t != NULL )
	{
		Visit(t);
		PreOrder(t->left, Visit);
		PreOrder(t->right, Visit);
	}

}




void InOrder( BiTreeNode *t, void Visit(BiTreeNode *t) )
{
	if( t != NULL )
	{
	
		InOrder(t->left, Visit);
		Visit(t);
		InOrder(t->right, Visit);
	}

}


void PostOrder( BiTreeNode *t, void Visit(BiTreeNode *t) )
{
	if( t != NULL )
	{		
		PostOrder(t->left, Visit);
		PostOrder(t->right, Visit);
		Visit(t);
	}

}


/***************************************************************
 *
 * NOTE:
 *	设计借助堆栈的循环结束算法来代替递推法进行前序遍历。
 *
 ***************************************************************/

void PreOrder2( BiTreeNode *t, void Visit(BiTreeNode *t) )
{
	BiTreeNode *p;
	SeqStack s;

	StackInitiate(&s);

	StackPush(&s, t);

	while( StackNotEmpty(s) )
	{
		if( 0 == StackPop(&s, &p) )
		{
			printf("\nWrong when call the StackPop()!\n");
			return;
		}

		Visit(p);
		if( p->right != NULL )
			StackPush(&s, p->right);
		if( p->left != NULL )
			StackPush(&s, p->left);
	}
}

/***************************************************************
 *
 * NOTE:
 *	撤销操作的算法实际上是后序遍历的实际应用。
 *
 ***************************************************************/
void Destroy(BiTreeNode **root)
{
	if( *root != NULL && (*root)->left != NULL )
		Destroy(&(*root)->left);

	if( *root != NULL && (*root)->right != NULL )
		Destroy( &(*root)->right);

	*root = NULL;
	free(*root);
}



/***************************************************************
 *
 * NOTE:
 *	打印操作实际上是中序遍历的实际应用。
 *
 ***************************************************************/
void PrintBiTree(BiTreeNode *t, int n)
{
	int i;

	if( NULL == t )
		return;

	PrintBiTree(t->right, n+5);

	for( i = 1; i < n; i ++ )
		printf(" ");

	printf("---");
	printf("%c\n", t->data);


	PrintBiTree(t->left,n+5);


}


/***************************************************************
 *
 * NOTE:
 *	搜索操作实际上是前序遍历的实际应用。
 *
 ***************************************************************/

BiTreeNode *Search(BiTreeNode *t, DataTypeT x)
{
	BiTreeNode *p;

	if( NULL == t )
		return NULL;

	if( x == t->data )
		return t;
	
	if( t->left != NULL )
	{
		p = Search(t->left,x);

		if( NULL != p)
			return p;
	}

	if( t->right != NULL )
	{
		p = Search( t->right, x);

		if( p != NULL)
			return p;
	}

	return NULL;
}


/***************************************************************
 *
 * NOTE:
 *	利用队列的先进先出的特点，对二叉树进行层序遍历。
 *
 ***************************************************************/



void StraOrder( BiTreeNode *t, void Visit(BiTreeNode *t) )
{
	SeqQueue s;
	BiTreeNode *p = NULL;

	QueueInitiate(&s);

	QueueAppend(&s,t);
	
	while( QueueNotEmpty(s) )
	{
		if( 0 == QueueDelete(&s,&p) )
		{
			printf("\nWrong when call QueueDelete()!\n");
			return;
		}
		
		Visit(p);

		if( NULL != p->left )
			QueueAppend(&s,p->left);

		if( NULL != p->right )
			QueueAppend(&s,p->right);
	}

}

void GetLength(BiTreeNode *t, int *i, int length)
{
	if( NULL == t )
	{
		if( *i < length )
			*i = length -1;
		return;
	}
	else
	{
		length ++;

		GetLength(t->left, i, length);

		GetLength(t->right, i, length);
	}
}