将二叉树中的重复节点映射到哈希表中

huangapple go评论64阅读模式
英文:

Mapping duplicate nodes from binary tree to a hashmap

问题

我正在尝试创建一个函数,该函数搜索二叉树以查找重复节点,并将每个唯一节点在树中出现的次数存储到哈希映射中。

以下是问题的更具体版本:

"创建一个名为YourBinaryTree的公共类,该类扩展了BinaryTree。覆盖protected Map<Object, Integer> valueCount()方法,并使其返回一个将树中的每个对象映射到其出现次数的映射。如果树为空(根为null),则应返回一个空的Map。不要在类中声明任何字段。"

我尝试了递归搜索树,但似乎无法正常工作,因为重复的节点会创建新的映射,而不是替换旧的值。

以下是我迄今为止编写的代码:

import java.util.Map;
import java.util.HashMap;

public class YourBinaryTree extends BinaryTree
{
    protected Map&lt;Object, Integer&gt; valueCount()
    {
        Map&lt;Object, Integer&gt; treeMap = new HashMap&lt;&gt;();
        
        if(root == null)
        {
            return treeMap;
        }
        
        if(root.left == null &amp;&amp; root.right == null)
        {
            treeMap.put(root.value , 1);
            return treeMap;
        }
        
        return valueCount(root);
    }
    
    private Map&lt;Object, Integer&gt; valueCount(Node current)
    {
        Map&lt;Object, Integer&gt; treeMap = new HashMap&lt;&gt;();
        
        if(current == null)
        {
            return treeMap;
        }
        
        if(treeMap.containsKey(current.value))
        {
            treeMap.put(current.value, treeMap.get(current) + 1);
        }
        else
        {
            treeMap.put(current.value, 1);
        }
        
        treeMap.putAll(valueCount(current.left));
        treeMap.putAll(valueCount(current.right));
        
        return treeMap;
    }
}

以下是创建二叉树的类的代码:

public class BinaryTree
{
    protected class Node
    {
        protected Object value;
        protected Node left;
        protected Node right;
        
        Node(Object setValue)
        {
            value = setValue;
        }
    }
    protected Node root;
}

我尝试使用merge函数,但我不太确定如何实现它。非常感谢您的帮助!

英文:

I'm trying to create a function that searches through a binary tree looking for duplicate nodes and stores the number of times each unique node appears in the tree into a hashmap.

Here's a more specific version of the question -

"Create a public class called YourBinaryTree that extends BinaryTree. Override protected Map<Object, Integer> valueCount() and have it return a Map mapping each object in the tree to the number of times that it appears. If the tree is empty (root is null) you should return an empty Map. Do not declare any fields in your class"

I'm tried recursively searching through the tree but I can't seem to get it to work because duplicate nodes are creating new mappings and not replace the values of old ones.

Here's the code I've written so far:

import java.util.Map;
import java.util.HashMap;
public class YourBinaryTree extends BinaryTree
{
protected Map&lt;Object, Integer&gt; valueCount()
{
Map&lt;Object, Integer&gt; treeMap = new HashMap&lt;&gt;();
if(root == null)
{
return treeMap;
}
if(root.left == null &amp;&amp; root.right == null)
{
treeMap.put(root.value , 1);
return treeMap;
}
return valueCount(root);
}
private Map&lt;Object, Integer&gt; valueCount(Node current)
{
Map&lt;Object, Integer&gt; treeMap = new HashMap&lt;&gt;();
if(current == null)
{
return treeMap;
}
if(treeMap.containsKey(current.value))
{
treeMap.put(current.value, treeMap.get(current) + 1);
}
else
{
treeMap.put(current.value, 1);
}
/*
Map&lt;Object, Integer&gt; treeMapLeft = new HashMap&lt;&gt;();
Map&lt;Object, Integer&gt; treeMapRight = new HashMap&lt;&gt;();
treeMapLeft.putAll(valueCount(current.left));
treeMapRight.putAll(valueCount(current.right));
treeMapRight.forEach(
(key, value)
-&gt; treeMapLeft.merge(key, value, (v1, v2) -&gt; v1+v2));
treeMap = treeMapLeft;
*/
treeMap.putAll(valueCount(current.left));
treeMap.putAll(valueCount(current.right));
return treeMap;
}
}

Here's the code for the class that creates the Binary Tree:

public class BinaryTree
{
protected class Node
{
protected Object value;
protected Node left;
protected Node right;
Node(Object setValue)
{
value = setValue;
}
}
protected Node root;
}

I've tried using the merge function but I'm really sure how to implement it. Any help would be very much appreciated, thank you! 将二叉树中的重复节点映射到哈希表中

答案1

得分: 2

We just need to do a simple recursive tree traversal:

import java.util.Map;
import java.util.HashMap;

public class YourBinaryTree extends BinaryTree {
    private void traverse_tree(Node root, Map&lt;Object, Integer&gt; objectCountMap) {
        if(root == null) {
            return;
        }
        objectCountMap.putIfAbsent(root, 0);
        objectCountMap.put(root, objectCountMap.get(root) + 1);
        traverse_tree(root.left, objectCountMap);
        traverse_tree(root.right, objectCountMap);
    }

    public Map&lt;Object, Integer&gt; valueCount()
    {
        Map&lt;Object, Integer&gt; objectCountMap = new HashMap&lt;&gt;();
        traverse_tree(root, objectCountMap);
        return objectCountMap;
    }
}

Be careful that the class of the key of objectCountMap should implement equals() and hashcode() method properly.

According to equals() and hashcode() of Object class, 2 objects are equal only when their memory addresses are equal.
For example:

Object obj1 = new Object();
Object obj2 = new Object();
Map&lt;Object, Integer&gt; countMap = new HashMap&lt;&gt;();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 1
countMap.get(obj2); // Returns 2 

-----------

Object obj1 = new Object();
Object obj2 = obj1 // obj2 has the same memory address as obj1
Map&lt;Object, Integer&gt; countMap = new HashMap&lt;&gt;();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 2
countMap.get(obj2); // Returns 2 
英文:

We just need to do a simple recursive tree traversal:

import java.util.Map;
import java.util.HashMap;

public class YourBinaryTree extends BinaryTree {
    private void traverse_tree(Node root, Map&lt;Object, Integer&gt; objectCountMap) {
        if(root == null) {
            return;
        }
        objectCountMap.putIfAbsent(root, 0);
        objectCountMap.put(root, objectCountMap.get(root) + 1);
        traverse_tree(root.left, objectCountMap);
        traverse_tree(root.right, objectCountMap);
    }

    public Map&lt;Object, Integer&gt; valueCount()
    {
        Map&lt;Object, Integer&gt; objectCountMap = new HashMap&lt;&gt;();
        traverse_tree(root, objectCountMap);
        return objectCountMap;
    }
}

Be careful that the class of the key of objectCountMap should implement equals() and hashcode() method properly.

According to equals() and hashcode() of Object class, 2 objects are equal only when their memory addresses are equal.
For example:

Object obj1 = new Object();
Object obj2 = new Object();
Map&lt;Object, Integer&gt; countMap = new HashMap&lt;&gt;();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 1
countMap.get(obj2); // Returns 2 

-----------

Object obj1 = new Object();
Object obj2 = obj1 // obj2 has same memory address as obj1
Map&lt;Object, Integer&gt; countMap = new HashMap&lt;&gt;();
countMap.put(obj1, 1);
countMap.put(obj2, 2);
countMap.get(obj1); // Returns 2
countMap.get(obj2); // Returns 2 

答案2

得分: 0

你正在在你的valueCount方法中创建一个新的映射,这个映射是空的,你需要在每次调用valueCount方法时传递你在重写的方法中创建的映射对象,以便更新它。所以你的方法将如下所示:

private void valueCount(Node current, HashMap<Object, Integer> treeMap) {
    // 你的其他代码
}
英文:

you are creating a new map in your valueCount method, which is empty, you need to pass your map object which is created in your overrided method in every call to value count method, to be updated. So your method wil look like this:

private void valueCount(Node current,HashMap&lt;Object,Integer&gt; treeMap){
//rest of your code
}

huangapple
  • 本文由 发表于 2020年8月8日 13:01:39
  • 转载请务必保留本文链接:https://go.coder-hub.com/63311992.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定