java - 用 map 实现树

Question

我有一个二叉树 -

            1
           / \
          3   5  
             / \  
            7   9  

现在我尝试使用 HashTable 表示树。所以我创建了一个 HashTable binaryTree -

HashTable binaryTree = new HashTable<Integer, Intgeger>();  

然后我尝试将项目添加到 binaryTree。我希望 1 作为 binaryTree 的键，它的所有子项(例如 - 3 和 5)作为它的值。所以我想把 -

binaryTree.put(1, 3);
binaryTree.put(1, 5);   

因为key 1有2个值，所以第二个没有插入HashTable - binaryTree？

如何将 3 和 5 添加到 binaryTree 中？还是有更好的数据结构来做到这一点？

提前致谢？

Answer 1

看起来您正在尝试将邻接列表“折叠”到单个哈希表中。这是可能的，但您需要将元素的类型更改为能够容纳两个整数的类型。

最常见的方法是使用 TreeNode 类:

class TreeNode {
    private final int left;
    private final int right;
    public int getLeft() { return left; }
    public int getRight() { return left; }
    TreeNode(int l, int r) { left = l; right = r; }
}

HashTable<Integer,TreeNode> binaryTree = new HashTable<Integer,TreeNode>();

现在插入看起来像这样:

binaryTree.put(1, new TreeNode(3, 5));

您也可以使用两个 int 的数组来代替自定义类，但是使用这种表示的代码可读性差:

HashTable<Integer,int[]> binaryTree = new HashTable<Integer,int[]>();
binaryTree.put(1, new int[] { 3, 5 });