《剑指offer》:[58]二叉树的下一个结点
栏目：php教程时间：2016-07-13 08:57:32
题目：给定1棵2叉树和其中1个结点，如何找出中序遍历顺序的下1个结点？树中的结点除有两个分别指向左右子结点的指针外，还有1个指向父节点的指针。
分析：这里已说了是中序遍历，所以我们就以中序遍历为例。由因而2叉树，所以有3种情况；
（1）如果如果1个结点有右子树，那末它的下1个结点就是它的右子树中最左子节点。也就是说从右子节点动身1直沿着指向左子结点的指针，我们就可以找到它的
下1个结点。
（2）如果这个结点没有右子树，如果结点是它父节点的左子树，则它的下1个结点就是它的父节点。
（3）如果1个结点没有右子树，并且是它父结点的右子树，那末旗下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叉树是：
运行结果：
------分隔线----------------------------
下一篇 Spring AOP 实现
------分隔线----------------------------