Tree_Graph Inorder Successor in Binary Search Tree BST中找中序遍历的后继节点 @CareerCup

原文：

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.

译文：

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

思路：

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

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

如果没有则，往上（parent）找，直到找到某个parent比当前值大！

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

package Tree_Graph;

import CtCILibrary.TreeNode;

public class S4_6 {

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