|
给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右孩子节点的指针，还有一个指向父节点的指针。
- 若该结点有右孩子结点，那么中序遍历中的下一个结点就是其右子树最左边的结点；
- 若该结点没有右孩子结点
- 若该结点是其父结点的左孩子，那么中序遍历中的下一个结点就是其父结点；
- 若该结点是其父结点的右孩子，那么需要不断向上寻找其祖先结点，直到该结点所在的树作为其祖先结点的左子树时，那么中序遍历中的下一个结点就是其祖先结点。
-
C++实现
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==NULL)return NULL;
if(pNode->right!=NULL){//如果右子树不为空
pNode = pNode->right;
//寻找右子树最左端的叶结点
while(pNode->left!=NULL)
pNode = pNode->left;
return pNode;
}
//寻找该结点所在的左子树的父结点
while(pNode->parent!=NULL){
TreeLinkNode* pParent = pNode->parent;
if(pParent->left==pNode)
return pParent;
pNode = pNode->parent;
}
return NULL;
}
| 
转播
