[發(fā)明專利]一種用于二叉樹添加和刪除結(jié)點(diǎn)的內(nèi)存分配方法

在審

• 申請?zhí)枺?/td>: 202011084048.7
• 申請日: 2020-10-12
• 公開（公告）號: CN112328389A
• 公開（公告）日: 2021-02-05
• 發(fā)明（設(shè)計）人: 龍恢;管志堅
• 申請（專利權(quán)）人: 長沙新弘軟件有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F12/02
• 代理公司: 長沙市標(biāo)致專利代理事務(wù)所(普通合伙) 43218
• 代理人: 徐邵華

1.一種用于二叉樹添加和刪除結(jié)點(diǎn)的內(nèi)存分配方法，該方法的二叉樹中每個結(jié)點(diǎn)包含三個指針變量，一個父結(jié)點(diǎn)指針和兩個子結(jié)點(diǎn)指針，其特征在于：為二叉樹設(shè)置一個對應(yīng)的鏈表，用于構(gòu)建二叉樹的私有內(nèi)存池，初始狀態(tài)下鏈表為空；當(dāng)向二叉樹添加結(jié)點(diǎn)的操作從系統(tǒng)分配內(nèi)存時，分配兩倍結(jié)點(diǎn)尺寸大小的內(nèi)存塊，即地址空間中連續(xù)的兩個結(jié)點(diǎn)，一個首結(jié)點(diǎn)和一個尾結(jié)點(diǎn)，將首結(jié)點(diǎn)作為新增結(jié)點(diǎn)插入二叉樹，將尾結(jié)點(diǎn)標(biāo)記為影子結(jié)點(diǎn)并作為空閑內(nèi)存塊放入二叉樹對應(yīng)的鏈表。

2.根據(jù)權(quán)利要求1所述的一種用于二叉樹添加和刪除結(jié)點(diǎn)的內(nèi)存分配方法，其特征是：當(dāng)向二叉樹添加結(jié)點(diǎn)時，若對應(yīng)的鏈表不為空，則從鏈表中取出一個影子結(jié)點(diǎn)作為新增結(jié)點(diǎn)插入二叉樹。

3.根據(jù)權(quán)利要求1所述的一種用于二叉樹添加和刪除結(jié)點(diǎn)的內(nèi)存分配方法，其特征是：當(dāng)從二叉樹刪除結(jié)點(diǎn)時，若被刪除的結(jié)點(diǎn)是影子結(jié)點(diǎn)，則將影子結(jié)點(diǎn)設(shè)置為空閑狀態(tài)并放入二叉樹對應(yīng)的鏈表。

4.根據(jù)權(quán)利要求1所述的一種用于二叉樹添加和刪除結(jié)點(diǎn)的內(nèi)存分配方法，其特征是：當(dāng)從二叉樹刪除結(jié)點(diǎn)時，若被刪除的結(jié)點(diǎn)不是影子結(jié)點(diǎn)，則檢查對應(yīng)的影子結(jié)點(diǎn)是否被占用，若未被占用，則將對應(yīng)的影子結(jié)點(diǎn)從鏈表中取出，同被刪除的結(jié)點(diǎn)一并通過系統(tǒng)釋放其內(nèi)存資源。

5.根據(jù)權(quán)利要求4所述的一種用于二叉樹添加和刪除結(jié)點(diǎn)的內(nèi)存分配方法，其特征是：當(dāng)從二叉樹刪除結(jié)點(diǎn)時，若被刪除的結(jié)點(diǎn)對應(yīng)的影子結(jié)點(diǎn)已被占用，則將影子結(jié)點(diǎn)的三個指針變量和數(shù)據(jù)遷移到被刪除的結(jié)點(diǎn)，并用被刪除的結(jié)點(diǎn)替換掉二叉樹中對應(yīng)的影子結(jié)點(diǎn)，然后將影子結(jié)點(diǎn)設(shè)置為空閑狀態(tài)并放入二叉樹對應(yīng)的鏈表。

6.根據(jù)權(quán)利要求4所述的一種用于二叉樹添加和刪除結(jié)點(diǎn)的內(nèi)存分配方法，其特征是：當(dāng)從二叉樹刪除結(jié)點(diǎn)時，若被刪除的結(jié)點(diǎn)對應(yīng)的影子結(jié)點(diǎn)已被占用，則從鏈表中取出一個新的影子結(jié)點(diǎn)，將被占用的影子結(jié)點(diǎn)中三個指針變量和數(shù)據(jù)遷移到新的影子結(jié)點(diǎn)，并用新的影子結(jié)點(diǎn)替換掉二叉樹中被占用的影子結(jié)點(diǎn)，然后將被刪除的結(jié)點(diǎn)和對應(yīng)的影子結(jié)點(diǎn)一并通過系統(tǒng)釋放其內(nèi)存資源。