【剑指Offer】二叉树的下一个结点

上图所示二叉树，找下一个结点，分四种情况考虑：

• 结点2——下一个结点为3
• 结点4——下一个结点为5
• 结点5——下一个结点为6
• 结点7——下一个结点为8

而下面所说的第二种情况类似于删除节点中的找后继节点，先判断是否存在右结点，再判断右结点是否存在左结点，如果存在左结点，就一直找到最下面的一个左结点，否则下一个结点就为右结点。

第一种情况是找父节点。

结点2和4都是在找父节点或者祖先结点；而5和7都是在找子节点或孙子结点。

而只有左边的结点才能够找祖先结点。

package jianzhiOffer;

class Node{
	int val;
	Node leftChild;
	Node rightChild;
	Node parrent;
	
	public Node(int value) {
		val = value;
		leftChild = null;
		rightChild = null;
		parrent = null;
	}
}

class CreatTree{
	Node root;
	
	public CreatTree() {
		this.root = null;
	}
	
	public void insert(int v) {
		Node newNode = new Node(v);
		Node current = root;
		Node parrent;
		
		if(root == null) {
			root = newNode;
		}
		else {
			while(true) {
				parrent = current;
				if(newNode.val<current.val) {
					current = current.leftChild;
					if(current==null) {
						parrent.leftChild = newNode;
						newNode.parrent = parrent;
						return;
					}
				}
				else {
					current = current.rightChild;
					if(current==null) {
						parrent.rightChild = newNode;
						newNode.parrent = parrent;
						return;
					}
				}
			}
		}
	
	}
	
	public void inOrder(Node localRoot) {
		if(localRoot!=null) {
			inOrder(localRoot.leftChild);
			System.out.print(localRoot.val + " ");
			inOrder(localRoot.rightChild);
		}
	}
}

public class NextNodeInBinaryTrees {
	
	public Node GetNext(Node pNode) {

		if(pNode.rightChild!=null) {
			Node nextNode = pNode.rightChild;

			while(nextNode.leftChild!=null) {
				nextNode = nextNode.leftChild;
			}
			return nextNode;
		}
		else {
			while(pNode.parrent != null) {
				Node par = pNode.parrent;

				if(par.leftChild==pNode) {
					return par;
				}
				pNode = pNode.parrent;
			}
		}
		
		
		return null;
	}
	
	public static void main(String[] args) {
		CreatTree tr = new CreatTree();
		NextNodeInBinaryTrees next = new NextNodeInBinaryTrees();
		
		tr.insert(5);
		tr.insert(3);
		tr.insert(2);
		tr.insert(4);
		tr.insert(7);
		tr.insert(6);
		tr.insert(8);
		
		Node root = tr.root;
		tr.inOrder(root);
		System.out.println();

		System.out.print(next.GetNext(root.leftChild.rightChild).val);
	}
}