首页 > 代码库 > 018给定二叉查找树的一个结点， 写一个算法查找它的“下一个”结点“（keep it up）
018给定二叉查找树的一个结点， 写一个算法查找它的“下一个”结点“（keep it up）
给定二叉查找树的一个结点， 写一个算法查找它的“下一个”结点(即中序遍历后它的后继结点)，
其中每个结点都有指向其父亲的链接。
这个题本质就是线索化二叉树时找后继结点的题。找后继结点存在两种情况：
1 如果当前结点有右孩子，则后继结点为右孩子的最左结点
2 如果没有右孩子，
A 当前结点为父结点的左孩子，则父结点就是后继结点
B 当前结点为父结点的右孩子，则向父结点找，直到当前结点不是父结点的右孩子终止，此时
其中每个结点都有指向其父亲的链接。
这个题本质就是线索化二叉树时找后继结点的题。找后继结点存在两种情况：
1 如果当前结点有右孩子，则后继结点为右孩子的最左结点
2 如果没有右孩子，
A 当前结点为父结点的左孩子，则父结点就是后继结点
B 当前结点为父结点的右孩子，则向父结点找，直到当前结点不是父结点的右孩子终止，此时
父节点就是后继结点
代码：
struct TreeNode
{
int data;
TreeNode* leftChild;
TreeNode* rightChild;
TreeNode* parent;
};
TreeNode* findContinue(const TreeNode* vNode)
{
if (vNode == NULL) return NULL;
if (vNode->rightChild != NULL)
{
TreeNode* Tmp = vNode->rightChild;
while (Tmp->leftChild != NULL)
{
Tmp = Tmp->leftChild;
}
return Tmp;
}
TreeNode* Cur = vNode;
TreeNode* pParent = Cur->parent;
while (pParent != NULL && pParent->rightChild == Cur)
{
Cur = pParent;
pParent = pParent->rightChild;
}
return pParent;
}018给定二叉查找树的一个结点， 写一个算法查找它的“下一个”结点“（keep it up）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。