用地图实现树

Question

我有一个像这样的二叉树 -

现在我正在尝试使用 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个value，所以第二个没有插入到HashTable - binaryTree中？

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

提前致谢？

Answer 1

您似乎在尝试 "fold" 邻接列表到单个散列 table 中。这是可能的，但您需要将元素的类型更改为能够容纳两个整数的类型。

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

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 的数组而不是自定义 class，但使用这种表示的代码可读性会差：

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

用地图实现树

Implemetning Tree with Map

java

algorithm

data-structures

hashtable

binary-tree