思路比较简单：
就是先调用minimum找到二叉树中的最小关键字的结点，即二叉树最左边的树叶，然后依然迭代地调用tree_successor寻找前一个结点x的后继：即比x->key大的所有关键字中最小的一个的节点。依次输出即可。
minimum很容易理解，利用蛮力一直往左遍历，到底即可。
tree_successor分两种情况，如果x有右子树，则x的后继就是右子树中最小关键字的那个结点，如果x没有右子树，则后继是x的最底层祖先。最底层祖先听着很拗口，用图示表示就是：13号结点的后继是15，15即为13的后继，13的祖先有15和30，而15为13的最底层祖先。
代码：
#include<iostream>运行结果：
using namespace std;
struct node//结点
{
int key;
node* p;
node* left;
node* right;
node(){}
node(int k):key(k),p(NULL),left(NULL),right(NULL){}
};
struct TREE//树
{
node* root;
TREE():root(NULL){}
};
node* minimum(node* x)//一直往左遍历到最底即可
{
while(x->left!=NULL)
x=x->left;
return x;
}
node* tree_successor(node* x)//找后继
{
if(x->right!=NULL)//如果有右子树，则后继为右子树中最小值
return minimum(x->right);
node* y=x->p;//如果没有右子树，后继为最底层祖先
while(y!=NULL && y->right==x)
{
x=y;
y=y->p;
}
return y;
}
void tree_insert(TREE* T,node* z)//插入节点
{
node* y=NULL;
node* x=T->root;//管理两个指针，父指针y,y的子树指针x
while(x!=NULL)//一直向下遍历到z应该插入的位置
{
y=x;
if(x->key < z->key)
x=x->right;
else x=x->left;
}
z->p=y;//先将z的父指针p指向y
if(y==NULL)//若树为空，树根即为z
T->root=z;
else if(z->key < y->key)//否则分插入左边还是右边
y->left=z;
else y->right=z;
}
void iterative_tree_walk(node* x)
{
node* p=minimum(x);//先找到最小值
while(p!=NULL)//然后依次迭代遍历前一个关键字的后继
{
cout<<p->key<<' ';
p=tree_successor(p);
}
}
void tree_walk(node* x)//递归中序
{
if(x!=NULL)
{
tree_walk(x->left);
cout<<x->key<<' ';
tree_walk(x->right);
}
}
void main()
{
int A[]={15,6,18,3,7,17,20,2,4,13,9};
int len=sizeof(A)/sizeof(A[0]);
TREE* T=new TREE;
node* z;
for(int i=0;i<len;i++)
{
z=new node(A[i]);
tree_insert(T,z);
}
cout<<"Recursion"<<endl;
tree_walk(T->root);
cout<<endl;
cout<<"Iteration"<<endl;
iterative_tree_walk(T->root);
cout<<endl;
}
