/*
* 前驱节点,中序遍历的前面的节点
* 如果有左子树,那么就是左子树上最右的节点,如果没有左子树,那么一起向上移动,直到该节点位于右子树,
*/
public class 二叉树的前驱节点 { 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 getpreNode(Node node) { if(node == null) { return null; } if(node.left != null) { return getrightmose(node.left); }else { Node pa = node.parent; while(pa != null && pa.right != node) { node = pa; pa = node.parent; } return pa; } } public static Node getrightmose(Node node) { if(node == null) { return null; } while(node.right != null) { node = node.right; } 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.right; System.out.println(getpreNode(test).value); } }