Python: 树结构和数字编码？

Question

我正在使用Python，手头有一些数据，我想把这些数据整理成树形结构，并给它们分配一些代码。这里有一些示例数据：

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

对于这些数据，什么样的树形结构比较合适呢？

另外，有没有办法从这个树形结构中提取出数字代码，这样我就可以查询数据并得到像下面这样的代码呢？

def get_code(place_name):
    # Python magic query to my tree structure
    return code
get_code("Africa") # returns 1
get_code("North Africa") # returns 1.1
get_code("Morocco") # returns 1.1.2

谢谢你的帮助 - 我还有很多关于Python的知识需要学习 :)

Answer 1

我不太确定我理解得对不对。如果我们把每个对象都放在一个全局字典里，那就失去了使用树形结构的意义，因为树形结构只是用来构建编号方案的。

不过，基于树的表示方式大概是这样的：

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")

Answer 2

可以用一个简单的类来表示树形结构，叫做POD（简单数据）。它的样子大概是这样的：

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

接下来，你可以给这个类的data属性赋值或者读取它，或者添加和删除子节点，可能还需要一些辅助方法来帮助你完成这些操作：

def add_child(self, child):
  self.children.append(child)

现在，想要把数据分成不同的树层级，可以用一个简单的算法。这个算法会查看所有有共同层级数据的地方（比如非洲），然后给它们分配一个位置，接着再递归处理下一层的数据。

比如，对于非洲，你会创建一个位置，数据为非洲。然后，它会有一个子节点，分别代表北非、西非等等。

为了“获取代码”，你可以用一个字典，把每个国家和它对应的位置节点关联起来，并利用节点中的父链接。从这个节点开始，向上遍历到顶层（直到父节点为None），在每一层中，把代码的一部分赋值为父节点子节点列表中的索引。

Answer 3

我建议，如果你能确保名字之间没有重复的话，可以考虑使用以下方法：

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 模块会更适合你。我从你在问题中提供的短例子中无法判断这一点！-)

编辑：提问者说他们可以很好地获取名称序列，但想看看如何从这些名称添加相关节点的代码——所以，接下来就是了！-)

def addnodes(names):
    parent = root
    for name in names:
        newnode = Node.byname.get(name)
        if newnode is None:
            newnode = Node(name, parent)
        parent = newnode

你知道为什么节点名称必须唯一吗？这对上面的类工作很重要！因为 Node.byname 是每个类的一个单独的 dict，它只能记录每个给定名称对应的一个“节点”。所以，如果一个名称在层级中重复出现，就会“冲突”，只有其中一个节点会被正确记录。

再说了，提问者提到的 get_code 函数是这个整个结构的主要原因，如果名称可能有歧义，它就无法按预期工作，因为提问者的要求是它只能返回 一个 字符串。所以，像这样的地理列表：

America   United States    Georgia
Europe    Eastern Europe   Georgia

(其中两个完全不相关的地区恰好都叫 'Georgia'——这种情况在现实世界的地理中经常发生，正如上面的例子所示！-) 会破坏整个方案（当然，这取决于 get_code 的要求如何被修改来处理歧义名称的参数，类结构当然可以相应地进行调整，以适应新的、截然不同的要求！）。

把这些设计决策封装在一个类中的好处是（尽管在这个情况下还有几个附带的函数——当然它们也可以优雅地变成类方法，但提问者的要求严格要求 get_code 是一个函数，所以我决定在这种情况下 addnodes 也可以是一个函数！-) 是这些具体的设计决策大部分被隐藏在代码的其他部分，因此可以很容易地进行修改（当然，只要要求不变——这就是为什么花时间和精力定义API要求比设计和编码的其他任何部分都重要！-) 这样可以重构内部行为（例如，为了优化、方便调试/测试等等），同时保持API指定的语义不变，从而让应用程序的其他部分保持原样（实际上只要实现API的部分经过彻底的单元测试，就不需要重新测试——这并不难，因为它们很好地隔离并且是独立的！-）。