数据结构与算法_二叉树

BinaryTree.h

#pragma once
#include <iostream>
#include "queue"
using namespace std;

template<class T> class BinaryTree;	//前置声明

template<class T>
class TreeNode
{
	friend class BinaryTree<T>;
public:
	TreeNode()
		{
			leftChild = NULL;
			rightChild = NULL;
		}
//private:
	T data;
	TreeNode<T> *leftChild;
	TreeNode<T> *rightChild; 
	
} ;


template<class T>
class BinaryTree
public:
	//二叉树可以进行的操作
	//void InOrder();		//中序遍历
	void InOrder(TreeNode<T> *CurNode);
	void PreOrder();	//先序遍历
	void PreOrder(TreeNode<T>* CurNode); 
	void PostOrder();	//后序遍历
	void PostOrder(TreeNode<T>* CurNode); 
	void LevelOrder();	//层序遍历 
	
	void Visit(TreeNode<T> *CurNode);	//显示当前节点的数据 
public:
	TreeNode<T> *root;	
};

template<class T>
void BinaryTree<T>::Visit(TreeNode<T> *CurNode)
{
	cout << CurNode->data << "  " ;
}

/**********************中序遍历**************************/
//template<class T>
//void BinaryTree<T>::InOrder()
//{
//	InOrder(root);
//}
template<class T>
void BinaryTree<T>::InOrder(TreeNode<T>* CurNode)
{
	if(CurNode)
	{
		InOrder(CurNode->leftChild);
		//显示当前节点
		Visit(CurNode);
		InOrder(CurNode->rightChild); 
	}
}
/**********************先序遍历**************************/
template<class T>
void BinaryTree<T>::PreOrder()
{
	PreOrder(root);
}
template<class T>
void BinaryTree<T>::PreOrder(TreeNode<T>* CurNode)
{
	if(CurNode)
	{
		//显示当前节点
		Visit(CurNode);
		PreOrder(CurNode->leftChild);	
		PreOrder(CurNode->rightChild); 
	}		
}
/**********************后序遍历**************************/
template<class T>
void BinaryTree<T>::PostOrder()
{
	PostOrder(root);
}
template<class T>
void BinaryTree<T>::PostOrder(TreeNode<T>* CurNode)
{
	if(CurNode)
	{
		
		PostOrder(CurNode->leftChild);	
		PostOrder(CurNode->rightChild); 
		//显示当前节点
		Visit(CurNode);
	}		
}
/**********************层序遍历**************************/
template<class T>
void BinaryTree<T>:: LevelOrder()
{
	queue<TreeNode<T>*> queue;
	TreeNode<T>* CurNode = root;
	while(CurNode)
	{
		Visit(CurNode);	//先显示根节点的数据
		if(CurNode->leftChild)	//再分别检查有没有左右子树，如果有，放入队列 
			queue.push(CurNode->leftChild); 
		if(CurNode->rightChild)
			queue.push(CurNode->rightChild);
		if(queue.empty())
			return ;
		CurNode = queue.front();//再从队列中取出第一个作为新的根节点 
		queue.pop();
		
	}
}

main.h

#include <iostream>
#include "BinaryTree.h"

using namespace std;

int main()
{
	BinaryTree<char> tree;  
	TreeNode<char> add, sub, mul, div, a, b,c,d,e,f,g;
	add.data = '+';
	sub.data = '-';
	mul.data = '*';
	div.data = '/';
	a.data = 'A';
	b.data = 'B';
	c.data = 'C';
	d.data = 'D';
	e.data = 'E';
	
	tree.root = &add;
	
	add.leftChild = &sub;
	add.rightChild = &e;
	sub.leftChild = &mul;
	sub.rightChild = &d;
	mul.leftChild = &div;
	mul.rightChild = &c;
	div.leftChild = &a;
	div.rightChild = &b;
	
	cout << "中序遍历：" ;
	tree.InOrder(tree.root);
	cout << endl; 
	
	cout << "先序遍历: " ;
	tree.PreOrder();	
	cout << endl; 
	
	cout << "后序遍历: " ;
	tree.PostOrder();	
	cout << endl; 
	
	cout << "层序遍历: " ;
	tree.LevelOrder();	
	cout << endl; 
	
	return 0;
}