面试题8:二叉树的下一个结点
面试题8:二叉树的下一个结点
// 面试题8:二叉树的下一个结点
// 题目:给定一棵二叉树和其中的一个结点,如何找出中序遍历顺序的下一个结点?
// 树中的结点除了有两个分别指向左右子结点的指针以外,还有一个指向父结点的指针。
// 二叉树的结构体定义如下。
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
BinaryTreeNode* m_pParent;
};
解题思路:
以上图为例,节点有没有左子树不影响,因为左子树肯定会在节点之前被遍历。
如果输入节点有右子树,比如根节点a有右子树c,但是节点c可能是其他左子树的根节点,所以中序遍历不能选择c。
应该从c的左子树一条路走到黑,走到叶结点为止,这样才是中序遍历节点a的下一个节点。
如果输入节点没有右子树,遍历之后应该继续向上遍历(如果父节点存在的话)。
如果节点是上一级节点的左子树,说明上一级节点是目前的根节点,下一个应该遍历它,比如节点h之后应遍历e。
如果节点是上一级节点的右子树,说明这一个小区域的中序遍历已完成,应该沿右子树一直向上回溯。
比如i节点一直回溯到b节点,b节点及b的子树都已经作为a的左子树被遍历完成,下一个就应该遍历b的父节点a。
不知道我有没有写明白,语言表述能力不太好,大概就是那么个意思。
伪代码:
BinaryTreeNode GetNext(BinaryTreeNode* pNode){
if(pNode==nullptr)
return nullptr;
if(pNode拥有右子树pRight){
while(pRight左子树不为空){
pRight=pRight的左子树;
}
return pRight;
}
else if(pNode是父节点右子树){
while(pNode父节点pParent是上一级节点的右子树){
pParent=pParent的父节点;
}
return pParent的父节点;
}
else{
return pNode的父节点;
}
}
c/c++:
作者的代码是做了一些优化的,pNode是上一级节点的右子树/左子树的公共代码被提出来了,我还是看了两分钟才想明白,太菜了。。
BinaryTreeNode* GetNext(BinaryTreeNode* pNode) {
//校验参数有效性
if (pNode == nullptr)
return nullptr;
BinaryTreeNode* pNext = nullptr;
//pNode拥有右子树
if (pNode->m_pRight != nullptr) {
BinaryTreeNode* pRight = pNode -> m_pRight;
while (pRight->m_pLeft != nullptr)
pRight = pRight->m_pLeft;
pNext = pRight;
}
//pNode没有右子树
else if(pNode->m_pParent!=nullptr){
BinaryTreeNode* pCurrent = pNode;
BinaryTreeNode* pParent = pNode->m_pParent;
//pNode是父节点的右子树
while (pParent != nullptr&&pCurrent == pParent->m_pRight) {
pCurrent = pParent;
pParent = pParent->m_pParent;
}
//pNode是父节点的左子树,直接向上遍历
pNext = pParent;
}
return pNext;
}