//算法导论10.4-5及12.1-3
//1. 10.4-5
//给定一个n节点的二叉树，写出一个O(n)时间的非递归过程，将该树每个节点的关键
//字输出。要求除该树本身的存储空间外只能使用固定量的额外存储空间，且在过程中
//不得修改该树，及时暂时的修改也不允许。
//2. 12.1-3
//设计一个执行中序遍历的非递归程序（提示：一种容易的方法是使用栈作为辅助数据
//结构；另一种比较复杂但比较简洁的做法是不使用栈，但要假设能测试两个指针是否
//相等。）
struct tree
{
int val;
tree *left,*right,*
parent;
};
void print(tree *
x)
{
cout<<x->val<<
" ";
}
//最简单的递归实现
void inorder_tree (tree *
x)
{
if(!x)
return;
inorder_tree (x->
left);
print(x);
inorder_tree (x->
right);
}
//用栈辅助实习二叉树非递归遍历
//不需要使用父节点指针
stack<tree *>
st;
void inorder_tree_stack(tree*
x)
{
while(x || !
st.empty())
{
//一路向左,不断将当前节点压入栈中
while(x)
{
st.push(x);
x=x->
left;
}
//取出栈顶元素，输出，并遍历其右节点
x=
st.top();
st.pop();
print(x);
x=x->
right;
}
}
//非递归的中序遍历树,不用栈实现，但需要父节点指针
//一共有3种情况
//1. 访问左孩子
//2. 访问右孩子
//3. 如果是从右孩子返回，表明整棵子树已访问完，需要沿树而上寻找父节点。
// 直到是从左孩子返回，或者访问到根节点的父节点
void inorder_tree_nostack(tree *
x)
{
if(!x)
return;
tree *y=
NULL;
while(
true)
{
//访问左孩子
if(y != x->
left)
{
while(x->left) x=x->
left;
}
print(x);
//访问右孩子
if(x->
right)
{
x=x->
right;
continue;
}
//回溯
do
{
y=
x;
x=x->
parent;
//访问到根节点的父节点（NULL)
if(!x)
return;
}while(y == x->
right);
}
}
转载于:https://www.cnblogs.com/blazebird/archive/2013/04/11/3015615.html
相关资源：数据结构—成绩单生成器
