¿Cómo puedo implementar un árbol en Python?

Respuestas:

233

anytree

Recomiendo https://pypi.python.org/pypi/anytree (soy el autor)

Ejemplo

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

Caracteristicas

anytree también tiene una potente API con:

  • creación de árbol simple
  • modificación simple del árbol
  • reservar árbol de iteración
  • iteración de árbol de orden posterior
  • resolver rutas de nodo relativas y absolutas
  • caminando de un nodo a otro.
  • representación de árbol (ver ejemplo arriba)
  • conexiones de conexión / desconexión de nodos
c0fec0de
fuente
31
Simplemente la mejor respuesta, otros están reinventando la rueda.
Ondrej
66
Es una buena forma de revelar que usted es el autor del paquete que está recomendando en su respuesta.
John Y
3
@ c0fec0de te amo !!!! Esta biblioteca es increíble, incluso tiene una funcionalidad de visualización
layer
2
@Ondrej bueno, las otras respuestas son menos dependientes y la pregunta original sí preguntó sobre las estructuras de datos integradas. Si bien anytreees probablemente una gran biblioteca, esta es una pregunta de Python, no una pregunta de Node.js.
Rob Rose
Encontré esta respuesta a través de Google. Esta biblioteca es realmente bonita. ¡Me encanta especialmente la capacidad de usar la clase mixin para hacer un árbol de cualquier objeto!
Rÿck Nöthing
104

Python no tiene la amplia gama de estructuras de datos "incorporadas" que tiene Java. Sin embargo, debido a que Python es dinámico, un árbol general es fácil de crear. Por ejemplo, un árbol binario podría ser:

class Tree:
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

Puedes usarlo así:

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"
Greg Hewgill
fuente
109
Esto realmente no explica mucho acerca de hacer una implementación de árbol útil.
Mike Graham
14
La pregunta está etiquetada con Python3, entonces no hay necesidad de derivar class Treedel objeto
cfi
3
@cfi Derivar a objectveces es solo una pauta: si una clase hereda de ninguna otra clase base, herede explícitamente del objeto. Esto también se aplica a las clases anidadas. Consulte la Guía de estilo de Google Python
Konrad Reiche
16
@platzhirsch: Lea y cite la directriz por completo: Google señala explícitamente que esto es necesario para que el código de Python 2 funcione como se esperaba y se recomienda para mejorar la compatibilidad con Py3. Aquí estamos hablando del código Py3. No hay necesidad de escribir más, legacy.
cfi
13
Es un árbol binario, no uno general como se solicitó.
Michael Dorner
49

Un árbol genérico es un nodo con cero o más hijos, cada uno de ellos un nodo (árbol) adecuado. No es lo mismo que un árbol binario, son estructuras de datos diferentes, aunque ambas comparten alguna terminología.

No hay ninguna estructura de datos integrada para árboles genéricos en Python, pero se implementa fácilmente con clases.

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')])])
Rudá Moura
fuente
¡Increíble, esto también se puede usar fácilmente como un gráfico! El único problema que vi es: ¿Cómo puedo diferenciar el nodo izquierdo del nodo derecho?
Ângelo Polotto
3
Por índice de niños. A la izquierda siempre habrá hijos [0] en ese caso.
Freund Allein
38

Puedes probar:

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

Como se sugiere aquí: https://gist.github.com/2012250

Ib33X
fuente
si desea ampliar a una cantidad arbitraria de niveles, compruebe: stackoverflow.com/a/43237270/511809
natbusa el
esto sombrea la función integrada hash.
Tritium21
20
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.traversePostorder(root.left)
            self.traversePostorder(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()
shivam garg
fuente
3
¿Puede agregar algunas notas para presentar su código y su implementación?
Michele d'Amico
Gracias por la implementación completa del árbol binario con funciones de utilidad. Como es Python 2, creé una esencia para la implementación de Binary Tree (Py3) para las personas que necesitan una versión de Python 3.
CᴴᴀZ
16

No hay árboles incorporados, pero puede construir uno fácilmente subclasificando un tipo de Nodo de la Lista y escribiendo los métodos de recorrido. Si haces esto, he encontrado que bisect es útil.

También hay muchas implementaciones en PyPi que puede explorar.

Si recuerdo correctamente, la lib estándar de Python no incluye estructuras de datos de árbol por la misma razón que la biblioteca de clases base .NET no: la localidad de memoria se reduce, lo que resulta en más errores de caché. En los procesadores modernos, generalmente es más rápido llevar una gran cantidad de memoria al caché, y las estructuras de datos "ricas en punteros" niegan el beneficio.

Justin R.
fuente
2
FYI: Las redes están cubiertas de odio contra Boost. Aparentemente se supone que es un GRAN dolor tratar, especialmente desde que se suspendió el soporte para ello. Así que recomendaría mantenerse alejado de eso
inspectorG4dget
Gracias. No he tenido ningún problema personalmente, pero no quiero engañar, así que he eliminado esa referencia.
Justin R.
11

Implementé un árbol rooteado como diccionario {child:parent}. Entonces, por ejemplo, con el nodo raíz 0, un árbol podría verse así:

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

Esta estructura hizo que fuera bastante fácil ir hacia arriba a lo largo de una ruta desde cualquier nodo a la raíz, lo cual era relevante para el problema en el que estaba trabajando.

pata
fuente
1
Esta es la forma en que estaba considerando hacerlo, hasta que vi la respuesta. Aunque desde un árbol es un padre con dos hijos, y si quieres bajar, puedes hacerlo {parent:[leftchild,rightchild]}.
JFA
1
Otra forma es usar listas de listas donde el primer (o más) elemento de la lista es el valor del nodo, y las siguientes dos listas anidadas representan sus subárboles izquierdo y derecho (o más para el árbol n-ario).
pepr
9

La respuesta de Greg Hewgill es excelente, pero si necesita más nodos por nivel, puede usar una lista | diccionario para crearlos: y luego usar el método para acceder a ellos por nombre u orden (como 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

Ahora solo cree una raíz y compílela: ej:

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

Eso debería ser suficiente para que comiences a descubrir cómo hacer que esto funcione

Bruno
fuente
Hay algo que falta en esta respuesta, estuve probando esta solución durante los últimos 2 días y creo que tiene un flujo lógico en el método de adición de objetos. Enviaré mi respuesta a esta pregunta, échale un vistazo y avísame si puedo ayudarte.
MAULIK MODI
8
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

funciona como un diccionario, pero proporciona tantos dictados anidados que desee. Intenta lo siguiente:

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']            = '*'

entregará un dictado anidado ... que realmente funciona como un árbol.

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

... Si ya tienes un dict, lanzará cada nivel a un árbol:

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

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

De esta manera, puede seguir editando / agregando / eliminando cada nivel de dictado como lo desee. Todos los métodos dict para transversal, etc., todavía se aplican.

natbusa
fuente
2
¿Hay alguna razón por la que elegiste extender en dictlugar de defaultdict? Según mis pruebas, extender en defaultdictlugar de dict y luego agregar self.default_factory = type(self)a la parte superior de init debería funcionar de la misma manera.
Rob Rose
Probablemente me falta algo aquí, ¿cómo navegas por esta estructura? parece muy difícil pasar de niños a padres, por ejemplo, o hermanos
Stormsson
6

He implementado árboles usando dictados anidados. Es bastante fácil de hacer y me ha funcionado con conjuntos de datos bastante grandes. He publicado una muestra a continuación, y puedes ver más en el código de 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:
    [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)
gaefan
fuente
5

He publicado una implementación de árbol Python [3] en mi sitio: http://www.quesucede.com/page/show/id/python_3_tree_implementation .

Espero que sea de utilidad,

Ok, aquí está el código:

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)
Brett Kromkamp
fuente
4

Si alguien necesita una forma más simple de hacerlo, un árbol es solo una lista anidada recursivamente (ya que el conjunto no es hashable):

[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]]

Donde cada rama es un par: [ object, [children] ]
y cada hoja es un par:[ object, [] ]

Pero si necesita una clase con métodos, puede usar anytree.

Hugo Trentesaux
fuente
1

¿Qué operaciones necesitas? A menudo hay una buena solución en Python usando un dict o una lista con el módulo bisect.

Hay muchas, muchas implementaciones de árbol en PyPI , y muchos tipos de árbol son casi triviales para implementarse en Python puro. Sin embargo, esto rara vez es necesario.

Mike Graham
fuente
0

Otra implementación de árbol basada libremente en la respuesta de Bruno :

class Node:
    def __init__(self):
        self.name: str = ''
        self.children: List[Node] = []
        self.parent: Node = self

    def __getitem__(self, i: int) -> 'Node':
        return self.children[i]

    def add_child(self):
        child = Node()
        self.children.append(child)
        child.parent = self
        return child

    def __str__(self) -> str:
        def _get_character(x, left, right) -> str:
            if x < left:
                return '/'
            elif x >= right:
                return '\\'
            else:
                return '|'

        if len(self.children):
            children_lines: Sequence[List[str]] = list(map(lambda child: str(child).split('\n'), self.children))
            widths: Sequence[int] = list(map(lambda child_lines: len(child_lines[0]), children_lines))
            max_height: int = max(map(len, children_lines))
            total_width: int = sum(widths) + len(widths) - 1
            left: int = (total_width - len(self.name) + 1) // 2
            right: int = left + len(self.name)

            return '\n'.join((
                self.name.center(total_width),
                ' '.join(map(lambda width, position: _get_character(position - width // 2, left, right).center(width),
                             widths, accumulate(widths, add))),
                *map(
                    lambda row: ' '.join(map(
                        lambda child_lines: child_lines[row] if row < len(child_lines) else ' ' * len(child_lines[0]),
                        children_lines)),
                    range(max_height))))
        else:
            return self.name

Y un ejemplo de cómo usarlo:

tree = Node()
tree.name = 'Root node'
tree.add_child()
tree[0].name = 'Child node 0'
tree.add_child()
tree[1].name = 'Child node 1'
tree.add_child()
tree[2].name = 'Child node 2'
tree[1].add_child()
tree[1][0].name = 'Grandchild 1.0'
tree[2].add_child()
tree[2][0].name = 'Grandchild 2.0'
tree[2].add_child()
tree[2][1].name = 'Grandchild 2.1'
print(tree)

Cuál debería dar salida:

                        Nodo raíz                        
     / / \              
Nodo secundario 0 Nodo secundario 1 Nodo secundario 2        
                   El | / \       
             Nieto 1.0 Nieto 2.0 Nieto 2.1
Solomon Ucko
fuente
0

Sugiero la biblioteca de networkx .

NetworkX es un paquete de Python para la creación, manipulación y estudio de la estructura, dinámica y funciones de redes complejas.

Un ejemplo de construcción de un árbol:

import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('B', 'D')
G.add_edge('A', 'E')
G.add_edge('E', 'F')

No estoy seguro de lo que quiere decir con un " árbol general ",
pero la biblioteca permite que cada nodo sea un objeto hashaable , y no hay restricción en el número de hijos que tiene cada nodo.

La biblioteca también proporciona algoritmos gráficos relacionados con árboles y capacidades de visualización .

Gal Avineri
fuente
-2

Si desea crear una estructura de datos de árbol, primero debe crear el objeto treeElement. Si crea el objeto treeElement, puede decidir cómo se comporta su árbol.

Para hacer esto a continuación es la clase 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

Ahora, tenemos que usar este elemento para crear el árbol, estoy usando el árbol A * en este ejemplo.

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)

Puede agregar / eliminar cualquier elemento del objeto, pero intente la estructura.

MAULIK MODI
fuente
-4
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)
Gagan Nirmal
fuente
Esto no parece responder a la pregunta de ninguna manera legible.
AlBlue