国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 《剑指offer》:[58]二叉树的下一个结点

《剑指offer》:[58]二叉树的下一个结点

来源:程序员人生   发布时间:2016-07-13 08:57:32 阅读次数:2241次
题目:给定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叉树是:


运行结果:



生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生