bintree.cpp

常用算法与数据结构原代码

#include <iostream.h>

typedef struct node{
	int data;
	node *lchild;
	node *rchild;
} TNODE;

TNODE *static_search(TNODE *t,int key)
{
	while (t!=NULL)
		if (t->data==key)
			return t;
		else
			if (key<t->data)
				t=t->lchild;
			else
				t=t->rchild;
	return NULL;
}

void dynamic_search(TNODE *t,int key,TNODE *&pkpt,TNODE *&kpt)
{
	pkpt=NULL;
	kpt=t;
	while (kpt!=NULL)
	{
		if (kpt->data==key)
			return;
		pkpt=kpt;
		if (key<kpt->data)
			kpt=kpt->lchild;
		else
			kpt=kpt->rchild;
	}
}

int insert(TNODE *&pt,int key)
{
	TNODE *p,*q,*r;
	dynamic_search(pt,key,p,q);
	if (q!=NULL)
		return 1;
	r=new TNODE;
	r->data=key;
	r->lchild=r->rchild=NULL;
	if (p==NULL)
		pt=r;
	else
		if (p->data>key)
			p->lchild=r;
		else
			p->rchild=r;
	return 0;
}

int del(TNODE *&pt,int key)
{
	TNODE *p,*q,*r;
	dynamic_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;
		}
	delete q;
	return 0;
}