bitreelib.h

数据结构c++-书的一些源代码

#include <iostream.h>
#include <stdlib.h>
#include "LinQueue.h"

template <class T> class BiTreeNode
{
	private:
		BiTreeNode<T> *leftChild;
		BiTreeNode<T> *rightChild;
	public:
		T data;
		BiTreeNode():leftChild(NULL), rightChild(NULL){}
		BiTreeNode(const T& item, BiTreeNode<T> *left = NULL, BiTreeNode<T> *right = NULL):
			data(item), leftChild(left), rightChild(right){}
		~BiTreeNode(){}

		BiTreeNode<T> *Left(void)const
			{return leftChild;}
		BiTreeNode<T> *Right(void)const
			{return rightChild;}
};

template <class T>
BiTreeNode<T> *GetTreeNode(T item, BiTreeNode<T> *left = NULL, BiTreeNode<T> *right = NULL)
{
	BiTreeNode<T> *p;
	p = new BiTreeNode<T> (item, left, right);
	
	if(p == NULL)
	{
		cerr << "内存分配失败!\n";
		exit(1);
	}
	return p;
}

template <class T>
void PrintTree(BiTreeNode<T> *t, int level)
{
	if(t!=NULL)
	{
		PrintTree(t->Right(),level+1);
		if(level!=0)
		{
			for(int i = 0; i < 6*(level-1); i++) cout<<" ";
			cout<<"  ----";
		}
		cout<<t->data<<endl;
		PrintTree(t->Left(),level+1);
	}
}

template <class T>
void Preorder(BiTreeNode<T> *t,void visit(T item))
{
	if(t!=NULL)
	{
		visit(t->data);
		Preorder(t->Left(),visit);
		Preorder(t->Right(),visit);
	}
}

template <class T>
void Inorder(BiTreeNode<T> *t,void visit(T item))
{
	if(t!=NULL)
	{
		Inorder(t->Left(),visit);
		visit(t->data);
		Inorder(t->Right(),visit);
	}
}

template <class T>
void Postorder(BiTreeNode<T> *t,void visit(T item))
{
	if(t!=NULL)
	{
		Postorder(t->Left(),visit);
		Postorder(t->Right(),visit);
		visit(t->data);
	}
}

template <class T>
void LevelScan(BiTreeNode<T> *t,void visit(T item))
{
	LinQueue<BiTreeNode<T>*> q;
	BiTreeNode<T> *p;
	q.QInsert(t);
	
	while(!q.QueueEmpty())
	{
		p=q.QDelete();
		visit(p->data);
		if(p->Left()!=NULL) q.QInsert(p->Left());

		if(p->Right()!=NULL) q.QInsert(p->Right());
	}
}

template <class T>
void CountLeaf(BiTreeNode<T> *t,int& count)
{
	if(t!=NULL)
	{
		CountLeaf(t->Left(),count);
		CountLeaf(t->Right(),count);
		if(t->Left()==NULL && t->Right()==NULL)
		count++;
	}
}

template <class T>
int Depth(BiTreeNode<T> *t)
{
	int depthleft,depthright,depthval;

	if(t==NULL) depthval=-1;
	else
	{
		depthleft=Depth(t->Left());
		depthright=Depth(t->Right());
		depthval=1+(depthleft>depthright ? depthleft:depthright);
	}
	return depthval;
}

//const indentunit = 6;
void IndentBlanks(int num)
{
	for(int i=0;i<num;i++)
	cout<<" ";
}
 
struct Info
{
	int xIndent,yLevel;
};

#include <math.h>

template <class T>
void PrintVTree(BiTreeNode<T> *t)
{
	int dataWidth = 2;
	int screenWidth = 64;
	LinQueue<BiTreeNode<T> *> Q;
	LinQueue<Info> QI;
	BiTreeNode<T> *p;
	Info    s,s1,s2;
	int offset, level = -1, len, i;
                                
	Q.QInsert(t);
	s.xIndent = screenWidth / dataWidth;
	s.yLevel = 0;
	QI.QInsert(s);
	while(!Q.QueueEmpty() && !QI.QueueEmpty())
	{
		s2 = s; //new add
		p = Q.QDelete();
		s = QI.QDelete();

		if(s.yLevel != level)
		{
			cout << "\n第" << s.yLevel << "层";
			level = s.yLevel;
			for(i = 0; i < s.xIndent-1; i++) cout<<" ";
		}
		else
		for(i = 0; i < s.xIndent - s2.xIndent; i++) cout<<" ";

		cout << p->data;
		if(p->Left() != NULL)
		{
			Q.QInsert(p->Left());
			s1.yLevel = s.yLevel + 1;
			offset = screenWidth / pow(dataWidth, s1.yLevel + 1);
			s1.xIndent = s.xIndent - offset;
			QI.QInsert(s1);
		}
		if(p->Right() != NULL)  
		{
			Q.QInsert(p->Right());
			s1.yLevel = s.yLevel + 1;
			offset = screenWidth / pow(dataWidth, s1.yLevel + 1);
			s1.xIndent = s.xIndent + offset;
			QI.QInsert(s1);
		}
	}
}

template <class T>
BiTreeNode<T> *Find(BiTreeNode<T> *root, T item)
{
	if(root == NULL) return NULL;
	if(root->data == item || root->data == item)
		return root;
	BiTreeNode<T> *p;
	if((p = Find(root->Left(), item)) != NULL) return p;
	if((p = Find(root->Right(), item)) != NULL) return p;
	return NULL;
}