学步园

下面代码仅供本人复习数据结构所用，实用性N低，各位飘过吧~~哈哈:>

//
// C++ 模版技术实现简单二叉树. 
//

#include <cstdlib>
#include <cstring>
#include <iostream>

// 二叉树类模版前置声明
template <typename T> class BinaryTree; 

//
// 二叉树节点类模版. 
//
template <typename T>
class Node
{
	friend class BinaryTree<T>;
private:
	T _data;
	Node<T> *_pLeftChild, *_pRightChild;
	
public:
	Node(const T &data)
		: _data(data)
		, _pLeftChild(NULL)
		, _pRightChild(NULL)
	{ NULL; }
};

//
// 二叉树类模版 
//
template <typename T> 
class BinaryTree
{
private:
	Node<T> *_pRoot;
	
private:
	void _create(Node<T> **ppRoot, T **ppArray, int *piSize, const T &delim);
	void _clear(Node<T> *pRoot);
	void _preOrder(Node<T> *pRoot) const;
	void _inOrder(Node<T> *pRoot) const;
	void _postOrder(Node<T> *pRoot) const; 
	size_t _height(Node<T> *pRoot) const; 
	size_t _count(Node<T> *pRoot) const; 
	
public:
	// 遍历类型. 
	enum TraversalType {
		PRE_ORDER,
		IN_ORDER,
		POST_ORDER	
	};
	
public:
	BinaryTree(T *array, int size, const T &delim);
	~BinaryTree(void);
	void traversal(const TraversalType type) const;
	size_t getHeight(void) const;
	size_t getNumberOfNode(void) const;
};

//
// 创建二叉树.
// 这里基于前序遍历构造二叉树，输入的是二叉树的先序序列， 
// 但必须在其中加入虚节点以表示空指针的位置. 
// 例如： 
//             (A)
//           /    \
//        (B)     (C)
//       /   \   /   \
//     (D)   %  (E)  (F)
//    /  \     /  \  / \
//   %   %    %   % %   %
//
// 其中字母代表节点，% 代表虚节点，故上图先序序列为：ABD%%%CE%%F%%. 
//
// 参数 ppRoot 是指向根指针的指针，故修改 *ppRoot 就修改了实参（根指针）本身.
// 参数 ppArray 是指向存储先序序列数组地址的指针，我们也需要必要的修改.
// 参数 piSize 是指向表示数组大小的整型变量的指针，我们也需要修改它. 
// 参数 delim 是分隔符，用来指代虚节点，我们需要跳过虚节点。 
// 
template <typename T>
void BinaryTree<T>::_create(Node<T> **ppRoot, 
							T **ppArray, 
							int *piSize,
							const T &delim)
{
	if (0 < *piSize && delim != **ppArray) 
	{
		*ppRoot = new Node<T>(**ppArray);
		_create(&((*ppRoot)->_pLeftChild), &(++*ppArray), &(--*piSize), delim);
		_create(&((*ppRoot)->_pRightChild), &(++*ppArray), &(--*piSize), delim);
	}
}
//
// 删除所有节点. 
//
template <typename T> 
void BinaryTree<T>::_clear(Node<T> *pRoot)
{
	if (NULL != pRoot)
	{
		_clear(pRoot->_pLeftChild);
		_clear(pRoot->_pRightChild);
		delete pRoot;
	}
}

//
// 前序遍历. 
//
template <typename T> 
void BinaryTree<T>::_preOrder(Node<T> *pRoot) const
{
	if (NULL != pRoot)
	{
		std::cout << pRoot->_data << " ";
		_preOrder(pRoot->_pLeftChild);
		_preOrder(pRoot->_pRightChild);
	}
}

//
// 中序遍历. 
//
template <typename T> 
void BinaryTree<T>::_inOrder(Node<T> *pRoot) const
{
	if (NULL != pRoot)
	{
		_inOrder(pRoot->_pLeftChild);
		std::cout << pRoot->_data << " ";
		_inOrder(pRoot->_pRightChild);
	}
}

//
// 后序遍历. 
//
template <typename T> 
void BinaryTree<T>::_postOrder(Node<T> *pRoot) const
{
	if (NULL != pRoot)
	{
		_postOrder(pRoot->_pLeftChild);
		_postOrder(pRoot->_pRightChild);
		std::cout << pRoot->_data << " ";
	}
}

//
// 通过后序遍历方式计算二叉树高度. 
//
template <typename T> 
size_t BinaryTree<T>::_height(Node<T> *pRoot) const
{
	static size_t height = 0, leftHeight = 0, rightHeight = 0;
	
	if (NULL != pRoot)
	{
		leftHeight = _height(pRoot->_pLeftChild);
		rightHeight = _height(pRoot->_pRightChild);
		
		height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
	}
	else {
		height = 0;
	}
	
	return height;
}

//
// 通过前序遍历方式计算二叉树节点数. 
//
template <typename T> 
size_t BinaryTree<T>::_count(Node<T> *pRoot) const
{
	static size_t counter = 0;
	
	if (NULL != pRoot) {
		counter = _count(pRoot->_pLeftChild) + _count(pRoot->_pRightChild) + 1;
	}
	else {
		counter = 0;
	}
	return counter;
}


template <typename T> 
inline BinaryTree<T>::BinaryTree(T *array, int size, const T &delim)
{ 
	_create(&_pRoot, &array, &size, delim);
}


template <typename T> 
inline BinaryTree<T>::~BinaryTree(void)
{
	_clear(_pRoot);
}

//
// 根据控制标识选择遍历方式. 
// 
template <typename T> 
void BinaryTree<T>::traversal(const TraversalType type) const
{
	switch (type)
	{
		case PRE_ORDER  :	_preOrder(_pRoot);	break;
		case IN_ORDER   :	_inOrder(_pRoot);	break;	
		case POST_ORDER :	_postOrder(_pRoot);	break;
	}
}


template <typename T> 
size_t BinaryTree<T>::getHeight(void) const
{
	return _height(_pRoot);
}


template <typename T> 
size_t BinaryTree<T>::getNumberOfNode(void) const
{
	return _count(_pRoot);
}

//
// 测试二叉树. 
//
int main(void)
{
	const size_t MAX_SIZE = 100;
	char szPreOrder[MAX_SIZE] = {'\0'};
	
	std::cout << "请输入二叉树节点数据前序序列：" << std::endl; 
	while (!std::cin.getline(szPreOrder, MAX_SIZE))
	{
		std::cout << "输入错误. " << std::endl;
		std::cout << "重新输入: ";
		std::cin.clear();
		std::cin.sync();	
	}
	
	BinaryTree<char> binTree(szPreOrder, strlen(szPreOrder), ' ');
	
	//
	// 遍历二叉树. 
	//
	std::cout << "前序遍历：";
	binTree.traversal(BinaryTree<char>::PRE_ORDER);
	std::cout << std::endl << "中序遍历：";
	binTree.traversal(BinaryTree<char>::IN_ORDER);
	std::cout << std::endl << "中序遍历：";
	binTree.traversal(BinaryTree<char>::POST_ORDER);
	std::cout << std::endl;
	
	std::cout << "树高：" << binTree.getHeight() << std::endl; 
	std::cout << "节点：" << binTree.getNumberOfNode() << std::endl; 
	
	return EXIT_SUCCESS;
}