Python3树结构实现

1、Python 3 tree implementationSource:# Python 3 Tree Implementation# Copyright (C) 2011, Brett Alistair Kromkamp - # All rights reserved.# Redistribution and use in source and binary forms, with or without modification,# are permitted provided that the following conditions are me

2、t:# Redistributions of source code must retain the above copyright notice, this list# of conditions and the following disclaimer.# Redistributions in binary form must reproduce the above copyright notice, this# list of conditions and the following disclaimer in the documentation and/or# other materi

3、als provided with the distribution.# Neither the name of the copyright holder nor the names of the contributors# may be used to endorse or promote products derived from this software without# specific prior written permission.# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS AS I

4、S AND# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CON

5、SEQUENTIAL DAMAGES# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN AN

6、Y WAY OUT OF THE USE OF THIS# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.import unittestdef sanitize_id(id): return id.strip().replace( , )#-# Test suiteclass TestUtilities(unittest.TestCase): def setUp(self): self.identifier1 = i denti fier 1 def test_sanitize_id(self): self.assert

7、Equal(sanitize_id(self.identifier1), identifier1) def tearDown(self): pass#-# Module testingif _name_ = _main_: unittest.main()#=import unittestimport uuidfrom utilities import sanitize_id# Module constants(_ADD, _DELETE, _INSERT) = range(3)class Node: Class for basic node functionality. def _init_(

8、self, name, identifier=None, expanded=True): self._identifier = (str(uuid.uuid1() if identifier is None else sanitize_id(str(identifier) = name self.expanded = expanded self._bpointer = None self._fpointer = property def identifier(self): return self._identifier property def bpointer(self)

9、: 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 i

10、s _DELETE: self._fpointer.remove(sanitize_id(identifier) elif mode is _INSERT: self._fpointer = sanitize_id(identifier)#-# Test suiteclass TestNode(unittest.TestCase): def setUp(self): self.node1 = Node(Test One, ide ntifier 1 ) def test_initialization(self): self.assertEqual(, Test O

11、ne) self.assertEqual(self.node1.identifier, identifier1) self.assertEqual(self.node1.expanded, True) def test_set_fpointer(self): self.node1.update_fpointer( identi fier 2) self.assertEqual(self.node1.fpointer, identifier2) def test_set_bpointer(self): self.node1.bpointer = identi fier 1 self.assert

12、Equal(self.node1.bpointer, identifier1) def tearDown(self): pass#-# Module testingif _name_ = _main_: unittest.main()#=import unittestfrom node import Node# Module constants(_ADD, _DELETE, _INSERT) = range(3)(_ROOT, _DEPTH, _WIDTH) = range(3)class Tree: def _init_(self): self.nodes = def get_index(s

13、elf, position): for index, node in enumerate(self.nodes): if node.identifier = position: break return index def create_node(self, name, identifier=None, parent=None): Create a child node for the node indicated by the parent parameter node = Node(name, identifier) self.nodes.append(node) self._update

14、_fpointer(parent, node.identifier, _ADD) node.bpointer = parent return node def move_node(self, source, destination): Move a node indicated by the source parameter to the parent node indicated by the dest parameter pass def remove_node(self, identifier): pass def show(self, position, level=_ROOT): q

15、ueue = selfposition.fpointer if level = _ROOT: print(0 1.format(, selfposition.identifier) else: print(t*level, 0 1.format(, selfposition.identifier) if selfposition.expanded: level += 1 for element in queue: self.show(element, level) # recursive call def expand_tre

16、e(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 = selfposition.fpointer while queue: yield queue0 expansion = selfqueue0.fpointer if mode is _DEPTH: q

17、ueue = expansion + queue1: # depth-first elif mode is _WIDTH: queue = queue1: + expansion # width-first def is_branch(self, position): return selfposition.fpointer def _update_fpointer(self, position, identifier, mode): if position is None: return else: selfposition.update_fpointer(identifier, mode)

18、 def _update_bpointer(self, position, identifier): selfposition.bpointer = identifier def _getitem_(self, key): return self.nodesself.get_index(key) def _setitem_(self, key, item): self.nodesself.get_index(key) = item def _len_(self): return len(self.nodes) def _contains_(self, identifier): return n

19、ode.identifier for node in self.nodes if node.identifier is identifier#-# Test suiteclass TestTree(unittest.TestCase): def setUp(self): pass def test_initialization(self): pass def tearDown(self): pass#-# Module testingif _name_ = _main_: # Example usage 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_no