bitree.cpp

C++写的二叉树类

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

#include "stdafx.h"
#include "BiTree.h"

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

Tree::Tree()
{
	lchild=rchild=NULL;
	data=0;
}

Tree::InOrderTraverse(BiTree T)
{
	if(T)
	{
		InOrderTraverse(T->lchild);
		cout<<T->data<<"    ";
		InOrderTraverse(T->rchild);
	}
	return 0;
}

Tree::~Tree()
{

}

int Tree::SearchBST(BiTree T,int key,BiTree f,Tree **p)
{
	if(! T)	{*p=f;return 0;}	//查找不成功
	else if(key==T->data)	{*p=T;return 1;}
	else if(key<T->data)	SearchBST(T->lchild,key,T,p);
	else SearchBST(T->rchild,key,T,p);
}


int Tree::InsertBST(Tree **T, int key)
{
	BiTree p,s;
	if(! SearchBST(*T,key,NULL,&p))
	{
		s=new Tree;
		s->data=key;
		if(! p) *T=s;
		else if(key<p->data) p->lchild=s;
		else p->rchild=s;
		return 1;
	}
	else return 0;
}

int Tree::DeleteBST(Tree **T,int key)
{
	if(! *T) return 0;
	else {
		if(key==(*T)->data)	{Delete(T);return 1;}
		else if (key<(*T)->data) DeleteBST(&(*T)->lchild,key);
		else DeleteBST(&(*T)->rchild,key);
	}
}

void Tree::Delete(Tree **p)
{
	BiTree q,s;
	if(! (*p)->rchild){
		q=*p;*p=(*p)->lchild;delete q;
	}
	else if(! (*p)->lchild){
		q=*p;*p=(*p)->rchild ;delete q;
	}
	else{
		q=*p;s=(*p)->lchild;
		while(s->rchild) {q=s;s=s->rchild;}
		(*p)->data=s->data;
		if(q!=*p)	q->rchild=s->lchild;
		else	q->lchild=s->lchild;
	}
}

void Tree::ASL(Tree* T,int level,int &TotalLen,int &n)
{
	if(T)
	{
		TotalLen+=level;
		n++;
		ASL(T->lchild,level+1,TotalLen,n);
		ASL(T->rchild,level+1,TotalLen,n);
	}
}