2 回答

TA貢獻1765條經驗 獲得超5個贊
你的結果對我來說是正確的。稀疏性的原因是這是二叉樹基于數組的支持結構的典型特征。如果樹不完整,則由于空元素表示未填充的子樹,因此存在浪費的條目。由于 BST 通常需要平衡以保持最佳時間復雜度,因此基于鏈接節點的方法是典型的解決方案,它使旋轉和平衡更容易。
通常,數組支持結構用于二進制堆,它受益于數組在堆分配節點和指針上的內存布局和速度;堆操作不允許稀疏性,并且很容易使用您在此處使用的相同父子關系在線性結構中進行推理。
話雖如此,您可以大大簡化代碼:
class BST {
? constructor() {
? ? this.array = [];
? }
? insert(value, ix=0) {
? ? if (this.array[ix] === undefined) {
? ? ? this.array[ix] = value;
? ? }
? ? else if (value < this.array[ix]) {
? ? ? this.insert(value, ix * 2 + 1);
? ? }
? ? else {
? ? ? this.insert(value, ix * 2 + 2);
? ? }
? }
}
/*
? ? 2
? ?/ \
? 0? ?3
? ? ? ?\
? ? ? ? 10
? ? ? ? ?\
? ? ? ? ? 30
*/
const bst = new BST();
[2, 0, 3, 10, 30].forEach(e => bst.insert(e));
console.log(bst.array);

TA貢獻1776條經驗 獲得超12個贊
我沒有檢查代碼,但結果對我來說是正確的。數組中的第一項是根。然后接下來的兩個是等級 1 節點然后接下來的 4 個是等級 2 節點。那么接下來的 8 個是 rank 4 節點 你的結果應該是
添加回答
舉報