我见过的BST的大多数例子都是这种形式
Class Node { Node left; Node right; Key key; Value value; }
但是BST看起来像具有额外约束的二进制堆的特定形式，即左子值应小于父值，该值应小于右节点值 .
二进制堆很容易使用数组实现 . 为什么不使用数组创建BST，以确保维护这个额外的规则？这样做的缺点是什么？
答案很简单：你不能只是动态地改变数组的大小 .
之后不能只改变数组的大小 . 如果您要使用数组，则必须根据添加或删除的内容进行放大或缩小，这会导致不必要的开销，因为您必须将内容从旧数组复制到新数组中 .
使用相应地使用引用或指针允许你刚刚（重新）分配 left 和 right 到一个新的节点，只要你插入或将其设置为 null （或类似的东西），如果你删除它为您提供了更多的动态结构的元素 .
left
right
null
1 回答
答案很简单：你不能只是动态地改变数组的大小 .
之后不能只改变数组的大小 . 如果您要使用数组，则必须根据添加或删除的内容进行放大或缩小，这会导致不必要的开销，因为您必须将内容从旧数组复制到新数组中 .
使用相应地使用引用或指针允许你刚刚（重新）分配
left和right到一个新的节点，只要你插入或将其设置为null（或类似的东西），如果你删除它为您提供了更多的动态结构的元素 .