在二叉树中找到一个节点的后继节点

在二叉树中找到一个节点的后继节点

现在有一种新的二叉树节点类型如下:

public class Node {
public int value;
public Node left;
public Node right; 
public Node parent;
public Node(int data) { 
    this.value = data; 
    }
} 

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。 假设有一 棵Node类型的节点组成的二叉树, 树中每个节点的parent指针都正确地指向自己的父节点, 头节点的parent指向null。 只给一个在二叉树中的某个节点 node, 请实现返回node的后继节点的函数。 在二叉树的中序遍历的序列中, node的下一个节点叫作node的后继节点。

class PNode {
     public int value;
     public PNode left;
     public PNode right;
     public PNode parent;
     public PNode(int data) {
         this.value = data;
     }
 }

 public static PNode getSuccessorNode(PNode node){
     if (node == null) return node;
     if (node.right != null) return mostLeftNode(node.right);
     else {
         PNode parent = node.parent;
         while (parent != null && parent.left != node){
             node = parent;
             parent = node.parent;
         }
         return parent;
     } 
 }

 public static PNode mostLeftNode(PNode node){
     if (node == null) return node;
     while (node.left != null){
         node = node.left;
     }
     return node;
 }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券