《劍指offer》:[58]二叉樹的下一個結點
來源：程序員人生 發布時間：2016-07-13 08:57:32 閱讀次數：2430次
題目：給定1棵2叉樹和其中1個結點，如何找出中序遍歷順序的下1個結點？樹中的結點除有兩個分別指向左右子結點的指針外，還有1個指向父節點的指針。
分析：這里已說了是中序遍歷，所以我們就以中序遍歷為例。由因而2叉樹，所以有3種情況；
（1）如果如果1個結點有右子樹，那末它的下1個結點就是它的右子樹中最左子節點。也就是說從右子節點動身1直沿著指向左子結點的指針，我們就可以找到它的
下1個結點。
（2）如果這個結點沒有右子樹，如果結點是它父節點的左子樹，則它的下1個結點就是它的父節點。
（3）如果1個結點沒有右子樹，并且是它父結點的右子樹，那末旗下1個結點就是沿著指向父指針的結點向上找，直到找到1個是它父結點的左子結點的結點。如果這樣的結點存在則該結點的父節點就是下1個結點。
說的可能不直觀，我們用3張圖來來直觀的解釋1下上述3種情況，由于我覺得1張簡單的圖遠比長篇大論要簡潔易懂，所以我的筆記里有很多圖，可能畫的不好！
具體實現代碼以下：
#include <iostream>
using namespace std;
struct BinaryTree
{
int data;
BinaryTree *pLeft;
BinaryTree *pRight;
BinaryTree *pParent;
};
BinaryTree *pRoot=NULL;
int arr[7]={10,6,15,4,5,12,18};
void InSertTree(BinaryTree *root1,int data)
{
//插入在左側；
if(root1->data > data)
{
if(root1->pLeft==NULL)
{
BinaryTree *node=new BinaryTree;
node->data=data;
node->pLeft=node->pRight=NULL;
node->pParent=root1;
root1->pLeft=node;
}
else
{
InSertTree(root1->pLeft,data);
}
}
//插入在右側；
else
{
if(root1->pRight==NULL)
{
BinaryTree *node=new BinaryTree;
node->data=data;
node->pLeft=node->pRight=NULL;
node->pParent=root1;
root1->pRight=node;
}
else
{
InSertTree(root1->pRight,data);
}
}
}
void CreateTree(BinaryTree **root,int length,int *array)
{
for(int i=0;i<length;i++)
{
if(*root==NULL)
{
BinaryTree *pNode=new BinaryTree;
pNode->data=array[i];
pNode->pLeft=pNode->pRight=NULL;
*root=pNode;
}
else
InSertTree(*root,array[i]);
}
}
BinaryTree *GetNextNode(BinaryTree* pNode)
{
if(pNode==NULL)
return NULL;
BinaryTree *pNext=NULL;
if(pNode->pRight!=NULL)
{
BinaryTree *right=pNode->pRight;
while(right->pLeft!=NULL)
right=right->pLeft;//找到最左側的1個節點；
pNext=right;
}
else if(pNode->pParent!=NULL)
{
BinaryTree *pCurrent=pNode;
BinaryTree *parent=pNode->pParent;
while(parent!=NULL && pCurrent==parent->pRight)
{
pCurrent=parent;
parent=parent->pParent;
}
pNext=parent;
}
return pNext;
}
int main()
{
BinaryTree *result=NULL;
CreateTree(&pRoot,7,arr);
result=GetNextNode(pRoot);
if(NULL==result)
cout<<"輸入的結點不存在！"<<endl;
else
cout<<pRoot->data<<"的下1個結點為："<<result->data<<endl;
system("pause");
return 0;
}
輸入的2叉樹是：
運行結果：
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
