二叉树结构定义如下：
public static class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; } }
后继结点：在一棵二叉树中，在中序遍历中，一个结点的下一个结点是谁！
大多数人普遍能想到的办法是，借助该结点往父结点指的指针，找到头结点，然后再中序遍历整棵树，然后找到后继结点。但是此种方法时间复杂度必然是O(N)。因为遍历二叉树本质是递归序。所以，有没有办法可以不用遍历二叉树，后继结点离给定的结点距离为K的话，可以直接找到呢？如果可以，那么时间复杂度就是O(K）。
我们都知道，中序遍历顺序是左根右，所以如果一个结点有右树的话，该结点的后继结点必然是该结点右树上最左的结点
所以同理，我们可以认识知道，前驱结点（在一棵二叉树中，在中序遍历中，一个结点的前一个结点是谁）：如果一个结点有左树的话，该结点的前驱结点就是该结点左树上最右的结点。当然，本篇文章我们只讨论后继结点的问题。
那么如果这个结点没右孩子呢？，这种情况它的后继结点怎么找呢？
x结点的后继节点：某一个结点（用?代替）的整颗左树上的最右结点是x，则？就是x的后继结点，但是整棵树的最右结点没有后继。 x就是？的前驱结点
附上截图，方便大家理解
package com.harrison.class07; public class Code07_SuccessorNode { public static class Node { public int value; public Node left; public Node right; public Node parent; public Node(int data) { this.value = data; } } public static Node getSuccessorNode(Node node) { if(node==null) { return node; } if(node.right!=null) {// 给定的结点有右孩子 return getLeftMost(node.right); }else {// 给定的结点无右孩子 Node parent=node.parent; while(parent!=null && parent.right==node) {// 当前结点不是父结点的左孩子 node=parent; parent=node.parent; } return parent; } } public static Node getLeftMost(Node node) { if(node==null) { return node; } while(node.left!=null) { node=node.left; } return node; } public static void main(String[] args) { Node head = new Node(6); head.parent = null; head.left = new Node(3); head.left.parent = head; head.left.left = new Node(1); head.left.left.parent = head.left; head.left.left.right = new Node(2); head.left.left.right.parent = head.left.left; head.left.right = new Node(4); head.left.right.parent = head.left; head.left.right.right = new Node(5); head.left.right.right.parent = head.left.right; head.right = new Node(9); head.right.parent = head; head.right.left = new Node(8); head.right.left.parent = head.right; head.right.left.left = new Node(7); head.right.left.left.parent = head.right.left; head.right.right = new Node(10); head.right.right.parent = head.right; Node test = head.left.left;// 1 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.left.right;// 2 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left;// 3 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.right;// 4 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.left.right.right;// 5 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head;// 6 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.left.left;// 7 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.left;// 8 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right;// 9 System.out.println(test.value + " next: " + getSuccessorNode(test).value); test = head.right.right; // 10's next is null System.out.println(test.value + " next: " + getSuccessorNode(test)); } }
