首页 > 代码库 > 基于中序遍历找到一个结点的后继结点
基于中序遍历找到一个结点的后继结点
题目：
基于中序遍历找到一个结点的后继结点。
分析：
首先明确中序遍历，顺序为：左--->根----->右
假设当前结点为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 =http://www.mamicode.com/= -1)>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。