博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
二叉树的下一个结点
阅读量:7077 次
发布时间:2019-06-28

本文共 613 字,大约阅读时间需要 2 分钟。

题目描述:

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

  因为是中序遍历,所有要找的这个父结点,肯定有这样的特征:

当前结点所在的子树一定是某个根结点的左子树。并且当前结点是该左子树的最右结点。

  所以算法设计:

如果当前结点有右子树,那么找右子树的最左结点。如果当前结点没有右子树,那么找一个合适的父结点。

  所以代码实现:

TreeLinkNode* GetNext(TreeLinkNode* pNode){	TreeLinkNode *cur = pNode;	if(cur->right != NULL)	{		cur = cur->right;		while(cur->left != NULL)		{			cur = cur->left;		}	}//if	else	{		TreeLinkNode *tmp = cur->next;		if(tmp == NULL)			return NULL;		while(tmp != NULL && tmp->left != cur)		{			cur = tmp;			tmp = tmp->next;		}		cur = tmp;	}	return cur;}

  

转载于:https://www.cnblogs.com/stemon/p/4762292.html

你可能感兴趣的文章
怎么获取红米6 Pro的root权限
查看>>
poj 3376 Finding Palindromes
查看>>
proxy vue3.0
查看>>
js和JQuery区别
查看>>
微信支付开发1 微信支付URL配置
查看>>
网页小工具集合
查看>>
seaJS源码
查看>>
Windows 8 学习笔记(一)
查看>>
UINavigationController的常用属性和方法
查看>>
centos7zabbix-agen安装
查看>>
CORS FOR AspNetCore
查看>>
iOS—仿微信单击放大图片
查看>>
noteexpress使用指南
查看>>
C从控制台(stdin)输入带空格的字符串到字符数组中
查看>>
Codeforces Round #428 A. Arya and Bran【模拟】
查看>>
【设计模式】抽象工厂模式
查看>>
OO第四次博客
查看>>
面试STAR法则
查看>>
Linux命令-自动挂载文件/etc/fstab功能详解[转]
查看>>
对地理信息标准化的思考
查看>>