struct BinaryTreeNode {
int m_value;
BinaryTreeNode* m_lchild;
BinaryTreeNode* m_rchild;
BinaryTreeNode* m_father;
};
BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
if (pNode == nullptr) return nullptr;
BinaryTreeNode* pNext = nullptr;
if (pNode->m_rchild != nullptr) {
BinaryTreeNode* pRight = pNode->m_rchild;
while (pRight->m_lchild) {
pRight = pRight->m_lchild;
}
pNext = pRight;
}
else if (pNode->m_father != nullptr) {
BinaryTreeNode* pCurrent = pNode;
BinaryTreeNode* pParent = pNode->m_father;
while (pParent && pCurrent == pParent->m_rchild) {
pCurrent = pParent;
pParent = pParent->m_father;
}
pNext = pParent;
}
return pNext;
}