_b_tree.cpp

用C++实现线索二叉树 教学或者自学均可使用 简单方便

// _B_TREE.cpp: implementation of the C_B_TREE class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "tree.h"
#include "_B_TREE.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

C_B_TREE::C_B_TREE()
{
	hbt.lptr=hbt.rptr=NULL;
	hbt.e=65535;
}

C_B_TREE::~C_B_TREE()
{

}

void C_B_TREE::insert_elem(ELEM_TYPE e)
{
	NODE *p,*s;
	s=(NODE *)malloc(sizeof(NODE));
	s->e=e;
	s->lptr=s->rptr=NULL;

	p=&hbt;
	for(;;)
	{
		if(e < p->e)
		{
			if(p->lptr)
				p=p->lptr;
			else
			{
				p->lptr=s;
				break;
			}
		}
		else
		{
			if(p->rptr)
				p=p->rptr;
			else
			{
				p->rptr=s;
				break;
			}
		}
	}
}





void C_B_TREE::visit(NODE *subbt,CListBox *mbox)
{
	CString str;
	if(subbt)
	{
		visit(subbt->lptr,mbox);
		str.Format("%6d",subbt->e);
		mbox->AddString(str);
		visit(subbt->rptr,mbox);
	}
}


NODE * C_B_TREE::get_root_node()
{
	return hbt.lptr;
}

void C_B_TREE::xs_tree()
{
	NODE *pf=&hbt;
	if(hbt.lptr)
	{
		xs_visit(&pf,hbt.lptr);
		pf->rptr=&hbt;
		pf->rflg=1;
	}
	else
	{
		hbt.rflg=hbt.lflg=1;
		hbt.lptr=hbt.rptr=&hbt;
	}
}

void C_B_TREE::xs_visit(NODE **pre,NODE *p)
{
	if(p)
	{
		xs_visit(pre,p->lptr);
		if(p->lptr)
			p->lflg=0;			//指向左子女

		if(!p->lptr)
		{
			p->lflg=1;			//指向前驱
			p->lptr=pre[0];
		}

		if(!pre[0]->rptr)
		{
			pre[0]->rflg=1;			//指向后继
			pre[0]->rptr=p;
		}

		pre[0]=p;
		xs_visit(pre,p->rptr);
		if(p->rptr)
			p->rflg=0;			//指向右子女

	}
}