分析： 首先明确中序遍历，顺序为：左--->根----->右 假设当前结点为p。 有两种情况： 1.当p有右子树时，那么其右子树的最左结点即为所求：
2.当p没有右子树时，有下面两种情况：
沿着p向上找，如果p的父结点的左孩子是p，那么该父结点即为所求，否则继续向上找。
代码：
/*
找到中序遍历下一个结点的后继结点
by Rowandjj
2014/8/19
*/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
int data;
struct _NODE_ *left;
struct _NODE_ *right;
struct _NODE_ *parent;
}Node,*pNode,*pTree;
//找到中序遍历时，p的后继结点
pNode after(pNode p)
{
if(p == NULL)
{
return NULL;
}
if(p->right != NULL)//存在右子树
{//找到右子树中的最左结点
pNode pTemp = p->right;
while(pTemp->left)
{
pTemp = pTemp->left;
}
return pTemp;
}else//不存在右子树
{//那么找到该结点的父结点，若当前结点是父结点的左孩子那么父结点即为所求
//否则继续向上寻找
pNode pParent = p->parent;
while(pParent && pParent->right == p)
{
p = pParent;
pParent = p->parent;
}
return pParent;
}
}
//构建
void create(pTree *pRoot,pNode pParent)
{
int data;
cin>>data;
if(data == -1)
{
return;
}
*pRoot = (pNode)malloc(sizeof(Node));
if(*pRoot == NULL)
{
exit(-1);
}
(*pRoot)->data = data;
(*pRoot)->left = NULL;
(*pRoot)->right = NULL;
(*pRoot)->parent = pParent;
create(&(*pRoot)->left,*pRoot);
create(&(*pRoot)->right,*pRoot);
}
//中序遍历
void display(pTree pRoot)
{
if(pRoot == NULL)
{
return;
}
if(pRoot->left != NULL)
{
display(pRoot->left);
}
cout<<pRoot->data<<" ";
if(pRoot->right != NULL)
{
display(pRoot->right);
}
}
int main()
{
pTree pTree = NULL;
create(&pTree,NULL);
// pNode p1 = pTree->left->right;
// cout<<p1->data<<endl;
// cout<<p1->parent->data<<endl;
//cout<<after(pTree)->data;
//cout<<after(pTree->left->right)->data<<endl;
cout<<after(pTree->left)->data<<endl;
display(pTree);
return 0;
}