在一颗二叉树中寻找一个结点的后继结点(前驱结点)

  • 找后继结点
  • 找前驱结点

找后继结点

首先知道什么是后继结点，就是二叉树中序遍历的序列中，某个结点紧随的那个结点比如下面的二叉树以及对应的中序遍历顺序。

image.png

则4的后继是2 ，2的后继是5，7的后继是null。

在树的结构中，每个结点有一个指向父亲的域parent，看如下结构

  1.     static class Node{
  2.         public int value;
  3.         public Node left;
  4.         public Node right;
  5.         public Node parent;
  7.         public Node(int value) {
  8.             this.value = value;
  9.         }
  10.     }

那么如何快速的寻找当前结点node后继结点呢? 其实只需要分为两种情况

  • 第一，如果node结点有右子树，那么就是右子树上最左的结点，例如上图的２的右子树上的最左结点是5，5的右子树上最左的结点是8，1的右子树上最左的结点是9，3的右子树上最左的结点是7。
  • 第二，如果node结点没有右子树，那么要分两种情况 : a. 看当前结点node 是不是它父亲(node.parent)的左孩子，如果是，那么它父亲(node.parent)就是它的后继；b.如果当前结点是它父亲的右孩子(node.parent.right == node)，那么就向上不停的寻找它的后继结点，即当前结点为node，它的父亲为parent，如果node还是parent的右孩子，就令node= parent，parent = parent.parent，一直向上，直到parent.left = node，就停止，此时parent就是当初要找的结点的后继。

(1) 对于上面的第二种情况看上面的例子，首先a情况

image.png

(2) 然后再看第二种情况的b ，也就是往上找后继的过程

image.png

找前驱结点

这个和找后继是同理的:

  • 当一个结点有左子树的时候，就是最左子树的最右结点；
  • 没有左子树的时候，a. 看当前结点node是不是它父亲(node.parent)的右孩子，如果是，那么它父亲(node.parent)就是它的前驱；b. 如果当前结点是它父亲的左孩子(node.parent.left == node)，那么就向上不停的寻找它的前驱结点，即当前结点为node，它的父亲为parent，如果node还是parent的左孩子，就令node= parent，parent = parent.parent，一直向上，直到parent.right = node，就停止，此时parent就是当初要找的结点的前驱。

完整的测试代码如下

  1. /**
  2.  * 寻找结点的后继和前驱结点
  3.  */
  4. public class SuccessorNode {
  6.     static class Node {
  7.         public int value;
  8.         public Node left;
  9.         public Node right;
  10.         public Node parent;
  12.         public Node(int value) {
  13.             this.value = value;
  14.         }
  15.     }
  17.     //寻找某个结点的后继结点
  18.     static Node getSuccessorNode(Node node) {
  19.         if (node == null) 
  20.             return null;
  21.         if (node.right != null) 
  22.             return getMostLeft(node.right);//第一种情况　　结点的右子树为null
  23.         else {  //第二种情况
  24.             Node parent = node.parent;
  25.             while (parent != null && parent.left != node) {
  26.                 node = parent;
  27.                 parent = node.parent;
  28.             }
  29.             return parent;
  30.         }
  31.     }
  33.     //找到某个结点的最左边的结点
  34.     static Node getMostLeft(Node node) {
  35.         if (node == null)
  36.             return null;
  37.         while (node.left != null)
  38.             node = node.left;
  39.         return node;
  40.     }
  43.     //寻找某个结点的前驱结点
  44.     static Node getPrecursorNode(Node node) {
  45.         if (node == null)
  46.             return null;
  47.         if (node.left!= null)
  48.             return getMostRight(node.left);//第一种情况　　结点的右子树为null
  49.         else {  //第二种情况
  50.             Node parent = node.parent;
  51.             while (parent != null && parent.right != node) {
  52.                 node = parent;
  53.                 parent = node.parent;
  54.             }
  55.             return parent;
  56.         }
  57.     }
  59.     //找到某个结点的最右边的结点
  60.     static Node getMostRight(Node node) {
  61.         if (node == null)
  62.             return null;
  63.         while (node.right != null)
  64.             node = node.right;
  65.         return node;
  66.     }
  68.     public static void main(String[] args) {
  70.         //先创建上图的树
  71.         Node head = new Node(1);
  72.         head.left = new Node(2);
  73.         head.left.parent = head;
  74.         head.left.left = new Node(4);
  75.         head.left.left.parent = head.left;
  76.         head.left.right = new Node(5);
  77.         head.left.right.parent = head.left;
  78.         head.left.right.right = new Node(8);
  79.         head.left.right.right.parent = head.left.right;
  80.         head.right = new Node(3);
  81.         head.right.parent = head;
  82.         head.right.left = new Node(6);
  83.         head.right.left.parent = head.right;
  84.         head.right.left.left = new Node(9);
  85.         head.right.left.left.parent = head.right.left;
  86.         head.right.right = new Node(7);
  87.         head.right.right.parent = head.right;
  89.         System.out.println("----------test Successor----------");
  90.         Node node = head; //测试1
  91.         System.out.println(node.value + "'s next : " + getSuccessorNode(node).value);
  93.         node = head.left.left; //测试4
  94.         System.out.println(node.value + "'s next : " + getSuccessorNode(node).value);
  96.         node = head.left.right.right; // 测试8
  97.         System.out.println(node.value + "'s next : " + getSuccessorNode(node).value);
  100.         System.out.println("----------test Precursor----------");
  102.         node = head; //测试1
  103.         System.out.println(node.value + "'s next : " + getPrecursorNode(node).value);
  105.         node = head.right.left.left; // 测试9
  106.         System.out.println(node.value + "'s next : " + getPrecursorNode(node).value);
  108.     }
  109. }

运行结果

image.png