python - How can I change recursive traversal of binary tree code to non-recursive traversal? -
class binarytree: def __init__(self, element, parent=none, left=none, right=none): __slots__ = '_element', '_parent', '_left', '_right' self._element = element self._parent = parent self._left = left self._right = right def getparent(self): return self._parent def getleft(self): return self._left def getright(self): return self._right def getsibling(self): if self.isroot(): return none elif self.getparent().getleft() == self: return self.getparent().getright() elif self.getparent().getright() == self: return self.getparent.getleft() else: raise valueerror("strange node") def _setparent(self, container): self._parent = container def _setleft(self, lchild): self._left = lchild def _setright(self, rchild): self._right = rchild def addleft(self, newelement): newtree = binarytree(newelement, self) if self._left == none: self._left = newtree else: newtree._left = self._left self._left._parent = newtree self._left = newtree return newtree def addright(self, newelement): newtree = binarytree(newelement, self) if self._right == none: self._right = newtree else: newtree._right = self._right self._right._parent = newtree self._right = newtree return newtree def getelement(self): return self._element def setelement(self, element): self._element = element def __str__(self): return "[ "+str(self._element)+" "+str(self._left)+" "+str(self._right)+" ]" def inorder(self): if self._left != none: other in self._left.inorder(): yield other yield self if self._right != none: other in self._right.inorder(): yield other def preorder(self): yield self if self._left != none: other in self._left.preorder(): yield other if self._right != none: other in self._right.preorder(): yield other def postorder(self): if self._left != none: other in self._left.postorder(): yield other if self._right != none: other in self._right.postorder(): yield other yield self def levelorder(self): queue = [] queue.append(self) while len(queue) != 0: p = queue.pop(0) if p._left != none: queue.append(p._left) if p._right != none: queue.append(p._right) yield p def children(self): if self._left: yield self._left if self._right: yield self._right def depth(self): if self._parent == none: return 0 else: return 1+self._parent.depth() def isinternal(self): return self._left or self._right def isexternal(self): return not self.isinternal() def isroot(self): return self._parent == none def height(self): if self.isexternal(): return 0 else: return 1 + max(c.height() c in self.children()) def delete(self): if self._parent: if self._parent._left == self: self._parent._left = none elif self._parent._right == self: self._parent._right = none else: raise valueerror("strange node cannot deleted") self._parent = none c in self.children(): c.delete() self._left = self._right = self._element = none del self self = none this code have. have change recursive inorder, preorder, postorder non-recursive. can give me answers or tips it?
Comments
Post a Comment