// 前序和中序比较简单,不做解释,后序遍历做了一定解释
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode
{
int m_data;
TreeNode * leftChild;
TreeNode * rightChild;
TreeNode(int data) : m_data(data), leftChild(NULL), rightChild(NULL) {}
};
void preOrderTravel(TreeNode * root)
{
stack< TreeNode * > st;
while( !st.empty() || root != NULL )
{
while( root )
{
st.push( root );
cout << root->m_data << " ";
root = root->leftChild;
}
root = st.top();
st.pop();
root = root->rightChild;
}
}
void inOrderTravel(TreeNode * root)
{
stack< TreeNode * > st;
while( !st.empty() || root != NULL )
{
while( root )
{
st.push( root );
root = root->leftChild;
}
root = st.top();
st.pop();
cout << root->m_data << " ";
root = root->rightChild;
}
}
// 后序遍历由于其有一定复杂性,需要构造一个辅助节点来
// 帮助,此节点会多2个标记,标记该结点是否已经遍历了左
// 右子树,可以输出该节点
struct Node
{
TreeNode * m_node;
int leftTag;
int rightTag;
// 要是该节点有左结点,则该节点标记置1,否则置0
Node(TreeNode * root)
{
m_node = root;
leftTag = root->leftChild ? 1 : 0;
rightTag = root->rightChild ? 1 : 0;
}
// 重载类型转换运算符,只是为了操作简便
operator TreeNode* ()
{
return m_node;
}
// 重载->运算符,只是为了操作简便
TreeNode * operator->()
{
return m_node;
}
};
void postOrderTravel(TreeNode * root)
{
if( root == NULL ) return;
Node node = root;
stack< Node > stn;
while( true )
{
// 若此节点有左子树,且左子树尚未被遍历,则遍历
// 这里不需要考虑 node 节点为空的情况,因为叶子
// 节点的 leftTag/rightTag 已经置为0啦
while( node.leftTag )
{
// 一旦遍历则直接令其为0,表示已经遍历
node.leftTag = 0;
stn.push( node );
node = node->leftChild;
}
// 进入这一步,表示左节点已经到了最左,只需判断该
// 节点是否有有右节点,因为这是后序遍历,根节点一定
// 在左右遍历完之后才输出
if( node.rightTag )
{
node.rightTag = 0;
stn.push( node );
node = node->rightChild;
}
else
{
cout << node->m_data << " ";
// 当最后一个节点输出之后,这里就可跳出
if( stn.empty() ) break;
node = stn.top();
stn.pop();
}
}
}
int main()
{
// 测试数据
TreeNode * root = new TreeNode( 1 );
TreeNode * node1 = new TreeNode( 2 );
TreeNode * node2 = new TreeNode( 3 );
TreeNode * node3 = new TreeNode( 4 );
TreeNode * node4 = new TreeNode( 5 );
TreeNode * node5 = new TreeNode( 6 );
TreeNode * node6 = new TreeNode( 7 );
TreeNode * node7 = new TreeNode( 8 );
root->leftChild = node1;
root->rightChild = node4;
node1->leftChild = node2;
node1->rightChild = node3;
node4->leftChild = node5;
node4->rightChild = node6;
node6->rightChild = node7;
cout << "前序遍历结果:" << endl;
preOrderTravel( root );
cout << endl;
cout << "中序遍历结果:" << endl;
inOrderTravel( root );
cout << endl;
cout << "后序遍历结果:" << endl;
postOrderTravel( root );
cout << endl;
return 0;
}