我如何在Python中实现树？ Python中有像Java一样的内置数据结构吗？
我正在尝试构build一棵普通的树。 Python中是否有内置的数据结构来实现树？
Python不像Java那样拥有相当广泛的“内置”数据结构。 但是，因为Python是dynamic的，所以一般的树很容易创build。 例如，二叉树可能是：
class Tree(object): def __init__(self): self.left = None self.right = None self.data = None 你可以像这样使用它：
root = Tree() root.data = "root" root.left = Tree() root.left.data = "left" root.right = Tree() root.right.data = "right"
anytree
我推荐https://pypi.python.org/pypi/anytree
例
from anytree import Node, RenderTree udo = Node("Udo") marc = Node("Marc", parent=udo) lian = Node("Lian", parent=marc) dan = Node("Dan", parent=udo) jet = Node("Jet", parent=dan) jan = Node("Jan", parent=dan) joe = Node("Joe", parent=dan) print(udo) Node('/Udo') print(joe) Node('/Udo/Dan/Joe') for pre, fill, node in RenderTree(udo): print("%s%s" % (pre, node.name)) Udo ├── Marc │ └── Lian └── Dan ├── Jet ├── Jan └── Joe print(dan.children) (Node('/Udo/Dan/Jet'), Node('/Udo/Dan/Jan'), Node('/Udo/Dan/Joe'))
特征
anytree也有一个强大的API：
- 简单的树创build
- 简单的树修改
- 预定树迭代
- 后序树迭代
- 解决相对和绝对的节点path
- 从一个节点走到另一个节点。
- 树渲染（参见上面的例子）
- 节点连接/分离连接
generics树是一个包含零个或多个子元素的节点，每个节点都是一个合适的（树）节点。 它与二叉树不同，它们是不同的数据结构，尽pipe它们都有一些术语。
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')])])
你可以试试：
from collections import defaultdict def tree(): return defaultdict(tree) users = tree() users['harold']['username'] = 'hrldcpr' users['handler']['username'] = 'matthandlersux'
正如这里所build议的： https ： //gist.github.com/2012250
没有内build的树，但是你可以很容易地通过从列表中inheritance一个Nodetypes和编写遍历方法来构造一棵树。 如果你这样做，我发现平分有用。
PyPi上也有许多可以浏览的实现。
如果我没有记错的话，Python标准库不包括树型数据结构，原因与.NET基类库不一样：内存局部性减less，导致更多的caching未命中。 在现代处理器上，将大量内存带入caching通常会更快，“指针丰富”的数据结构会否定这种好处。
class Node: """ Class Node """ def __init__(self, value): self.left = None self.data = value self.right = None class Tree: """ Class tree will provide a tree as well as utility functions. """ def createNode(self, data): """ Utility function to create a node. """ return Node(data) def insert(self, node , data): """ Insert function will insert a node into tree. Duplicate keys are not allowed. """ #if tree is empty , return a root node if node is None: return self.createNode(data) # if data is smaller than parent , insert it into left side if data < node.data: node.left = self.insert(node.left, data) elif data > node.data: node.right = self.insert(node.right, data) return node def search(self, node, data): """ Search function will search a node into tree. """ # if root is None or root is the search data. if node is None or node.data == data: return node if node.data < data: return self.search(node.right, data) else: return self.search(node.left, data) def deleteNode(self,node,data): """ Delete function will delete a node into tree. Not complete , may need some more scenarion that we can handle Now it is handling only leaf. """ # Check if tree is empty. if node is None: return None # searching key into BST. if data < node.data: node.left = self.deleteNode(node.left, data) elif data > node.data: node.right = self.deleteNode(node.right, data) else: # reach to the node that need to delete from BST. if node.left is None and node.right is None: del node if node.left == None: temp = node.right del node return temp elif node.right == None: temp = node.left del node return temp return node def traverseInorder(self, root): """ traverse function will print all the node in the tree. """ if root is not None: self.traverseInorder(root.left) print root.data self.traverseInorder(root.right) def traversePreorder(self, root): """ traverse function will print all the node in the tree. """ if root is not None: print root.data self.traversePreorder(root.left) self.traversePreorder(root.right) def traversePostorder(self, root): """ traverse function will print all the node in the tree. """ if root is not None: self.traversePreorder(root.left) self.traversePreorder(root.right) print root.data def main(): root = None tree = Tree() root = tree.insert(root, 10) print root tree.insert(root, 20) tree.insert(root, 30) tree.insert(root, 40) tree.insert(root, 70) tree.insert(root, 60) tree.insert(root, 80) print "Traverse Inorder" tree.traverseInorder(root) print "Traverse Preorder" tree.traversePreorder(root) print "Traverse Postorder" tree.traversePostorder(root) if __name__ == "__main__": main()
我实现了一个根目录的树作为一个字典{child:parent} 。 因此，例如对于根节点0 ，树可能看起来像这样：
tree={1:0, 2:0, 3:1, 4:2, 5:3}
这个结构使得沿着从任何节点到根的path向上走很容易，这与我正在处理的问题有关。
我已经使用嵌套的字典来实现树。 这是很容易做到的，它已经为我工作了相当大的数据集。 我已经在下面发布了一个示例，您可以在Google代码中看到更多信息
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: [cd] [xcd] [cxd] [xcxxd] 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)
Greg Hewgill的答案很好，但是如果你需要更多的节点，你可以使用一个列表来创build它们：然后使用方法通过名字或顺序来访问它们（比如id）
class node(object): def __init__(self): self.name=None self.node=[] self.otherInfo = None self.prev=None def nex(self,child): "Gets a node by number" return self.node[child] def prev(self): return self.prev def goto(self,data): "Gets the node by name" for child in range(0,len(self.node)): if(self.node[child].name==data): return self.node[child] def add(self): node1=node() self.node.append(node1) node1.prev=self return node1
现在只需要创build一个root并构build它：例如：
tree=node() #create a node tree.name="root" #name it root tree.otherInfo="blue" #or what ever tree=tree.add() #add a node to the root tree.name="node1" #name it root / child1 tree=tree.add() tree.name="grandchild1" root / child1 / grandchild1 tree=tree.prev() tree=tree.add() tree.name="gchild2" root / child1 / \ grandchild1 gchild2 tree=tree.prev() tree=tree.prev() tree=tree.add() tree=tree.name="child2" root / \ child1 child2 / \ grandchild1 gchild2 tree=tree.prev() tree=tree.goto("child1") or tree=tree.nex(0) tree.name="changed" root / \ changed child2 / \ grandchild1 gchild2
这应该足以让你开始研究如何使这项工作
我已经在我的网站上发布了一个Python [3]树实现： http : //www.quesucede.com/page/show/id/python_3_tree_implementation 。
希望它是有用的，
好的，这是代码：
import uuid def sanitize_id(id): return id.strip().replace(" ", "") (_ADD, _DELETE, _INSERT) = range(3) (_ROOT, _DEPTH, _WIDTH) = range(3) class Node: def __init__(self, name, identifier=None, expanded=True): self.__identifier = (str(uuid.uuid1()) if identifier is None else sanitize_id(str(identifier))) self.name = name self.expanded = expanded self.__bpointer = None self.__fpointer = [] @property def identifier(self): return self.__identifier @property def bpointer(self): return self.__bpointer @bpointer.setter def bpointer(self, value): if value is not None: self.__bpointer = sanitize_id(value) @property def fpointer(self): return self.__fpointer def update_fpointer(self, identifier, mode=_ADD): if mode is _ADD: self.__fpointer.append(sanitize_id(identifier)) elif mode is _DELETE: self.__fpointer.remove(sanitize_id(identifier)) elif mode is _INSERT: self.__fpointer = [sanitize_id(identifier)] class Tree: def __init__(self): self.nodes = [] def get_index(self, position): for index, node in enumerate(self.nodes): if node.identifier == position: break return index def create_node(self, name, identifier=None, parent=None): node = Node(name, identifier) self.nodes.append(node) self.__update_fpointer(parent, node.identifier, _ADD) node.bpointer = parent return node def show(self, position, level=_ROOT): queue = self[position].fpointer if level == _ROOT: print("{0} [{1}]".format(self[position].name, self[position].identifier)) else: print("\t"*level, "{0} [{1}]".format(self[position].name, self[position].identifier)) if self[position].expanded: level += 1 for element in queue: self.show(element, level) # recursive call def expand_tree(self, position, mode=_DEPTH): # Python generator. Loosly based on an algorithm from 'Essential LISP' by # John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241 yield position queue = self[position].fpointer while queue: yield queue[0] expansion = self[queue[0]].fpointer if mode is _DEPTH: queue = expansion + queue[1:] # depth-first elif mode is _WIDTH: queue = queue[1:] + expansion # width-first def is_branch(self, position): return self[position].fpointer def __update_fpointer(self, position, identifier, mode): if position is None: return else: self[position].update_fpointer(identifier, mode) def __update_bpointer(self, position, identifier): self[position].bpointer = identifier def __getitem__(self, key): return self.nodes[self.get_index(key)] def __setitem__(self, key, item): self.nodes[self.get_index(key)] = item def __len__(self): return len(self.nodes) def __contains__(self, identifier): return [node.identifier for node in self.nodes if node.identifier is identifier] if __name__ == "__main__": tree = Tree() tree.create_node("Harry", "harry") # root node tree.create_node("Jane", "jane", parent = "harry") tree.create_node("Bill", "bill", parent = "harry") tree.create_node("Joe", "joe", parent = "jane") tree.create_node("Diane", "diane", parent = "jane") tree.create_node("George", "george", parent = "diane") tree.create_node("Mary", "mary", parent = "diane") tree.create_node("Jill", "jill", parent = "george") tree.create_node("Carol", "carol", parent = "jill") tree.create_node("Grace", "grace", parent = "bill") tree.create_node("Mark", "mark", parent = "jane") print("="*80) tree.show("harry") print("="*80) for node in tree.expand_tree("harry", mode=_WIDTH): print(node) print("="*80)
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
这样，你可以保持编辑/添加/删除每个字典级别，如你所愿。 所有的字典方法遍历等，仍然适用。
你需要什么操作？ 在Python中使用字典或带有平分模块的列表通常有一个很好的解决scheme。
PyPI上有许多树实现，许多树types在纯Python中实现都很简单。 但是，这是很less需要的。
def iterative_bfs(graph, start): '''iterative breadth first search from start''' bfs_tree = {start: {"parents":[], "children":[], "level":0}} q = [start] while q: current = q.pop(0) for v in graph[current]: if not v in bfs_tree: bfs_tree[v]={"parents":[current], "children":[], "level": bfs_tree[current]["level"] + 1} bfs_tree[current]["children"].append(v) q.append(v) else: if bfs_tree[v]["level"] > bfs_tree[current]["level"]: bfs_tree[current]["children"].append(v) bfs_tree[v]["parents"].append(current)
