bisearch.cpp

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

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

template <class T> class BiSearchTree
{
	private:
		BiTreeNode<T> *root;
		void PreOrder(BiTreeNode<T> *t, void (*visit)(T item));
		void InOrder(BiTreeNode<T> *t, void (*visit)(T item));
		void PostOrder(BiTreeNode<T> *t, void (*visit)(T item));
		BiTreeNode<T> *SearchParent(BiTreeNode<T> *root, BiTreeNode<T> *current);
	public:
		BiSearchTree():root(NULL){};
		~BiSearchTree(){};
		void MakeTree(const T &item, BiSearchTree<T> &left, BiSearchTree<T> &right);
		void BreakTree(T &item, BiTreeNode<T> &left, BiTreeNode<T> &right);

		void PreOrder(void (*visit)(T item))
			{PreOrder(root, visit);}
		void InOrder(void (*visit)(T item))
			{InOrder(root, visit);}
		void PostOrder(void (*visit)(T item))
			{PostOrder(root, visit);}

		const BiTreeNode<T> *GetRoot()const
			{return root;}
//		BiTreeNode<T> *Current(BiTreeNode<T> *t);
		BiTreeNode<T> *Parent(BiTreeNode<T> *current);
		BiTreeNode<T> *LeftChild(BiTreeNode<T> *current)
			{return root != NULL ? current->Left() : NULL;}
		BiTreeNode<T> *RightChild(BiTreeNode<T> *current)
			{return root != NULL ? current->Right() : NULL;}

		int Insert(BiTreeNode<T>* &current, const T &item);
//		int Find(const T &item);

		friend istream &operator>> (istream &in, BiSearchTree<T> *tree);
};

template <class T>
void BiSearchTree<T>::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 BiSearchTree<T>::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 BiSearchTree<T>::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 BiSearchTree<T>::MakeTree(const T &item, BiSearchTree<T> &left, BiSearchTree<T> &right)
{
	root = new BiTreeNode<T>(item, left.root, right.root);
	left.root = right.root = NULL;
}

template <class T>
void BiSearchTree<T>::BreakTree(T &item, BiTreeNode<T> &left, BiTreeNode<T> &right)
{
	if(root != NULL)
	{
		item = root->data;
		left.root = root->leftChild;
		right.root = root->rightChild;

		delete root;
		root = NULL;
	}
}

template <class T>
BiTreeNode<T> *BiSearchTree<T>::Parent(BiTreeNode<T> *current)
{	
	SearchParent(root, current);
}

template <class T>
BiTreeNode<T> *BiSearchTree<T>::SearchParent(BiTreeNode<T> *root, BiTreeNode<T> *current)
//在树root中回溯查找结点current的双亲结点。
//查找到时返回current结点的双亲结点；否则返回空结点
{
	if(root == NULL) return NULL;
	if(root->Left() == current || root->Right() == current)
		return root;
	BiTreeNode<T> *p;
	if((p = SearchParent(root->Left(), current)) != NULL)  return p;
	if((p = SearchParent(root->Right(), current)) != NULL) return p;
	return NULL;
}

template <class T>
istream &operator>> (istream &in, BiSearchTree<T> *tree)
{
	T item;
	in >> item;
	while(item != StopMark)
	{
		tree.Insert(item);
		in >> item;
	}
	return in;
}

template <class T>
int Insert(const T &item)
{
	
}

template <class T>
void Visit(T item)
{
	cout << item << "   ";
}

void main(void)
{
	BiSearchTree<char> a, b, c, d, e, f, g, null;
	g.MakeTree('G', null, null);
	d.MakeTree('D', null, g);
	b.MakeTree('B', d, null);
	e.MakeTree('E', null, null);
	f.MakeTree('F', null, null);
	c.MakeTree('C', e, f);
	a.MakeTree('A', b, c);

	a.PostOrder(Visit);
}