Python-简单的树结构实现

#定义一个树结构#定义一个树状结构classNode():def__init__(self,father=None,data=None,child=None):self.father=fatherself.data=data#数据self.child=[]#子树，是一个数列ifchild!=None:foriinchild:self.child.append(i)classTree():def__init__(self):self.root=Node()self.datalist=[]#容器，数据容器self.nodelist=[]#栈defadd_root(self,data,child=None,father=None):#创建根节点ifself.root.data==None:#判断是否为跟树self.root=Node(data=data,child=child)else:node=self.deep_first_search(father)#查询已有的节点ifnode==None:e='父节点选择错误'raiseValueError#'父节点选择错误'root=Node(father=father,data=data)node.child.append(root)defdeep_first_search(self,outer_data=None):#深度优先遍历data=self.root.data#取出节点数据self.nodelist.append(self.root)ifdata!=None:while1:data_child=self.nodelist[-1]#取出栈中的对象self.nodelist.remove(self.nodelist[-1])#取出栈中的对象data=data_child.dataself.datalist.append(data)iflen(data_child.child)!=0:#判断是否有子节点foriindata_child.child:self.nodelist.append(i)ifdata==outer_data:self.datalist=list(set(self.datalist))returndata_childiflen(self.nodelist)==0:breakself.datalist=list(set(self.datalist))returnNonedefbreadth_first_search(self,outer_data=None):#广度优先遍历data=self.root.data#取出节点数据self.nodelist.append(self.root)ifdata!=None:while1:data_child=self.nodelist[0]#取出栈中的对象self.nodelist.remove(self.nodelist[0])#取出栈中的对象data=data_child.dataself.datalist.append(data)iflen(data_child.child)!=0:#判断是否有子节点foriindata_child.child:self.nodelist.append(i)ifdata==outer_data:self.datalist=list(set(self.datalist))returndata_childiflen(self.nodelist)==0:breakself.datalist=list(set(self.datalist))returnNonedefpath(self,data):#查询路径ob=self.breadth_first_search(data)pa=[]while1:pa.append(ob.data)ifob.father!=None:#print(ob.father)ob=self.breadth_first_search(ob.father)else:breakreturnpaif__name__=='__main__':tree=Tree()tree.add_root(data='a')tree.add_root(data='b',father='a')tree.add_root(data='c',father='a')tree.add_root(data='d',father='c')tree.add_root(data='e',father='c')tree.deep_first_search()print(tree.path('d'))