Tree_GraphInorderSuccessorinBinarySearchTreeBST中找中序遍历的后继节点@CareerCup

原文&＃xff1a;

Write an algorithm to find the ‘next’ node (i.e., in-order successor) of a given node in a binary search tree where each node has a link to its parent.

译文&＃xff1a;

给定二叉查找树的一个结点&＃xff0c; 写一个算法查找它的“下一个”结点(即中序遍历后它的后继结点)&＃xff0c; 其中每个结点都有指向其父亲的链接。

思路&＃xff1a;

CC150的解法是有用到parent指针。

就是看看有没有右孩子&＃xff0c;如果有&＃xff0c;则好办&＃xff0c;直接找右子树的最小值。

如果没有则&＃xff0c;往上&＃xff08;parent&＃xff09;找&＃xff0c;直到找到某个parent比当前值大&＃xff01;

如果不允许parent指针&＃xff0c;就从root节点往下找&＃xff0c;可参考&＃xff1a;http://blog.csdn.net/fightforyourdream/article/details/19860143

package Tree_Graph;import CtCILibrary.TreeNode;public class S4_6 {// 有parent指针的情况&＃xff0c;分有右孩子和没有右孩子两种情况public static TreeNode inorderSucc(TreeNode node) {if(node &＃61;&＃61; null) {return null;}if(node.right !&＃61; null) { // 有右孩子return leftMostChild(node.right);} else { // 没有右孩子TreeNode cur &＃61; node;TreeNode parent &＃61; node.parent;
// while (parent!&＃61;null && parent.left!&＃61;cur) {while (parent!&＃61;null && node.data > parent.data) {cur &＃61; parent;parent &＃61; parent.parent;}return parent;}}// 找一个树的最小节点public static TreeNode leftMostChild(TreeNode root) {if(root &＃61;&＃61; null) {return null;}while (root.left !&＃61; null) {root &＃61; root.left;}return root;}public static void main(String[] args) {int[] array &＃61; {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};TreeNode root &＃61; TreeNode.createMinimalBST(array);for (int i &＃61; 0; i " &＃43; next.data);} else {System.out.println(node.data &＃43; "->" &＃43; null);}}}
}