设计优秀网站作品,网站开发前端要学什么,推广普通话手抄报模板,网站页面关键词都一样这种存储结构是一种顺序存储结构#xff0c;采用元素形如“[结点值#xff0c;双亲结点索引]”的列表表示。通常每个结点有唯一的索引(或者伪地址#xff09;,根结点的索引为0#xff0c;它没有双亲结点#xff0c;其双亲结点的索引为-1。例如#xff0c;所示的树对应的双…这种存储结构是一种顺序存储结构采用元素形如“[结点值双亲结点索引]”的列表表示。通常每个结点有唯一的索引(或者伪地址,根结点的索引为0它没有双亲结点其双亲结点的索引为-1。例如所示的树对应的双亲存储结构如下 #树的双亲存储结构
t[[A,-1],[B,0],[C,0],[D,1],[E,1],[F,1],[G,4]] 在该存储结构t中索引为i的结点是t[i]其中t[i][0]为结点值t[i][1]为该结点的双亲结点的索引。 若一棵树采用双亲在储结构存储设计一个算法求指定索引是i的结点的层次。 解用cnt 表示索引i的结点的层次初始为1。沿着双亲指针向上移动当没有到达根结点时循环cnt 增1i向上移动一次。当到达根结点时cnt 恰好为原索引i结点的层次最后返回cnt。对应的算法如下 python
def find_level(parent, i):cnt 1while parent[i] ! -1:cnt 1i parent[i]return cntpython树的双亲存储结构
class FNode():def __init__(self,nameNone,iNone):#name为数据,i为其对应的父节点下标self.node[name,i]
class ftree():#存储节点数据def __init__(self):self.data[]#增加def add(self,name,i):#添加节点数据进入数的结构p FNode(name,i)#建立节点self.data.append(p.node)#添加进入#创建def CreateTree(self,arr):#传入对应数据建立数arr为一个树关系的二维列表for i in arr:self.data.append(i)#删除def Dex(self,name,i):#给出节点的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# 修改节点数据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_namebreak#查找节点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]#遍历树结构,双亲存储单位的结构决定了它只能层次遍历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))
双亲存储结构利用了每个结点根节点除外有啡一双亲的性质。在这种存储结构 中求某个结点的双亲结点十分容易但求某个结点的孩子结点时需要遍历整个结构。
