题目:给定一棵二叉树和其中一个节点,如何找出中序遍历序列的下一个节点?树中的节点除了有两个分别指向左、右节点的指针,还有一个节点指向父节点的指针。
中序遍历序列是{d,b,h,e,i,a,f,c,g}
如果一个节点有右子树,那么它的下一个节点就是它的 右子树中的最左子节点。也就是说,从右子节点出发一直沿着指向左子节点的指针,我们就能找到它的下一个节点。
接着我们分析一个节点没有右子树的情形。如果节点是它父节点的左子节点,那么它的下一个节点就是它的父节点。
如果一个节点既没有右子树,并且它还是它父节点的右子节点,那么这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历,直到找到一个是它父节点的左子节点的节点。如果这样的节点存在,那么这个节点的父节点就是我们要找的下一个节点。
BinaryTreeNode* GetNext(BinaryTreeNode* pNode) { if (pNode == NULL)//如果树为空树 { return NULL; } BinaryTreeNode* pNext = NULL; if (pNode->right != NULL)//如果节点有右子树,则右子树的最左节点是该节点的下一个节点 { BinaryTreeNode* pRight = pNode->right; while (pRight->letf != NULL) { pRight = pRight->letf; } pNext = pRight; } else if (pNode->parent->NULL)//右子树为空但是有父节点 {//这里有两种情况,如果节点是父节点的左子节点,则下一个节点就是父节点, //如果节点是父节点的右子节点并且为叶子结点 BinaryTreeNode* pCurrent = pNode; BinaryTreeNode* pParent = pNode->parent; while (pParent != NULL && pCurrent == pParent->right)//父节点不空,并且该节点是父节点的右子树 { pCurrent = pParent; pParent = pParent->parent; } pNext = pPrent; } return pNext; }