2 回答

TA貢獻(xiàn)1765條經(jīng)驗(yàn) 獲得超5個(gè)贊
你的結(jié)果對我來說是正確的。稀疏性的原因是這是二叉樹基于數(shù)組的支持結(jié)構(gòu)的典型特征。如果樹不完整,則由于空元素表示未填充的子樹,因此存在浪費(fèi)的條目。由于 BST 通常需要平衡以保持最佳時(shí)間復(fù)雜度,因此基于鏈接節(jié)點(diǎn)的方法是典型的解決方案,它使旋轉(zhuǎn)和平衡更容易。
通常,數(shù)組支持結(jié)構(gòu)用于二進(jìn)制堆,它受益于數(shù)組在堆分配節(jié)點(diǎn)和指針上的內(nèi)存布局和速度;堆操作不允許稀疏性,并且很容易使用您在此處使用的相同父子關(guān)系在線性結(jié)構(gòu)中進(jìn)行推理。
話雖如此,您可以大大簡化代碼:
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貢獻(xiàn)1776條經(jīng)驗(yàn) 獲得超12個(gè)贊
我沒有檢查代碼,但結(jié)果對我來說是正確的。數(shù)組中的第一項(xiàng)是根。然后接下來的兩個(gè)是等級 1 節(jié)點(diǎn)然后接下來的 4 個(gè)是等級 2 節(jié)點(diǎn)。那么接下來的 8 個(gè)是 rank 4 節(jié)點(diǎn) 你的結(jié)果應(yīng)該是
添加回答
舉報(bào)