在二叉搜索树中查找表亲

Question

在二叉树中，如果两个节点处于同一级别并且具有不同的父节点，则它们是表亲。

为此，在二叉搜索树中，我使用树图将每个键关联到一个级别，并使用树图将每个键关联到父级。然后我在 root 上调用 BFS，它设置各种键的级别。

但是我的 isCousins 函数即使对于我在代码中创建的二叉树中 cousins.For 示例的节点也给出 false，12 和 50 是表兄弟，但它仍然打印 false。

这是我的源代码。

import java.util.*;
class BST
{
 Node root;
 LinkedList<Node> q=new LinkedList<Node>();
 TreeMap<Integer,Integer> level=new TreeMap<Integer,Integer>(); 
 TreeMap<Integer,Node> parent=new TreeMap<Integer,Node>(); 
 Node insert(Node x,int key)
 {
     if(x==null)
     {
         parent.put(key,null);
         return new Node(key,null,null,null);
     }
     else if(x.key<key)
     {
         x.right=insert(x.right,key);
         x.right.parent=x;
         parent.put(key,x.right.parent);
         return x;
     }
     else if(x.key>key)
     {
         x.left=insert(x.left,key);         
         x.left.parent=x;
         parent.put(key,x.left.parent);
         return x;
     }
     else { x.key=key; return x;}
 }
 public void BFS(Node r)
 {
     if(r==null)
      return;
     if(r.parent==null)
      level.put(r.key,0);
     else level.put(r.key,level.get(r.parent.key)+1);     
     q.add(r);

     while(q.size()!=0)
     {
        Node n=q.poll();
        BFS(n.left);
        BFS(n.right);
     }
 } 
public boolean isCousins(int a,int b)
{
 BFS(root);
 if(level.get(a)==level.get(b)&&parent.get(a)!=parent.get(b))
  return true;
 else return false;
}
public static void main(String []args)
 {
     BST tree1=new BST();
     tree1.root=null;
     tree1.root=tree1.insert(tree1.root,15);
     tree1.root=tree1.insert(tree1.root,66);
     tree1.root=tree1.insert(tree1.root,5);
     tree1.root=tree1.insert(tree1.root,3);
     tree1.root=tree1.insert(tree1.root,12);
     tree1.root=tree1.insert(tree1.root,75);
     tree1.root=tree1.insert(tree1.root,50);     
     System.out.println(tree1.isCousins(12,50));
 }
} 
class Node
{
 Node left,right,parent;
 int key;
 int level;
 Node(int k,Node l,Node r,Node p)
 {
     key=k;
     left=l;
     right=r;
     parent=p;
 }
}

Answer 1

节点不是原始类型，所以你不能有这样的代码：

parent.get(a)!=parent.get(b);

使用基本运算符比较非基本类型只是比较对象引用，而不是对象本身的实际内容。相反，写：

!parent.get(a).equals(parent.get(b));

由于您的 TreeMap 级别中的值是整数而不是整数，因此您不应将它们与 == 进行比较。相反，请再次使用 .equals() 方法。

level.get(a).equals(level.get(b));

此外，

level.get(a).equals(level.get(b))&&!parent.get(a).equals(parent.get(b));

是一个布尔语句，所以你可以只输入

return level.get(a).equals(level.get(b))&&!parent.get(a).equals(parent.get(b));

而不是

if(level.get(a).equals(level.get(b))&&!parent.get(a).equals(parent.get(b)))
   return true;
return false;

Answer 2

由 Patrick Murphy 提供，由于小错误导致错误输出，我使用以下条件很容易纠正：

if(parent.get(key)==null)

正确的代码是：

import java.util.*;
class BST
{
 Node root;
 LinkedList<Node> q=new LinkedList<Node>();
 TreeMap<Integer,Integer> level=new TreeMap<Integer,Integer>(); 
 TreeMap<Integer,Node> parent=new TreeMap<Integer,Node>(); 
 Node insert(Node x,int key)
 {
     if(x==null)
     {
         parent.put(key,null);
         return new Node(key,null,null,null);
     }
     else if(x.key<key)
     {
         x.right=insert(x.right,key);
         x.right.parent=x;
         if(parent.get(key)==null)
         parent.put(key,x);
         return x;
     }
     else if(x.key>key)
     {
         x.left=insert(x.left,key);         
         x.left.parent=x;
         if(parent.get(key)==null)
         parent.put(key,x);
         return x;
     }
     else { x.key=key; return x;}
 }
 public void BFS(Node r)
 {
     if(r==null)
      return;
     if(r.parent==null)
      level.put(r.key,0);
     else level.put(r.key,level.get(r.parent.key)+1);     
     q.add(r);

     while(q.size()!=0)
     {
        Node n=q.poll();
        BFS(n.left);
        BFS(n.right);
     }
 }
 public static void main(String []args)
 {
     BST tree1=new BST();
     tree1.root=null;
     tree1.root=tree1.insert(tree1.root,15);
     tree1.root=tree1.insert(tree1.root,66);
     tree1.root=tree1.insert(tree1.root,5);
     tree1.root=tree1.insert(tree1.root,3);
     tree1.root=tree1.insert(tree1.root,12);
     tree1.root=tree1.insert(tree1.root,75);
     tree1.root=tree1.insert(tree1.root,50);
     System.out.println(tree1.isCousins(66,75));
}
public boolean isCousins(int a,int b)
{
 BFS(root);
 if(level.get(a)==level.get(b)&&parent.get(a)!=parent.get(b))
  return true;
 else return false;
}
} 
class Node
{
 Node left,right,parent;
 int key;
 int level;
 Node(int k,Node l,Node r,Node p)
 {
     key=k;
     left=l;
     right=r;
     parent=p;
 }
}

在二叉搜索树中查找表亲

Finding Cousins in binary search tree

java

binary-tree

breadth-first-search