Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
public TreeNode findNext(TreeNode node) { if(node == null) return null; if(node.parent==null || node.right != null) { // find left most child in right sub tree TreeNode next = node.right; while(next.left != null) next = next.left; return next; } else { // go up until we are on the left side of parent node TreeNode p = node.parent; while(p != null && p.left != node) { node = p; p = p.parent; } return p; } }
如果没有父节点的话,可以这么做:
public TreeNode findNext(TreeNode root, TreeNode node) { if(root == null || node == null) return null; if(node.right != null) { TreeNode n = node.right; while(n.left != null) { n = n.left; } return n; } TreeNode n = null; while(root != null) { if(root.val > node.val) { n = root; root = root.left; } else if(root.val < node.val) { root = root.right; } else { break; } } return n; }
Reference:
http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
相关推荐
450._Delete_Node_in_a_BST【LeetCode单题讲解系列】
A application about binary search tree, Insert, Delete, Find, Print node.
将bst文件放到MiKTeX的bst文件夹下自己新建的gbt7714-2005文件下,1)作者名称如 KERNER B S 的样式 GBT7714-2005NLang.bst 2)作者名称如 KERNER B S 的样式 GBT7714-2005NLang_UP.bst 3)作者名称如 Kerner B S 的...
BST纠偏调试步骤
The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than or equal to the node's key. Both the left ...
BST纠偏系统调试手册.pdf
该资源为国标参考文献的bst样式文件,GBT7714-2005NLang.bst样式文件。可以在论文参考文献排版时使用
BST自动纠偏系统
代码支持《数据结构与算法分析》中的BST数据结构C++代码
BST纠偏操作英文说明pdf,BST纠偏操作英文说明
解决springer论文参考文献引用乱序问题
BST-物料纠偏系统ERK 1000H使用手册pdf,BST-物料纠偏系统ERK 1000H使用手册
舵机供电模块超声波模块供电口舵机模块电机模块红外检测模块检测提示模块电源提示灯亚博 BST-V51 智能小车底板电路原理图。
BST物料纠偏系统 ekrPro com40 使用手册
解决IEE模板同名作者不显示问题,放入到latex目录即可
BST24108 PCI总线,8通道CAN总线通讯卡,光隔离,支持定时发送 BST24208-01 CPCI(3U前出线)总线,8通道CAN总线通讯卡,磁隔离,支持定时发送 BST24212 CPCI(3U前出线)总线,20通道CAN总线通讯卡,磁隔离,支持...
此代码为原创代码 主要描述排序二叉树即BST的创建,以及二叉树的中序遍历,BST的广度遍历下的层序遍历。
BST的定义,非常标准,非常值得参考,,对于入门的同学很有用
BST数据结构问题的c++代码实现,自己写的,希望对大家有帮助
BST-BMP180-DS000-07.pdf英文资料