Как я могу реализовать дерево в Python? Есть ли встроенные структуры данных в Python, как в Java?

Question

Я пытаюсь построить общее дерево. Есть ли в Python встроенные структуры данных для реализации дерева?

Answer 1

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 с:

• Простое создание дерева
• простая модификация дерева
• итерация дерева предзаказа
• повторение дерева после заказа
• разрешение относительных и абсолютных путей к узлам
• ходьба от одного узла к другому.
• рендеринг дерева (см. Пример выше)
• узел присоединения / отсоединения соединений

Answer 2

Python не обладает таким обширным диапазоном «встроенных» структур данных, как в Java. Однако, поскольку Python динамический, общее дерево легко создать. Например, двоичное дерево может быть:

class Tree:
    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"

Answer 3

Родовое дерево - это узел с нулем или более дочерних узлов, каждый из которых является собственным (древовидным) узлом. Это не то же самое, что бинарное дерево, это разные структуры данных, хотя обе имеют общую терминологию.

В 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')])])

Answer 4

Вы можете попробовать:

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

Как предлагается здесь: https://gist.github.com/2012250

Answer 5

В нем нет встроенных деревьев, но вы можете легко создать его, создав подкласс типа Node из List и написав методы обхода. Если вы сделаете это, я нашел bisect полезным.

Есть также много реализаций PyPi , которые вы можете просмотреть.

Если я правильно помню, стандартная библиотека Python не включает в себя древовидные структуры данных по той же причине, что и библиотека базовых классов .NET: локальность памяти уменьшается, что приводит к большему количеству пропусков кэша. На современных процессорах обычно быстрее просто помещать большой объем памяти в кеш, а структуры данных с «указателем» сводят на нет преимущества.

Answer 6

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

Answer 7

Ответ Грега Хьюджилла великолепен, но если вам нужно больше узлов на уровень, вы можете использовать список | словарь для их создания: а затем использовать метод для доступа к ним по имени или по порядку (например, по идентификатору)

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

Теперь просто создайте рут и создайте его: например:

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

Этого должно быть достаточно, чтобы вы начали понимать, как заставить это работать

Answer 8

Я внедрил корневое дерево как словарь {child:parent}.Так, например, с корневым узлом 0 дерево может выглядеть так:

tree={1:0, 2:0, 3:1, 4:2, 5:3}

Эта структура позволила довольно легко идти вверх по пути от любого узла к корню, что было актуально дляпроблема, над которой я работал.

Answer 9

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 для обхода и т. Д. Все еще применяются.

Answer 10

Я реализовал деревья с помощью вложенных диктов. Это довольно легко сделать, и это сработало для меня с довольно большими наборами данных. Я разместил образец ниже, и вы можете увидеть больше на Google code

  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)