【数据结构】 二叉树(2)

后序遍历（非递归）：

void?_PostOrder_NoR()
????{
????????Node*?pre?=?NULL;
????????Node*?cur?=?_root;
????????stack<Node*>?s;
????????while?(cur?||?!s.empty())
????????{
????????????while?(cur)
????????????{
????????????????s.push(cur);
????????????????cur?=?cur->_left;
????????????}

????????????Node*?top?=?s.top();
????????????if?(top->_right?==?NULL?||?top->_right?==?pre)
????????????{
????????????????cout?<<?top->_data?<<?"?";
????????????????s.pop();
????????????????pre?=?top;
????????????}
????????????else
????????????{
????????????????cur?=?top->_right;
????????????}
????????}
????}

发现，非递归的实现是利用栈结构存储和管理二叉树的。

附源代码以及测试代码：

BinaryTree.h 文件：

#pragma?once?

#include?<stack>
template?<class?T>
struct?BinaryTreeNode
{
????T?_data;
????BinaryTreeNode<T>*?_left;
????BinaryTreeNode<T>*?_right;

????BinaryTreeNode(const?T&?x)
????????:?_data(x)
????????,?_left(NULL)
????????,?_right(NULL)
????{}
};

template?<class?T>
class?BinaryTree
{
????typedef?BinaryTreeNode<T>?Node;
public:
????BinaryTree()
????????:_root(NULL)
????{}

????BinaryTree(const?T*?a,?size_t?size,?const?T&?invalid)
????{
????????size_t?index?=?0;
????????_root?=?_CreatBinaryTree(?a,?size,?index,?invalid);
????}

????BinaryTree(const?BinaryTree<T>&?t)
????{
????????_root?=?_Copy(t._root);
????}

????//BinaryTree<T>&?operator=(const?BinaryTree<T>&?t)
????//{
????//????if?(this?!=?&t)
????//????{
????//????????Node*?tmp?=?_Copy(t._root);
????//????????_Destory(_root);
????//????????_root?=?tmp;
????//????}
????//????return?*this;
????/
                        
（编辑：ASP站长网）