算法导论：10.4-2 给定一个二叉树，写出一个 O(n) 时间的递归过程，将该树每个结点的关键字输出。

#ifndef _BINARY_TREE_H_
#define _BINARY_TREE_H_

/*****************************************************
算法导论：10.4-2 一个二叉树，使用递归输出每个结点
******************************************************/

#include <iostream>

template <class T>
class BinaryTree;

template <class T>
class BinaryTree
{
public:
	class Node{
	public:
		friend class BinaryTree < T >;
		T value;
	private:
		Node() :_parent(nullptr), _left(nullptr), _right(nullptr){}
		Node(const T& v) :_parent(nullptr), _left(nullptr), _right(nullptr), value(v){}
		Node* _parent;
		Node* _left;
		Node* _right;
	};

	BinaryTree() :_root(nullptr){  }
	// 使用一个数组构造一个完全二叉树，给出数组的头指针和数组的长度
	BinaryTree(T*, size_t);
	~BinaryTree();

	Node *getRoot()const{ return _root; }

	void print() const;

private:
	// 二叉树的根结点
	Node* _root;

	void freeNodes(const Node* root);
	void print(const Node*) const;
	void createTree(Node *root, T* a, size_t pos, size_t size);
};

template <class T>
BinaryTree<T>::BinaryTree(T* a, size_t size){
	_root = new Node(a[0]);
	createTree(_root, a, 0, size);
}

template<class T>
void BinaryTree<T>::createTree(Node *root, T* a, size_t pos, size_t size){
	// 将数组中的元素按照顺序加入到二叉树中
	// 左子树坐标，左子数的坐标为 2 * pos + 1
	size_t pos_left = 2 * pos + 1;
	// 右子树坐标，右子树的坐标为 2 * pos + 2
	size_t pos_right = pos_left + 1;
	// 创建根结点
	if(pos_left < size){
		// 创建左子树
		root->_left = new Node(a[pos_left]);
		createTree(root->_left, a, pos_left, size);
	}
	if(pos_right < size){
		// 创建右子树
		root->_right = new Node(a[pos_right]);
		createTree(root->_right, a, pos_right, size);
	}
}

template <class T>
BinaryTree<T>::~BinaryTree(){
	// 释放所有结点所占空间
	if (_root)
		freeNodes(_root);
}

template <class T>
void BinaryTree<T>::freeNodes(const Node* root){
	// 释放左孩子结点
	if (root->_left)
		freeNodes(root->_left);
	// 释放右孩子结点
	if (root->_right)
		freeNodes(root->_right);
	// 释放本结点
	delete root;
}

template <class T>
void BinaryTree<T>::print() const{
	if (_root) {
		print(_root);
	}
}

template <class T>
void BinaryTree<T>::print(const Node* root) const{
	if(root){
		std::cout << root->value << " ";
		print(root->_left);
		print(root->_right);
	}
}
#endif

递归输出二叉树的每个结点