binarytree.cpp

数据结构测试程序

// binarytree.cpp: implementation of the binarytree class.
//
//////////////////////////////////////////////////////////////////////

#include "binarytree.h"
#include "stdio.h"
#include "stdlib.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

binarytree::binarytree()
{

}
 
binarytree::~binarytree()
{

}

void binarytree::initbtree(binarytree *bt) //初始化二叉树
{
	elemtpb x;
	if (bt!=NULL)
	{
		scanf("%c",&x);
		if (x!=NIL)
		{
			bt=new binarytree;
			bt->elem=x;
			initbtree(bt->lchild);
			initbtree(bt->rchild);
		}
		else	bt=NULL;
	}

}

void binarytree::preorder(binarytree *t)//先序遍历
{
	if (t!=NULL)
	{
		printf("%c",t->elem);
		preorder(t->lchild);
		preorder(t->rchild);
	}

}

void binarytree::midorder(binarytree *t)//中序遍历
{
	if (t!=NULL)
	{
		midorder(t->lchild);
		printf("%c",t->elem);
		midorder(t->rchild);
	}
}

void binarytree::posorder(binarytree *t)//后序遍历
{
	if (t!=NULL)
	{
		posorder(t->lchild);
		printf("%c",t->elem);
		posorder(t->rchild);
	}

}

void binarytree::search(binarytree *t, char key, binarytree **pkpt, binarytree **kpt)
{
	*pkpt=NULL;
	*kpt=t;
	while (*kpt!=NULL){
		if((*kpt)->elem==key)return;
		*pkpt=*kpt;
		if(key<(*kpt)->elem) *kpt=(*kpt)->lchild;
		else *kpt=(*kpt)->rchild;
	}
	
}

int binarytree::insert(binarytree **pt, char key)
{
	binarytree *p,*q,*r;
	search(*pt,key,&p,&q);
	if(q!=NULL) return 1;
	r=(binarytree*)malloc(sizeof(binarytree));
	r->elem=key;
	r->lchild=r->rchild=NULL;
	if(p==NULL)*pt=r;
	else if (p->elem>key)
		p->lchild=r;
	else p->rchild=r;
	return 0;
	
}

int binarytree::deleteb(binarytree **pt, char key)
{
	binarytree *p,*q,*r;
	search(*pt,key,&p,&q);
	if (q==NULL)return 1;
	if (p==NULL)
		if (q->lchild==NULL)
			*pt=q->rchild;
		else{
			*pt=q->lchild;
			r=q->lchild;
			while (r->rchild!=NULL)
				r=r->rchild;
			r->rchild=q->rchild;
		}
	else if (q->lchild==NULL)
		if (q==p->lchild)
			p->lchild=q->rchild;
		else
			p->rchild=q->rchild;
		else{
			r=q->lchild;
			while(r->rchild!=NULL)r=r->rchild;
			r->rchild=q->rchild;
			if (q==p->lchild)
				p->lchild=q->lchild;
			else
				p->rchild=q->lchild;
		}
		free(q);
		return 0;

}