非递归遍历二叉树（前序，中序，后序，叶子节点的计算）

#pragma once
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
template<class T>
struct BinaryTreeNode
{
	T _data;
	BinaryTreeNode* _left;
	BinaryTreeNode* _right;
	BinaryTreeNode(const T& x)
		:_data(x)
		, _left(NULL)
		, _right(NULL)
	{}
};
template<class T>
class BinaryTree
{
protected:
	BinaryTreeNode<T>* _root;
protected:
	//先序遍历产生二叉树
	BinaryTreeNode<T>* _CreateBinaryTree(T* arr, size_t &index, size_t size)
	{
		BinaryTreeNode<T>* root = NULL;
		if (index < size&&arr[index] != ‘#‘)
		{
			root = new BinaryTreeNode<T>(arr[index]);
			root->_left = _CreateBinaryTree(arr, ++index, size);
			root->_right = _CreateBinaryTree(arr, ++index, size);
		}
		return root;
	}
	void _PreOrder(BinaryTreeNode<T>* root)
	{
		if (root != NULL)
		{
			cout << root->_data << " ";
			_PreOrder(root->_left);
			_PreOrder(root->_right);
		}
		return;
	}
	void _InOrder(BinaryTreeNode<T>* root)
	{
		if (root != NULL)
		{
			_InOrder(root->_left);
			cout << root->_data<<" ";
			_InOrder(root->_right);
		}
		return;
	}void _PostOrder(BinaryTreeNode<T>* root)
	{
		if (root != NULL)
		{
			_PostOrder(root->_left);
			_PostOrder(root->_right);
			cout << root->_data << " ";
		}
		return;
	}
	void _Clear(BinaryTreeNode<T>* root)
	{
		if (root)
		{
			_Clear(root->_left);
			_Clear(root->_right);
			delete root;
		}
	}
	
	int  _Size(BinaryTreeNode<T>*  root)
	{
		if (root==NULL)
			return 0;
		return  1 + _Size(root->_left) + _Size(root->_right);
	}
	int _Depth(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
			return  0;
		int leftDepth = _Depth(root->_left);
		int rightDepth = _Depth(root->_right);
		return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
	}
	BinaryTreeNode<T>*  _Copy(BinaryTreeNode<T>* root)
	{
		BinaryTreeNode<T>*  tmp = NULL;
		if (root)
		{
			tmp = new BinaryTreeNode<T>(root->_data);
			tmp->_left=_Copy(root->_left);
			tmp->_right=_Copy(root->_right);
		}
		return tmp;
	}
	int _LeftNum(BinaryTreeNode<T>* root)
	{
		if (root == NULL)
			return 0;
		if (root->_left == NULL&&root->_right == NULL)
			return 1;
		return   _LeftNum(root->_left) + _LeftNum(root->_right);
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	BinaryTree(T* a, size_t size)
	{
		size_t index = 0;
		_root = _CreateBinaryTree(a, index, size);
	}
	BinaryTree(const BinaryTree& b)
	{
		_root = _Copy(b._root);
	}
	BinaryTree&  operator=(BinaryTree b)
	{
		swap(_root, b._root);
	}
	~BinaryTree()
	{
		_Clear(_root);
		_root = NULL;
	}
	void  PreOrder()
	{
		_PreOrder(_root);
		cout << endl;
	}
	void  InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	void  PostOrder()
	{
		_PostOrder(_root);
		cout << endl;
	}
	int Size()
	{
		return  _Size(_root);
	}
	int Depth()
	{
		return _Depth(_root);
	}
	int LeafNum()
	{
		return _LeftNum(_root);
	}
	void PreOrder_Non_R()
	{
		stack<BinaryTreeNode<T>*>  s;
		if (_root)
			s.push(_root);
		while (!s.empty())
		{
			BinaryTreeNode<T>* top = s.top();
			cout << top->_data << " ";
			s.pop();
			if (top->_right)
				s.push(top->_right);
			if (top->_left)
				s.push(top->_left);
		}
		cout << endl;
	}
	void  InOrder_Non_R()
	{
		stack<BinaryTreeNode<T>*>  s;
		BinaryTreeNode<T>* cur = _root;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			BinaryTreeNode<T>* top = s.top();
			cout << top->_data << " ";
			s.pop();
			cur = top->_right;
		}
		cout << endl;
	}
	void  PostOrder_Non_R()
	{
		stack<BinaryTreeNode<T>*>  s;
		BinaryTreeNode<T>* cur = _root;
		BinaryTreeNode<T>* prevVisited = NULL;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			BinaryTreeNode<T>* top = s.top();
			if (top->_right == NULL || top->_right == prevVisited)//两种情况，才访问根节点
			{
				cout << top->_data << " ";
				s.pop();
				prevVisited = top;
				cur = NULL;//可要可不要
			}
			else
			    cur = top->_right;
		}
		cout << endl;
	}
};
#include"BinaryTree.h"
void Test1()
{
	int array[10] = { 1, 2, 3, ‘#‘, ‘#‘, 4, ‘#‘, ‘#‘, 5, 6 };
	BinaryTree<int> b2(array, 10);
	b2.PreOrder();
	b2.PreOrder_Non_R();
	b2.InOrder();
	b2.InOrder_Non_R();
	b2.PostOrder();
	b2.PostOrder_Non_R();
	cout << b2.LeafNum() << endl;
}
int main()
{
	Test1();
	system("pause");
	return 0;
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1749718

非递归遍历二叉树（前序，中序，后序，叶子节点的计算）

原文：http://10541556.blog.51cto.com/10531556/1749718