递归与非递归实现二叉树

    二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i - 1）个结点；深度为k的二叉树至多有2^k - 1个结点。由于树的定义是递归实现的，所以在进行二叉树的前序、中序和后序遍历可通过递归实现，但也可通过非递归的栈来实现，二叉树的层次遍历可通过队列实现。

下面我对二叉树及前序、中序、后序遍历二叉树等方法进行实现

例如二叉树:

测试用例：

int arrary[10] = {1,2,3,'$','$',4,'$','$',5,6};

arrary为上图所示二叉树，通过前序存储的，'$'表示非法值，即没有结点

二叉树的结构：

template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _data;
	BinaryTreeNode();
	BinaryTreeNode(const T& x);
};

template<class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;
public:
	BinaryTree();
	BinaryTree(const T* a, size_t size, const T& invalid);
	BinaryTree(const BinaryTree<T>& t);
	BinaryTree<T>& operator=(BinaryTree<T> t);
	~BinaryTree();
	void PrevOrder();//前序遍历-递归	
	void InOrder();//中序遍历-递归
	void PostOrder();//后序遍历-递归
	void PrevOrder_NonR();//前序遍历-非递归
	void InOrder_NonR();//中序遍历-非递归
	void PostOrder_NonR();//后序遍历-非递归
	void LevelOrder();//层次遍历
	size_t Size();//结点个数
	size_t Depth();//树的深度
	size_t LeafSize();//叶子结点个数
	size_t GetkLevel();//第k层结点个数
protected:
	Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid);//树的建立
	Node* _CopyTree(Node* t);//复制树
	void _Distory(Node* root);//清空结点，先释放子树，再释放根结点
	void _PrevOrder(Node* root);//前序遍历
	void _InOrder(Node* root);//中序遍历
	void _PostOrder(Node* root);//后序遍历
	size_t _Size(Node* root);//结点个数
	size_t _Depth(Node* root);//树的深度
	//size_t _LeafSize(Node* root);//叶子结点个数
	size_t _LeafSize(Node* root,size_t& size);//叶子结点个数
	//size_t _GetkLevel(int k, Node* root);//第k层结点个数
	size_t _GetkLevel(int k, Node* root, int& size, int level);//第k层结点个数
private:
	Node* _root;// BinaryTreeNode<T>* _root;
};

二叉树的构造、拷贝构造、赋值运算和析构的实现，由于二叉树存在左子树和右子树，故用递归实现其功能，具体实现如下：

template<class T>
BinaryTreeNode<T>::BinaryTreeNode()
:_left(NULL)
, _right(NULL)
, _data(0)
{}
template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T& x)
: _left(NULL)
, _right(NULL)
, _data(x)
{}

template<class T>
BinaryTree<T>::BinaryTree()
:_root(NULL)
{}
template<class T>
BinaryTree<T>::~BinaryTree()
{
	_Distory(_root);
}
template<class T>
void BinaryTree<T>::_Distory(Node* root)//清空结点，先释放子树，再释放根结点
{
	if (root == NULL)
	{
		return;
	}
	if (root->_left)//递归释放子结点
	{
		_Distory(root->_left);
	}
	if (root->_right)
	{
		_Distory(root->_right);
	}
	delete root;
	root = NULL;
}
template<class T>
BinaryTree<T>::BinaryTree(const T* a, size_t size, const T& invalid)
{
	size_t index = 0;//标记数组下标
	_root = _CreateTree(a, size, index, invalid);
}
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::_CreateTree(const T* a, size_t size, size_t& index, const T& invalid)//树的建立
{
	Node* root = NULL;
	if (index < size && a[index] != invalid)//indx<size以防数组越界
	{
		root = new Node(a[index]);
		root->_left = _CreateTree(a, size, ++index, invalid);//左子树递归
		root->_right = _CreateTree(a, size, ++index, invalid);//右子树递归
	}
	return root;
}
template<class T>
BinaryTree<T>::BinaryTree(const BinaryTree<T>& t)
{
	_root = _CopyTree(t._root);
}
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::_CopyTree(Node* t)//此处的返回类型不能用Node表示
{
	Node* root = NULL;
	if (t != NULL)
	{
		root = new Node(t->_data);
		root->_left = _CopyTree(t->_left);
		root->_right = _CopyTree(t->_right);
	}
	return root;
}
template<class T>
BinaryTree<T>& BinaryTree<T>::operator=(BinaryTree<T> t)//现代写法
{
	if (this != &t)
	{
		BinaryTree<T> tmp = t;
		swap(_root, tmp._root);
	}
	return *this;
}

前序遍历(先根遍历)：(1)先访问根节点；(2)前序访问左子树；(3)前序访问右子树.【1 2 3 4 5 6】

下面分别用递归和非递归两种方法实现。

二叉树的递归实现前序遍历

//递归实现
template<class T>
void BinaryTree<T>::PrevOrder()//前序遍历(先根结点)
{
	_PrevOrder(_root);
}
template<class T>
void BinaryTree<T>::_PrevOrder(Node* root)
{
	if (root == NULL)
	{
		return;
	}
	cout << root->_data << " ";
	_PrevOrder(root->_left);
	_PrevOrder(root->_right);
}

二叉树的非递归实现前序序列，利用栈实现。

由于栈是后进先出，对于二叉树的前序遍历先访问左子树后访问右子树，故右结点比左结点先进栈

//非递归实现（利用栈实现）
template<class T>
void BinaryTree<T>::PrevOrder_NonR()//前序遍历-非递归
{
	stack<Node*> s;
	if (_root)
	{
		s.push(_root);
	}
	while (!s.empty())
	{
		Node* top = s.top();//访问栈顶元素
		cout << top->_data << " ";
		s.pop();
		//右结点比左结点先进栈
		if (top->_right)
		{
			s.push(top->_right);
		}
		if (top->_left)
		{
			s.push(top->_left);
		}
	}
	cout << endl;
}

中序遍历：(1)中序访问左子树；(2)访问根节点；(3)中序访问右子树.【3 2 4 1 6 5】

下面分别用递归和非递归两种方法实现

二叉树的递归实现中序序列

template<class T>
void BinaryTree<T>::InOrder()//中序遍历（中根结点）
{
	_InOrder(_root);
}
template<class T>
void BinaryTree<T>::_InOrder(Node* root)
{
	if (root == NULL)
	{
		return;
	}
	_InOrder(root->_left);
	cout << root->_data << " ";
	_InOrder(root->_right);
}

二叉树的非递归实现中序序列

//非递归实现（利用栈实现）
template<class T>
void BinaryTree<T>::InOrder_NonR()//中序遍历-非递归
{
	if (_root == NULL)
	{
		return;
	}
	stack<Node*> s;
	Node* cur = _root;
	while (cur || !s.empty())
	{
		//压一棵树的左结点，直到最左结点
		while (cur)
		{
			s.push(cur);
			cur = cur->_left;
		}
		if (!s.empty())
		{
		    Node* top = s.top();
		    cout << top->_data << " ";
		    s.pop();
			cur = top->_right;//使cur指向最左结点top的右结点
		}
	}
	cout << endl;
}

后序遍历(后根遍历)：(1)后序访问左子树；(2)后序访问右子树；(3)访问根节点.【3 4 2 6 5 1】

下面分别用递归和非递归两种方法实现

二叉树的递归实现后序序列

//递归实现
template<class T>
void BinaryTree<T>::PostOrder()//后序遍历（后根结点）
{
	_PostOrder(_root);
}
template<class T>
void BinaryTree<T>::_PostOrder(Node* root)//后序遍历
{
	if (root == NULL)
	{
		return;
	}
	_PostOrder(root->_left);
	_PostOrder(root->_right);
	cout << root->_data << " ";
}
//非递归实现（利用栈实现）

二叉树的非递归实现后序序列

template<class T>
void BinaryTree<T>::PostOrder_NonR()//后序遍历-非递归
{
	if (_root == NULL)
	{
		return;
	}
	stack<Node*> s;
	Node* cur = _root;
	Node* prev = NULL;
	while (cur || !s.empty())
	{
		//压一棵树的左结点，直到最左结点
		while (cur)
		{
			s.push(cur);
			cur = cur->_left;
		}
		Node* top = s.top();
		if (top->_right == NULL || top->_right == prev)
		{
			cout << top->_data << " ";
			s.pop();
			prev = top;
		}
		else//当未访问过栈顶的右子树，则继续右子树的访问
		{
			cur = top->_right;
		}
		cout << endl;
	}
}

层序遍历：一层层节点依次遍历。【1 2 5 3 4 6】

下面用非递归方法实现，利用队列进行访问。

//递归实现
template<class T>
void BinaryTree<T>::LevelOrder()//层次遍历,通过队列实现
{
	queue<Node*> q;//建立队列存放Note*类型值
	if (_root != NULL)
	{
		q.push(_root);
	}
	while (!q.empty())
	{
		Node* front = q.front();
		cout << front->_data << " ";//访问队头
		q.pop();//队头出队列
		if (front->_left != NULL)//存在左或右结点入队列
		{
			q.push(front->_left);
		}
		if (front->_right != NULL)
		{
			q.push(front->_right);
		}
	}
	cout << endl;
}

求树的结点个数，递归实现：

template<class T>
size_t BinaryTree<T>::Size()//结点个数
{
	return _Size(_root);
}
template<class T>
size_t BinaryTree<T>::_Size(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}//root不为0，则Size+1
	return _Size(root->_left) + _Size(root->_right) + 1;
}

求树的深度，递归实现：

template<class T>
size_t BinaryTree<T>::Depth()//树的深度
{
	return _Depth(_root);
}
template<class T>
size_t BinaryTree<T>::_Depth(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	size_t LeftDepth = _Depth(root->_left);
	size_t RightDepth = _Depth(root->_right);
	if (LeftDepth > RightDepth)//root不为0，则深度+1
	{
		return LeftDepth + 1;
	}
	else
	{
		return RightDepth + 1;
	}
}

求树的叶子结点个数，递归实现：

//方法一
template<class T>
size_t BinaryTree<T>::LeafSize()//叶子结点个数
{
	return _LeafSize(_root);
}
template<class T>
size_t BinaryTree<T>::_LeafSize(Node* root)
{
	if (root == 0)
	{
		return 0;
	}
	if (root->_left == 0 && root->_right == 0)
	{
		return 1;
	}
	return _LeafSize(root->_left) + _LeafSize(root->_right);
}
//方法二:在LeafSize中定义_size表示叶子结点个数
template<class T>
size_t BinaryTree<T>::LeafSize()//叶子结点个数
{
	size_t _size = 0;
	return _LeafSize(_root, _size);
}
template<class T>
size_t BinaryTree<T>::_LeafSize(Node* root, size_t& size)
{
	if (root == 0)
	{
		return 0;
	}
	if (root->_left == 0 && root->_right == 0)
	{
		++size;
		return size;
	}
	_LeafSize(root->_left, size);
	_LeafSize(root->_right, size);
	return size;
}

二叉树中第k层结点的个数，递归实现：

//方法一
template<class T>
size_t BinaryTree<T>::GetkLevel(int k)
{
        assert(k>0);
	return _GetkLevel(k, _root);
}
template<class T>
size_t BinaryTree<T>::_GetkLevel(int k, Node* root)//第k层结点个数
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)//利用递归使k递减，k==1结束
	{
		return 1;
	}
	size_t size1 = _GetkLevel(k - 1, root->_left);
	size_t size2 = _GetkLevel(k - 1, root->_right);
	return size1 + size2;
}
//方法二:在GetkLevel中定义size表示第k层结点个数
template<class T>
size_t BinaryTree<T>::GetkLevel(int k)
{
	assert(k > 0);
	int size = 0;//size为二叉树第level层结点个数
	int level = 1;//第level层
	return _GetkLevel(k, _root, size, level);
}
template<class T>
size_t BinaryTree<T>::_GetkLevel(int k, Node* root, int& size, int level)//第k层结点个数
{
	if (root == NULL)
	{
		return 0;
	}
	if (level == k)
	{
		++size;
		return size;
	}
	_GetkLevel(k, root->_left, size, level+1);
	_GetkLevel(k, root->_right, size, level+1);
	return size;
}