Hoe kan ik een boom in Python implementeren?

Ik probeer een algemene boomstructuur te maken.

Zijn er ingebouwde datastructuren in Python om het te implementeren?

Antwoord 1, autoriteit 100%

Ik raad anytreeaan (ik ben de auteur).

Voorbeeld:

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

anytreeheeft ook een krachtige API met:

• eenvoudige boom maken
• eenvoudige wijziging van de boom
• pre-order boom-iteratie
• herhaling na bestelling
• relatieve en absolute knooppaden oplossen
• lopen van het ene knooppunt naar het andere.
• weergave van de boom (zie voorbeeld hierboven)
• knooppunt bevestigingen/loskoppelen

Antwoord 2, autoriteit 41%

Python heeft niet het hele uitgebreide aanbod van “ingebouwde” datastructuren zoals Java dat wel heeft. Omdat Python echter dynamisch is, is een algemene boom eenvoudig te maken. Een binaire boom kan bijvoorbeeld zijn:

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

Je kunt het als volgt gebruiken:

root = Tree()
root.data = "root"
root.left = Tree()
root.left.data = "left"
root.right = Tree()
root.right.data = "right"

Als u een willekeurig aantal kinderen per knooppunt nodig heeft, gebruik dan een lijst met kinderen:

class Tree:
    def __init__(self, data):
        self.children = []
        self.data = data
left = Tree("left")
middle = Tree("middle")
right = Tree("right")
root = Tree("root")
root.children = [left, middle, right]

Antwoord 3, Autoriteit 20%

Een generieke boom is een knooppunt met nul of meer kinderen, elk een eigen (boom) knooppunt. Het is niet hetzelfde als een binaire boom, het zijn verschillende datastructuren, hoewel beide een terminologie delen.

Er is geen ingebouwde gegevensstructuur voor generieke bomen in Python, maar het is gemakkelijk geïmplementeerd met klassen.

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

Antwoord 4, Autoriteit 14%

U kunt het proberen:

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

Zoals hier gesuggereerd: https://gist.github.com/2012250

Antwoord 5, autoriteit 11%

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

Antwoord 6, Autoriteit 6%

Er zijn geen bomen ingebouwd, maar u kunt er een eenvoudig construeren door een knooppunttype uit de lijst te maken en de traversale methoden te schrijven. Als je dit doet, heb ik bisect nuttig.

Er zijn ook veel implementaties op PYPI die u kunt bladeren.

Als ik me goed herinner, bevat de Python Standard Lib geen boomgegevensstructuren om dezelfde reden dat de .NET-basisklasse-bibliotheek niet: lokaliteit van het geheugen wordt verminderd, wat resulteert in meer cache-missers. Op moderne processors is het meestal sneller om gewoon een groot stuk geheugen in de cache te brengen, en “Pointer Rich” Data Structures negeren het voordeel.

Antwoord 7, Autoriteit 4%

Ik heb een geroote boom geïmplementeerd als een woordenboek {child:parent}. Dus bijvoorbeeld met het wortelknooppunt 0, kan er een boom eruit zien:

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

Deze structuur maakte het vrij gemakkelijk om langs een pad naar boven te gaan van een knooppunt naar de root, die relevant was voor het probleem waar ik aan werkte.

Antwoord 8, Autoriteit 3%

Het antwoord van Greg Hewgill is geweldig, maar als u meer knooppunten per niveau nodig heeft, kunt u een lijst gebruiken | Woordenboek om ze te maken: en gebruik vervolgens de methode om ze te openen op naam of bestelling (zoals 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

Maak nu gewoon een root en bouw deze op:
bijv:

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

Dat zou genoeg moeten zijn om uit te zoeken hoe je dit kunt laten werken

Antwoord 9, autoriteit 3%

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

Werkt als een woordenboek, maar biedt zoveel geneste dictten die u wilt.
Probeer het volgende:

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

levert een geneste dict … die inderdaad als een boom werkt.

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

… als je al een dict hebt, zal het elk niveau naar een boom werpen:

d = {'foo': {'amy': {'what': 'runs'} } }
tree = Tree(d)
print(d['foo']['amy']['what']) # returns 'runs'
d['foo']['amy']['when'] = 'now' # add new branch

Op deze manier kunt u elk dictieniveau bewerken / toevoegen / verwijderen als u wilt.
Alle DICT-methoden voor traversal enz. Toevoegen, nog steeds van toepassing.

Antwoord 10, Autoriteit 2%

Ik heb bomen geïmplementeerd met behulp van geneste dictten. Het is vrij gemakkelijk om te doen, en het heeft voor mij gewerkt met mooie grote datasets. Ik heb een onderstaande monster gepost en je kunt meer zien op 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)

Antwoord 11, autoriteit 2%

Als iemand een eenvoudigere manier nodig heeft om het te doen, is een boom slechts een recursief geneste lijst (aangezien set niet hashbaar is):

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

Waarbij elke tak een paar is: [ object, [children] ]
en elk blad is een paar: [ object, [] ]

Maar als je een klasse met methoden nodig hebt, kun je anytree gebruiken.

Antwoord 12, autoriteit 2%

Ik heb een Python 3-boom implementatie op mijn site gepubliceerd: https://web.archive.org/web/20120723175438/www.quesuede.com/page/show/id/python_3_tree_implementatie

Hier is de code:

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)

Antwoord 13

Als u al de NetworkX bibliotheek, kunt u een boom gebruiken die dat gebruikt. Anders kunt u een van de andere antwoorden proberen.

NetworkX is een Python-pakket voor de creatie, manipulatie en studie
van de structuur, dynamiek en functies van complexe netwerken.

Zoals ‘Tree’ is een andere term voor een (normaal geroote) aangesloten acyclische grafiek, en deze worden ‘Arborescences’ genoemd in NetworkX.

Mogelijk wilt u een vliegtuigboom implementeren (aka bestelde boom) waar elke broer of zus een unieke rang heeft en dit normaal wordt gedaan via de labeling van de knooppunten.

De taal van de grafiekziet er echter anders uit dan de taal van de boom, en de manier om een boom te ‘wortelen’ wordt normaal gesproken gedaan door een gerichte graaf te gebruiken, terwijl er enkele zijn echt coole functies en bijbehorende visualisaties beschikbaar, het zou waarschijnlijk geen ideale keuze zijn als je networkx nog niet gebruikt.

Een voorbeeld van het bouwen van een boom:

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

Met de bibliotheek kan elk knooppunt elk hash-object, en er is geen beperking op het aantal kinderen dat elk knooppunt heeft.

De bibliotheek biedt ook grafiekalgoritmengerelateerd aan bomen en visualisatie-mogelijkheden.

Antwoord 14

Nog een tree-implementatie die losjes is gebaseerd op Bruno’s antwoord:

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

En een voorbeeld van hoe het te gebruiken:

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)

Wat moet worden uitgevoerd:

Hoofdknooppunt
   / / \
Child node 0 Child node 1 Child node 2
          | / \
       Kleinkind 1.0 Kleinkind 2.0 Kleinkind 2.1

Antwoord 15

Hallo, je mag itertreeeens proberen (ik ben de auteur).

Het pakket gaat in de richting van een willekeurig boompakket, maar met een iets andere focus. De prestatie op enorme bomen (>100000 items) is veel beter en het gaat om iterators om een effectief filtermechanisme te hebben.

>>>from itertree import *
>>>root=iTree('root')
>>># add some children:
>>>root.append(iTree('Africa',data={'surface':30200000,'inhabitants':1257000000}))
>>>root.append(iTree('Asia', data={'surface': 44600000, 'inhabitants': 4000000000}))
>>>root.append(iTree('America', data={'surface': 42549000, 'inhabitants': 1009000000}))
>>>root.append(iTree('Australia&Oceania', data={'surface': 8600000, 'inhabitants': 36000000}))
>>>root.append(iTree('Europe', data={'surface': 10523000 , 'inhabitants': 746000000}))
>>># you might use __iadd__ operator for adding too:
>>>root+=iTree('Antarktika', data={'surface': 14000000, 'inhabitants': 1100})
>>># for building next level we select per index:
>>>root[0]+=iTree('Ghana',data={'surface':238537,'inhabitants':30950000})
>>>root[0]+=iTree('Niger', data={'surface': 1267000, 'inhabitants': 23300000})
>>>root[1]+=iTree('China', data={'surface': 9596961, 'inhabitants': 1411780000})
>>>root[1]+=iTree('India', data={'surface': 3287263, 'inhabitants': 1380004000})
>>>root[2]+=iTree('Canada', data={'type': 'country', 'surface': 9984670, 'inhabitants': 38008005})    
>>>root[2]+=iTree('Mexico', data={'surface': 1972550, 'inhabitants': 127600000 })
>>># extend multiple items:
>>>root[3].extend([iTree('Australia', data={'surface': 7688287, 'inhabitants': 25700000 }), iTree('New Zealand', data={'surface': 269652, 'inhabitants': 4900000 })])
>>>root[4]+=iTree('France', data={'surface': 632733, 'inhabitants': 67400000 }))
>>># select parent per TagIdx - remember in itertree you might put items with same tag multiple times:
>>>root[TagIdx('Europe'0)]+=iTree('Finland', data={'surface': 338465, 'inhabitants': 5536146 })

De gemaakte boom kan worden weergegeven:

>>>root.render()
iTree('root')
     └──iTree('Africa', data=iTData({'surface': 30200000, 'inhabitants': 1257000000}))
         └──iTree('Ghana', data=iTData({'surface': 238537, 'inhabitants': 30950000}))
         └──iTree('Niger', data=iTData({'surface': 1267000, 'inhabitants': 23300000}))
     └──iTree('Asia', data=iTData({'surface': 44600000, 'inhabitants': 4000000000}))
         └──iTree('China', data=iTData({'surface': 9596961,  'inhabitants': 1411780000}))
         └──iTree('India', data=iTData({'surface': 3287263, 'inhabitants': 1380004000}))
     └──iTree('America', data=iTData({'surface': 42549000, 'inhabitants': 1009000000}))
         └──iTree('Canada', data=iTData({'surface': 9984670, 'inhabitants': 38008005}))
         └──iTree('Mexico', data=iTData({'surface': 1972550, 'inhabitants': 127600000}))
     └──iTree('Australia&Oceania', data=iTData({'surface': 8600000, 'inhabitants': 36000000}))
         └──iTree('Australia', data=iTData({'surface': 7688287, 'inhabitants': 25700000}))
         └──iTree('New Zealand', data=iTData({'surface': 269652, 'inhabitants': 4900000}))
     └──iTree('Europe', data=iTData({'surface': 10523000, 'inhabitants': 746000000}))
         └──iTree('France', data=iTData({'surface': 632733, 'inhabitants': 67400000}))
         └──iTree('Finland', data=iTData({'surface': 338465, 'inhabitants': 5536146}))
     └──iTree('Antarktika', data=iTData({'surface': 14000000, 'inhabitants': 1100}))

Bijvoorbeeld Filteren kan als volgt:

>>>item_filter = Filter.iTFilterData(data_key='inhabitants', data_value=iTInterval(0, 20000000))
>>>iterator=root.iter_all(item_filter=item_filter)
>>>for i in iterator:
>>>    print(i)
iTree("'New Zealand'", data=iTData({'surface': 269652, 'inhabitants': 4900000}), subtree=[])
iTree("'Finland'", data=iTData({'surface': 338465, 'inhabitants': 5536146}), subtree=[])
iTree("'Antarktika'", data=iTData({'surface': 14000000, 'inhabitants': 1100}), subtree=[])

Antwoord 16

Als u een boomgegevensstructuur wilt maken, moet u eerst het object treeElement maken. Als u het object treeElement maakt, kunt u beslissen hoe uw boom zich gedraagt.

Hiervoor volgt de TreeElement-klasse:

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

Nu moeten we dit element gebruiken om de boom te maken, ik gebruik de A* boom in dit voorbeeld.

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)

U kunt elementen van het object toevoegen / verwijderen, maar de structuur intect maken.