binarytree.h

将森林转化为相应二叉树的算法

#define NULL 0
template <class T>class BinaryTreeNode;

template <class T>
class BinaryTree{
	private:
		BinaryTreeNode<T>* root;
		BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* root,
									BinaryTreeNode<T>* current);
	public:
		BinaryTree(BinaryTreeNode<T>* rt);
		BinaryTree(T*,int);
		~BinaryTree(){};
		bool isEmpty()const;
		BinaryTreeNode<T>* Root(){return root;};
		BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *current);
		BinaryTreeNode<T>* LeftSilbling(BinaryTreeNode<T>* current);
		BinaryTreeNode<T>* RightSilbling(BinaryTreeNode<T>* current);

		void CreatTree(const T& elem,BinaryTree<T>& leftTree,BinaryTree<T>& rightTree);
};
template<class T>
BinaryTree<T>::BinaryTree(T* elem,int n)
{
root=new BinaryTreeNode<T>[n];
int nodeNumber=1;
using std::queue;
queue<BinaryTreeNode<T>*> aQueue;
BinaryTreeNode<T>* pointer=(BinaryTreeNode<T>*)root;
aQueue.push(pointer);
for (int i=0;i<n;i++)
	{
	pointer=aQueue.front();
	pointer->setValue(elem[i]);
	if (nodeNumber<n)
		{
		pointer->setLeftchild(root+nodeNumber);
		aQueue.push(pointer->leftchild());
		nodeNumber++;
		}	
	if (nodeNumber<n)
		{
		pointer->setRightchild(root+nodeNumber);
		aQueue.push(pointer->rightchild());
		nodeNumber++;
		}	
	aQueue.pop();
	}
root=(BinaryTreeNode<T>*)root;

}
template<class T>
BinaryTree<T>::BinaryTree(BinaryTreeNode<T>* rt)
{
 root=rt;
}

template<class T>
class BinaryTreeNode{
	friend class BinaryTree;
	private:
		T element;
		BinaryTreeNode<T>* left;
		BinaryTreeNode<T>* right;
	public:
		BinaryTreeNode();
		BinaryTreeNode(const T& ele);
		BinaryTreeNode(const T& ele,
						BinaryTreeNode<T>* l,
						BinaryTreeNode<T> *r);
		T value()const;
		BinaryTreeNode<T>* leftchild() const;
		BinaryTreeNode<T>* rightchild() const;
		void setLeftchild(BinaryTreeNode<T>*);
		void setRightchild(BinaryTreeNode<T>*);
		void setValue(const T& val);
		bool isLeaf()const;
		BinaryTreeNode<T>& operator=(const BinaryTreeNode<T>& Node);
};

template<class T>
BinaryTreeNode<T>::BinaryTreeNode()
{
element=(T)0;
left=right=NULL;
}
template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T &ele)
{
element=ele;
left=right=NULL;
}
template<class T>
void BinaryTreeNode<T>::setLeftchild(BinaryTreeNode<T> *Node)
{
left=Node;
}

template<class T>
void BinaryTreeNode<T>::setRightchild(BinaryTreeNode<T> *Node)
{
right=Node;
}
template<class T>
void BinaryTreeNode<T>::setValue(const T& val)
{
element=val;
}
template<class T>
BinaryTreeNode<T>* BinaryTreeNode<T>::leftchild() const
{
return left;
}
template<class T>
BinaryTreeNode<T>* BinaryTreeNode<T>::rightchild() const
{
return right;
}
template<class T>
T BinaryTreeNode<T>::value() const
{
return element;
}