返回二叉树中节点的父级 [英] Return parent of node in Binary Tree

问题描述

我正在编写代码以返回任何节点的父节点，但是我陷入了困境。我不想使用任何预定义的ADT。

I'm writing a code to return the parent of any node, but I'm getting stuck. I don't want to use any predefined ADTs.

//Assume that nodes are represented by numbers from 1...n where 1=root and even 
//nos.=left child and odd nos=right child.
public int parent(Node node){
    if (node % 2 == 0){
       if (root.left==node)
       return root;
    else
       return parent(root.left);
    }
    //same case for right
}

但是该程序无法正常工作并给出错误的结果。我的基本算法是该程序从 root 开始，检查它是在 left 还是在正确。如果是子节点，或者如果查询的节点是 else ，则与子节点一起递归。

But this program is not working and giving wrong results. My basic algorithm is that the program starts from the root checks if it is on left or on the right. If it's the child or if the node that was queried else, recurses it with the child.

推荐答案

尝试一下。它可能会起作用：

Try this .It may work :

public BinaryTreeNode getParent(BinaryTreeNode root, BinaryTreeNode node) {

    BinaryTreeNode lh = null, rh = null;
    if (null == root)
        return null;

    if (root.getLeft() == node || root.getRight() == node)
        return root;

    lh = getParent(root.getLeft(), node);
    rh = getParent(root.getRight(), node);

    return lh != null ? lh : rh;

}

这篇关于返回二叉树中节点的父级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！