Python：树结构和数字代码？

Question

我使用的是Python，我有一些数据，我想把它们放到树格式中并分配代码。以下是一些示例数据：

Africa    North Africa    Algeria
Africa    North Africa    Morocco
Africa    West Africa     Ghana
Africa    West Africa     Sierra Leone

对于这些数据，什么是合适的树结构？在

另外，有没有一种方法可以让我从这个树结构中检索数字代码，这样我就可以像下面的例子一样查询数据并得到代码？在

^{pr2}$

感谢您的帮助-关于Python我还有很多东西要学习：）

Answer 1

一个表示树的即席POD（“普通旧数据”）类就可以了，类似于：

class Location(object):
  def __init__(self, data, parent)
    self.data = data
    self.parent = parent
    self.children = []

现在分配/读取data属性，或添加/删除子级，可能使用helper方法：

^{pr2}$

现在，要真正地将数据划分为树级别，一个简单的算法是查看具有公共级别数据的所有位置（如非洲），并为它们分配一个位置，然后递归地为下一个级别的数据分配位置。在

因此，对于非洲，您可以使用data=Africa创建一个位置。然后，它将有一个定位子对象用于北非、西非等。在

对于“获取代码”，有一个字典将每个国家映射到其位置节点，并使用节点中的父链接。在每个级别从节点遍历到顶部（直到parent为None），将代码的一部分指定为父级的子列表中的索引。在

Answer 2

我建议，假设你可以相信名字之间没有重复，比如：

class Node(object):
    byname = {}

    def __init__(self, name, parent=None):
        self.name = name
        self.parent = parent
        self.children = []
        self.byname[name] = self
        if parent is None:  # root pseudo-node
            self.code = 0
        else:  # all normal nodes
            self.parent.children.append(self)
            self.code = len(self.parent.children)

    def get_codes(self, codelist):
        if self.code:
            codelist.append(str(self.code))
            self.parent.get_codes(codelist)

root = Node('')

def get_code(nodename):
    node = Node.byname.get(nodename)
    if node is None: return ''
    codes = []
    node.get_codes(codes)
    codes.reverse()
    return '.'.join(codes)

您是否还想查看Python代码，以了解如何在给定名称的层次序列（例如['Africa', 'North Africa', 'Morocco']）的情况下添加节点？我希望在上面的结构下它会很清楚，所以你可能想自己做一个练习，但是当然要问你是否愿意看到一个解决方案；-）。在

从文本行（字符串）中获取名称的层次序列取决于分隔符是什么——在您的示例中，它看起来像是纯粹为了美观而添加的一堆空格，与列的排列有关（如果是这样的话，我建议使用一个简单的基于re的方法来拆分两个+空格的序列），但是如果它实际上是（例如）制表符作为分隔符，那么Python标准库中的csv模块将更好地为您服务。我只是不能从你在Q中发布的一个简短的例子来判断！-)在

编辑：OP说他们可以很好地获得名称序列，但希望看到从这些节点添加相关节点的代码——所以，开始吧！-)在

^{pr2}$

了解为什么节点名是唯一的，这对于使上面的类工作很重要吗？由于Node.byname是每个类的一个dict，它只能为每个给定的名称记录一个“对应的节点”——因此，在层次结构中的两个或多个位置重复的名称将“冲突”，并且只有两个或多个节点中的一个将被正确记录。在

但话说回来，这个函数get_code是整个设备无法正常工作的主要原因，如果一个名称可能是模棱两可的，因为操作的规范要求它只返回一个字符串。所以，一些地理列表

America   United States    Georgia
Europe    Eastern Europe   Georgia

（当两个完全不相关的区域同时被命名为'Georgia'——正如上面的例子所示，这种不幸的事情经常发生在现实世界中！-)会破坏整个方案（取决于get_code的规范如何碰巧被修改以处理一个模棱两可的名称参数，当然，类结构肯定会相应地改变，以适应新的、完全不同的规范！）。在

将这些设计决策封装在一个类中的好处是（尽管在这个例子中有几个附带的函数——它们可以优雅地被制作成类方法，当然，但是OP的规范严格要求get_code是一个函数，所以我决定，在这种情况下，addnodes也可以是一个函数！-)具体的设计决策大部分是隐藏在代码的其余部分中的，因此可以很容易地修改（当然，只要规范永远不变——这就是为什么花时间和精力定义自己的API规范如此重要，这比设计和编码的任何其他部分都重要得多！-)重构内部行为（例如为了优化、易于调试/测试等等），同时保持API指定的语义不变，从而使应用程序的所有其他部分保持原始状态（实际上，甚至不需要重新测试，当然，只要实现API的部分都经过了非常彻底的单元测试——不难做到，因为它们很好地隔离和独立！-). 在

Answer 3

我不确定，如果我做对了。如果我们把每个对象都保存在一个全局dict中，那么它就失去了使用树的目的，而树只用于构造编号方案。 但是基于树的表示法看起来像这样：

class Location(object):

    allLocation = {}

    def __init__(self, name):
        self.name = name
        self.parent = None
        self.number = "0"
        self.children = {}

    def putChild(self, childLocation):
        if childLocation.name not in self.allLocation.keys():
            # Now adjust the number scheme
            #if self.number is "0":
            # this is root
            numScheme = str(len(self.children) + 1)

            childLocation.setNumber(numScheme)

            # Add the child
            self.children[childLocation.number] = childLocation
            self.allLocation[childLocation.name] = childLocation
            childLocation.parent = self
            return 0
        else:
            return 1 # Location already a child of the current clocation

    def setNumber(self, num):
        if self.number is not "0":
            # raise an exception, number already adjusted
            pass
        else:
            # set the number 
            self.number = num


    def locateChild(self, numScheme):
        # Logic should be to break up the numScheme and pass the token successively 
        numSchemeList = []

        if type(numScheme) is str:
            numSchemeList = numScheme.split(".")
        else:
            numSchemeList = numScheme


        if len(numSchemeList) >= 1:
            k = numSchemeList.pop()
            # if the child is available 

            if k in self.children.keys():
                childReferenced = self.children[k]


                # Is child of child required
                if len(numSchemeList) >= 1:
                    return childReferenced.locateChild(numSchemeList)
                else:
                    return childReferenced
            else:
                # No such child
                return None
        else:
            # The list is empty , search ends here
            return None

    def getScheme(self, name):
        if name in self.allLocation.keys():
            locObj = self.allLocation[name]
            return locObj.getNumScheme(name, "")
        else:
            return None

    def getNumScheme(self, name, numScheme="0",):
        if not self.parent:
            return numScheme
        if numScheme != "":
            return self.parent.getNumScheme(name, self.number + "." + numScheme)
        else:
            return self.parent.getNumScheme(name, self.number )



root = Location("root")
africa = Location("Africa")
asia = Location("Asia")
america = Location("America")
root.putChild(africa)
root.putChild(asia)
root.putChild(america)

nafrica = Location("North Africa")
africa.putChild(nafrica)

nafrica.putChild(Location("Morrocco"))

obj = root.locateChild("1.1.1")
print obj.name

print root.getScheme("Morrocco")