binary.h

一个最简单的二叉树的算法

#include "stdafx.h"
#include <iostream>
#include "LinkNode.h"
#include "LinkQuee.h"
#include "node.h"
using namespace std;
template <class T>
class BinaryTree
{
public:
	BinaryTree(){root = 0;}
	~BinaryTree(){};
	bool IsEmpty()const
	{
		return ((root)? false : ture);
	}
	bool Root(T &x) const;
	void MakeTree(const T &value,BinaryTreeNode<T>*);
//	void BreakTree(T &value, BinaryTree<T> &left,BinaryTree<T> &right);
	void PreOrderH(BinaryTreeNode<T> *u)
	{
		u = root;
		PreOrder(u);
	}
	void InOrderH(BinaryTreeNode<T> *u)
	{
		u = root;
		InOrder(u);
	}
	void PostOrderH(BinaryTreeNode<T> *u)
	{
		u = root;
		PostOrder(u);
	}
	void LevelOrder(BinaryTreeNode<T> *u);
private:
	BinaryTreeNode<T> *root;
	void PreOrder(BinaryTreeNode<T>*t);
	void InOrder(BinaryTreeNode<T>*t);
	void PostOrder(BinaryTreeNode<T>*t);
};
template<class T>
bool BinaryTree<T>::Root(T &x)const
{
	if(root)
	{
		x = root ->data;
		return true;
	}
	else
		return false;
}
template<class T>
void BinaryTree<T>::MakeTree(const T &value,BinaryTreeNode<T> *ptr)
{
	
	ptr = root;
	if(ptr == NULL)
	{
		ptr = new BinaryTreeNode<T>(value);
	}
	else 
	{if(ptr->data>value)
		MakeTree(value,ptr->Left);
	else MakeTree(value,ptr->Right);
	}
}
/*template<class T>
void BinaryTree<T>::BreakTree(T &value, BinaryTree<T> &left,BinaryTree<T> &right)
{
	value = root ->data;
	left.root = root ->Left;
	right.root = root ->Right;
	delete root;
	root = 0;
}*/
template<class T>
void BinaryTree<T>::PreOrder(BinaryTreeNode<T> *t)
{
	if(t != NULL)
	{
		cout << t->data;
		Preorder(t->LeftChild);
		Preorder(t->RightChild);
	}
}
template <class T>
void BinaryTree<T>::InOrder(BinaryTreeNode<T> *t)
{
	if (t != NULL) 
	{
		InOrder(t->LeftChild);
		cout << t->data;
		InOrder(t->RightChild);
	}
}
template <class T>
void BinaryTree<T>::PostOrder(BinaryTreeNode<T> *t)
{
	if (t != NULL) 
	{
		PostOrder(t->LeftChild);
		PostOrder(t->RightChild);
		cout << t->data;
	}
}

template<class T>
void BinaryTree<T>::LevelOrder(BinaryTreeNode<T> *u)
{
	LinkedQueue<BinaryTreeNode<T>*> Q;
	u = root;
	while (t != NULL) {
		cout << u->data;
		if (u->Left) 
			Q.Add(u->Left);
		if (u->Right) 
			Q.Add(u->Right);
		try {Q.Delete(u);}
		catch (OutOfBounds) 
		{return;}
	}
}