python樹的雙親存儲結(jié)構(gòu)的實現(xiàn)示例

更新時間：2023年11月24日 11:49:04 作者：Guff_hys

本文主要介紹了python樹的雙親存儲結(jié)構(gòu),這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu),采用元素形如“[結(jié)點值,雙親結(jié)點索引]”的列表表示,感興趣的可以了解一下

這種存儲結(jié)構(gòu)是一種順序存儲結(jié)構(gòu)，采用元素形如“[結(jié)點值，雙親結(jié)點索引]”的列表表示。通常每個結(jié)點有唯一的索引(或者偽地址）,根結(jié)點的索引為0，它沒有雙親結(jié)點，其雙親結(jié)點的索引為-1。例如，所示的樹對應的雙親存儲結(jié)構(gòu)如下：

樹的雙親存儲結(jié)構(gòu)

t=[["A",-1],["B",0],["C",0],["D",1],["E",1],["F",1],["G",4]]

在該存儲結(jié)構(gòu)t中，索引為i的結(jié)點是t[i]，其中t[i][0]為結(jié)點值，t[i][1]為該結(jié)點的雙親結(jié)點的索引。

若一棵樹采用雙親在儲結(jié)構(gòu)存儲，設計一個算法求指定索引是i的結(jié)點的層次。

解：用cnt 表示索引i的結(jié)點的層次（初始為1）。沿著雙親指針向上移動，當沒有到達根結(jié)點時循環(huán)：cnt 增1，i向上移動一次。當?shù)竭_根結(jié)點時cnt 恰好為原索引i結(jié)點的層次，最后返回cnt。對應的算法如下：

def find_level(parent, i):
    cnt = 1
    while parent[i] != -1:
        cnt += 1
        i = parent[i]
    return cnt

python樹的雙親存儲結(jié)構(gòu)：

class FNode():
    def __init__(self,name=None,i=None):#name為數(shù)據(jù),i為其對應的父節(jié)點下標
        self.node=[name,i]
class ftree():#存儲節(jié)點數(shù)據(jù)
    def __init__(self):
        self.data=[]
    #增加
    def add(self,name,i):#添加節(jié)點數(shù)據(jù)進入數(shù)的結(jié)構(gòu)
        p = FNode(name,i)#建立節(jié)點
        self.data.append(p.node)#添加進入
    #創(chuàng)建
    def CreateTree(self,arr):#傳入對應數(shù)據(jù)建立數(shù)arr為一個樹關(guān)系的二維列表
        for i in arr:
            self.data.append(i)
    #刪除
    def Dex(self,name,i):#給出節(jié)點的name和i進行刪除
        for j in range(len(self.data)):
            if self.data[j][0]==name and self.data[j][1]==i:
                self.data.pop(j)
                break
    # 修改節(jié)點數(shù)據(jù)
    def alter(self,name,i,n_name):
        for j in range(len(self.data)):
            if self.data[j][0]==name and self.data[j][1]==i:
                self.data[j][0]=n_name
                break
    #查找節(jié)點
    def find(self,name,i):
        for j in range(len(self.data)):
            if self.data[j][0]==name and self.data[j][1]==i:
                return self.data[j]

    #遍歷樹結(jié)構(gòu),雙親存儲單位的結(jié)構(gòu)決定了它只能層次遍歷
    def display(self):
        for i in range(len(self.data)):
            print(self.data[i][0],end=" ")
        print()

t = [['A',-1],['B',0],['C',0],['D',1],['E',1],['F',1],['G',4]]
tree_1 = ftree()
tree_1.CreateTree(t)
tree_1.display()
tree_1.add('H',4)
tree_1.display()
tree_1.Dex('H',4)
tree_1.display()
tree_1.alter('G',4,'5')
tree_1.display()
print(tree_1.find('A',-1))

雙親存儲結(jié)構(gòu)利用了每個結(jié)點（根節(jié)點除外）有啡一雙親的性質(zhì)。在這種存儲結(jié)構(gòu)中，求某個結(jié)點的雙親結(jié)點十分容易，但求某個結(jié)點的孩子結(jié)點時需要遍歷整個結(jié)構(gòu)。

到此這篇關(guān)于python樹的雙親存儲結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)python樹的雙親存儲結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: