bigtree是一个Python树实现，集成了Python列表、字典和pandas DataFrame。它是python式的，易于学习，并可扩展到许多类型的工作流。

bigtree有很多组成部分，即

从列表、字典和熊猫数据框架构建树 遍历树 修改树(移位/复制节点) 搜索树 辅助方法(克隆树，修剪树，获取两个树之间的差异) 导出树(打印到控制台，导出树到字典，熊猫数据框架，图像等) 其他树结构:二叉树! 其他图结构:有向无环图(dag)!

我还能说什么呢……是的，这也是有据可查的。

一些例子:

from bigtree import list_to_tree, tree_to_dict, tree_to_dot

# Create tree from list, print tree
root = list_to_tree(["a/b/d", "a/c"])
print_tree(root)
# a
# ├── b
# │   └── d
# └── c

# Query tree
root.children
# (Node(/a/b, ), Node(/a/c, ))

# Export tree to dictionary / image
tree_to_dict(root)
# {
#     '/a': {'name': 'a'},
#     '/a/b': {'name': 'b'},
#     '/a/b/d': {'name': 'd'},
#     '/a/c': {'name': 'c'}
# }

graph = tree_to_dot(root, node_colour="gold")
graph.write_png("tree.png")

来源/免责声明:我是bigtree的创造者;)

你可以试试:

from collections import defaultdict
def tree(): return defaultdict(tree)
users = tree()
users['harold']['username'] = 'hrldcpr'
users['handler']['username'] = 'matthandlersux'

建议在这里:https://gist.github.com/2012250

class Tree(dict):
    """A tree implementation using python's autovivification feature."""
    def __missing__(self, key):
        value = self[key] = type(self)()
        return value

    #cast a (nested) dict to a (nested) Tree class
    def __init__(self, data={}):
        for k, data in data.items():
            if isinstance(data, dict):
                self[k] = type(self)(data)
            else:
                self[k] = data

作为一个字典，但提供尽可能多的嵌套字典。 试试下面的方法:

your_tree = Tree()

your_tree['a']['1']['x']  = '@'
your_tree['a']['1']['y']  = '#'
your_tree['a']['2']['x']  = '$'
your_tree['a']['3']       = '%'
your_tree['b']            = '*'

将传递一个嵌套的字典…就像树一样。

{'a': {'1': {'x': '@', 'y': '#'}, '2': {'x': '$'}, '3': '%'}, 'b': '*'}

．.． 如果你已经有字典了，它会把每一层都投射到一棵树上:

d = {'foo': {'amy': {'what': 'runs'} } }
tree = Tree(d)

print(d['foo']['amy']['what']) # returns 'runs'
d['foo']['amy']['when'] = 'now' # add new branch

这样，你就可以随心所欲地编辑/添加/删除每个词典级别。 遍历等所有dict方法仍然适用。

泛型树是一个具有零个或多个子节点的节点，每个子节点都是一个合适的(树)节点。它与二叉树不同，它们是不同的数据结构，尽管它们都有一些相同的术语。

Python中没有任何用于泛型树的内置数据结构，但很容易通过类实现。

class Tree(object):
    "Generic tree node."
    def __init__(self, name='root', children=None):
        self.name = name
        self.children = []
        if children is not None:
            for child in children:
                self.add_child(child)
    def __repr__(self):
        return self.name
    def add_child(self, node):
        assert isinstance(node, Tree)
        self.children.append(node)
#    *
#   /|\
#  1 2 +
#     / \
#    3   4
t = Tree('*', [Tree('1'),
               Tree('2'),
               Tree('+', [Tree('3'),
                          Tree('4')])])

如果您想要创建树数据结构，那么首先必须创建treeElement对象。如果您创建了treeElement对象，那么您可以决定树的行为。

下面是TreeElement类:

class TreeElement (object):

def __init__(self):
    self.elementName = None
    self.element = []
    self.previous = None
    self.elementScore = None
    self.elementParent = None
    self.elementPath = []
    self.treeLevel = 0

def goto(self, data):
    for child in range(0, len(self.element)):
        if (self.element[child].elementName == data):
            return self.element[child]

def add(self):

    single_element = TreeElement()
    single_element.elementName = self.elementName
    single_element.previous = self.elementParent
    single_element.elementScore = self.elementScore
    single_element.elementPath = self.elementPath
    single_element.treeLevel = self.treeLevel

    self.element.append(single_element)

    return single_element

现在，我们必须使用这个元素来创建树，在这个例子中我使用的是A*树。

class AStarAgent(Agent):
# Initialization Function: Called one time when the game starts
def registerInitialState(self, state):
    return;

# GetAction Function: Called with every frame
def getAction(self, state):

    # Sorting function for the queue
    def sortByHeuristic(each_element):

        if each_element.elementScore:
            individual_score = each_element.elementScore[0][0] + each_element.treeLevel
        else:
            individual_score = admissibleHeuristic(each_element)

        return individual_score

    # check the game is over or not
    if state.isWin():
        print('Job is done')
        return Directions.STOP
    elif state.isLose():
        print('you lost')
        return Directions.STOP

    # Create empty list for the next states
    astar_queue = []
    astar_leaf_queue = []
    astar_tree_level = 0
    parent_tree_level = 0

    # Create Tree from the give node element
    astar_tree = TreeElement()
    astar_tree.elementName = state
    astar_tree.treeLevel = astar_tree_level
    astar_tree = astar_tree.add()

    # Add first element into the queue
    astar_queue.append(astar_tree)

    # Traverse all the elements of the queue
    while astar_queue:

        # Sort the element from the queue
        if len(astar_queue) > 1:
            astar_queue.sort(key=lambda x: sortByHeuristic(x))

        # Get the first node from the queue
        astar_child_object = astar_queue.pop(0)
        astar_child_state = astar_child_object.elementName

        # get all legal actions for the current node
        current_actions = astar_child_state.getLegalPacmanActions()

        if current_actions:

            # get all the successor state for these actions
            for action in current_actions:

                # Get the successor of the current node
                next_state = astar_child_state.generatePacmanSuccessor(action)

                if next_state:

                    # evaluate the successor states using scoreEvaluation heuristic
                    element_scored = [(admissibleHeuristic(next_state), action)]

                    # Increase the level for the child
                    parent_tree_level = astar_tree.goto(astar_child_state)
                    if parent_tree_level:
                        astar_tree_level = parent_tree_level.treeLevel + 1
                    else:
                        astar_tree_level += 1

                    # create tree for the finding the data
                    astar_tree.elementName = next_state
                    astar_tree.elementParent = astar_child_state
                    astar_tree.elementScore = element_scored
                    astar_tree.elementPath.append(astar_child_state)
                    astar_tree.treeLevel = astar_tree_level
                    astar_object = astar_tree.add()

                    # If the state exists then add that to the queue
                    astar_queue.append(astar_object)

                else:
                    # Update the value leaf into the queue
                    astar_leaf_state = astar_tree.goto(astar_child_state)
                    astar_leaf_queue.append(astar_leaf_state)

你可以从对象中添加/删除任何元素，但要使结构为完整的。

我使用嵌套字典实现了树。这很容易做到，而且对我来说，它在相当大的数据集上很有效。我在下面发布了一个示例，你可以在谷歌代码中看到更多

  def addBallotToTree(self, tree, ballotIndex, ballot=""):
    """Add one ballot to the tree.

    The root of the tree is a dictionary that has as keys the indicies of all 
    continuing and winning candidates.  For each candidate, the value is also
    a dictionary, and the keys of that dictionary include "n" and "bi".
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.

    If candidate c is a winning candidate, then that portion of the tree is
    expanded to indicate the breakdown of the subsequently ranked candidates.
    In this situation, additional keys are added to the tree[c] dictionary
    corresponding to subsequently ranked candidates.
    tree[c]["n"] is the number of ballots that rank candidate c first.
    tree[c]["bi"] is a list of ballot indices where the ballots rank c first.
    tree[c][d]["n"] is the number of ballots that rank c first and d second.
    tree[c][d]["bi"] is a list of the corresponding ballot indices.

    Where the second ranked candidates is also a winner, then the tree is 
    expanded to the next level.  

    Losing candidates are ignored and treated as if they do not appear on the 
    ballots.  For example, tree[c][d]["n"] is the total number of ballots
    where candidate c is the first non-losing candidate, c is a winner, and
    d is the next non-losing candidate.  This will include the following
    ballots, where x represents a losing candidate:
    [c d]
    [x c d]
    [c x d]
    [x c x x d]

    During the count, the tree is dynamically updated as candidates change
    their status.  The parameter "tree" to this method may be the root of the
    tree or may be a sub-tree.
    """

    if ballot == "":
      # Add the complete ballot to the tree
      weight, ballot = self.b.getWeightedBallot(ballotIndex)
    else:
      # When ballot is not "", we are adding a truncated ballot to the tree,
      # because a higher-ranked candidate is a winner.
      weight = self.b.getWeight(ballotIndex)

    # Get the top choice among candidates still in the running
    # Note that we can't use Ballots.getTopChoiceFromWeightedBallot since
    # we are looking for the top choice over a truncated ballot.
    for c in ballot:
      if c in self.continuing | self.winners:
        break # c is the top choice so stop
    else:
      c = None # no candidates left on this ballot

    if c is None:
      # This will happen if the ballot contains only winning and losing
      # candidates.  The ballot index will not need to be transferred
      # again so it can be thrown away.
      return

    # Create space if necessary.
    if not tree.has_key(c):
      tree[c] = {}
      tree[c]["n"] = 0
      tree[c]["bi"] = []

    tree[c]["n"] += weight

    if c in self.winners:
      # Because candidate is a winner, a portion of the ballot goes to
      # the next candidate.  Pass on a truncated ballot so that the same
      # candidate doesn't get counted twice.
      i = ballot.index(c)
      ballot2 = ballot[i+1:]
      self.addBallotToTree(tree[c], ballotIndex, ballot2)
    else:
      # Candidate is in continuing so we stop here.
      tree[c]["bi"].append(ballotIndex)