bitreenode.h

《数据结构-使用C语言》第三版

//二叉链存储结构的二叉树操作实现 
typedef struct Node 
{
	DataType data;
	struct Node *leftChild;
	struct Node *rightChild;
}BiTreeNode;

void Initiate(BiTreeNode **root)
{
	*root=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	(*root)->leftChild=NULL;
	(*root)->rightChild=NULL;
}

BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)
{
	BiTreeNode *s, *t;
	
	if(curr==NULL)return NULL;
	t=curr->leftChild;
	s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	s->data=x;
	s->leftChild=t;
	s->rightChild=NULL;
	
	curr->leftChild=s;
	return curr->leftChild;
}

BiTreeNode * InsertRightNode(BiTreeNode *curr, DataType x)
{
	BiTreeNode *s, *t;
	
	if(curr==NULL)return NULL;
	
	t=curr->rightChild;
	s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	s->data=x;
	s->rightChild=t;
	s->leftChild=NULL;
	
	curr->rightChild=s;
	return curr->rightChild;
}
//撤销
void Destroy(BiTreeNode **root)
{
	if((*root)!=NULL && (* root)->leftChild != NULL)
	Destroy(&(*root)->leftChild);
	
	if((*root)!=NULL && (* root)->rightChild != NULL)
	Destroy(&(*root)->rightChild);
	
	free(*root);
}

BiTreeNode * DeleteLeftTree(BiTreeNode *curr)
{
	if(curr==NULL || curr->leftChild==NULL)return NULL;
	
	Destroy(&curr->leftChild);
	curr->leftChild=NULL;
	return curr;
}

BiTreeNode * DeleteRightTree(BiTreeNode *curr)
{
	if(curr==NULL || curr->rightChild==NULL)return NULL;
	
	Destroy(&curr->rightChild);
	curr->rightChild=NULL;
	return curr;
}

//遍历 

void PreOrder(BiTreeNode *t, void Visit(DataType item))
{
	if(t!=NULL)
	{
		Visit(t->data);
		PreOrder(t->leftChild, Visit);
		PreOrder(t->rightChild, Visit);
	}
}

void InOrder(BiTreeNode *t, void Visit(DataType item))
{
	if(t!=NULL)
	{
		InOrder(t->leftChild, Visit);
		Visit(t->data);
		InOrder(t->rightChild, Visit);
	}
}

void PostOrder(BiTreeNode *t, void Visit(DataType item))
{
	if(t!=NULL)
	{
		PostOrder(t->leftChild, Visit);
		PostOrder(t->rightChild, Visit);
		Visit(t->data);
	}
}

//应用:打印和查找
void PrintBiTree(BiTreeNode *bt, int n)
{
	int i;
	if(bt==NULL)return ;
	PrintBiTree(bt->rightChild, n+1);
	
	for(i=0;i<n;i++)printf("    ");
	if(n>=0)
	{
		printf("---");
		printf("%c\n",bt->data);
	}
	PrintBiTree(bt->leftChild, n+1);
}

BiTreeNode *Search(BiTreeNode *bt, DataType x)
{
	BiTreeNode *p;
	if(bt==NULL)return NULL;
	if(bt->data==x)return bt;
	
	if(bt->leftChild!=NULL)
	{
		p=Search(bt->leftChild, x);
		if(p!=NULL)return p;
	}
	if(bt->rightChild!=NULL)
	{
		p=Search(bt->rightChild, x);
		if(p!=NULL)return p;
	}
	return NULL;
}