Traversing a binary tree in Python

I am almost finished with a project that has us creating a dictionary class that utilizes a binary tree structure. I am however stuck on how to implement a method that prints out all the elements in the tree, I just don't have much experience with binary trees so its rather confusing on how to code it.

The method I am trying to figure out is a keys method, that will traverse the entire tree and return a list o开发者_StackOverflow中文版f all the keys. Someone I know has hinted that I should create a private helper function that recursively traverses the tree and keeps track of all the keys. I would like to create what is he is talking about but I have no earthly idea how to code it. Can anyone help me code this out? Figuring this out would pretty much finish it all up for me.

Here is my code so far. [Key:Value] pairs are tuples. I have coded it and also had some help from textbook examples to construct all you see here:

class DictWithTree:

    def __init__(self):
        self._element = None
        self._left = None
        self._right = None
        self._size = 0

    def isempty(self):
        if self._element == None:
            return True
        return False

    def __len__(self):
        return self._size

    def __contains__(self,key):
        path = self._tracePath(key)
        return path[-1]._size > 0

    def _tracePath(self,key): # taken from the textbook example and modified
        if len(self) == 0 or key == self._element[0]:
            return [self]   
        elif len(key) < len(self._element[0]):
            return [self] + self._left._tracePath(key)
        else:
            return [self] + self._right._tracePath(key)

    def __getitem__(self,key):
        if len(self) == 0:
            raise KeyError(key)   
        elif key == self._element[0]:
            return self._element[1]
        elif key < self._element[0]:
            return self._left[key]
        elif key > self._element[0]:
            return self._right[key]
        else:
            raise KeyError(key)

    def __setitem__(self,key,value):
        path = self._tracePath(key)
        endOfPath = path[-1]
        if endOfPath._element != None:       
            if endOfPath._element[0] == key: 
                endOfPath._element = key,value
        if endOfPath._size == 0: # a new element
            for location in path:
                location._size += 1
            endOfPath._element = key,value
            endOfPath._left = DictWithTree()
            endOfPath._right = DictWithTree()

    def clear(self):
        self._element = None
        self._left = None
        self._right = None
        self._size = 0

    def pop(self,key):
        value = self[key]
        self._remove(key)
        return value

    def popitem(self):     # returns the 'last' item in the dictionary,
        if self.isempty(): # (i.e. the largest key in the dictionary)
            return KeyError("There are no keys in the dictionary")
        elif self._right._element == None:
            return self._element
        else:   
            return self._right.popitem()                                   

    def _remove(self,key):
        path = self._tracePath(key)
        endOfPath = path[-1]
        if endOfPath._size > 0:
            for location in path:
                location._size -= 1
            if len(endOfPath._left) == 0:
                endOfPath._promoteChild(endOfPath._right)
            elif len(endOfPath._right) == 0:
                endOfPath._promoteChild(endOfPath._left)
            else:
                endOfPath._element = endOfPath._left.pop()

    def _promoteChild(self,child):
        self._element = child._element
        self._left = child._left
        self._right = child._right

---

There is another solution for recursive in-order tree traversal using Python 3's yield from:

def traverse(tree):
    if tree.left is not None:
        yield from traverse(tree.left)

    yield tree.value

    if tree.right is not None:
        yield from traverse(tree.right)

print(list(traverse(tree_root)))

I think it's far more readable and conceptually simple. I hope it will be helpful to somebody.

---

All you need to do is create a helper method visitAllSubnodes(node) which does something to the current node, then recursively calls itself on the left and right subnodes. What visitAllSubnodes(node) does can be anything, in your case it could be something like print(node._element), but you can make your function wonderfully modular, e.g.

def visitAllSubnodes(node, whatToDoAtEachNode):
    whatToDoAtEachNode(node)
    visitAllSubnodes(node._left, whatToDoAtEachNode)
    visitAllSubnodes(node._right, whatToDoAtEachNode)

def printAllElements(node):
    visitAllSubnodes(node, lambda x:print(x))

To actually return something, you need to use the concept of higher order functions and closures. For example, you could make a function which defines a private personal accumulator (a list you add to), and another function to which that private personal accumulator belongs to, then return the function.

So for example, each time traversed the tree, you could invoke this higher order function, let's call it makeFunctionWhichKeepsTrackOfWhatHasBeenPassedIntoIt(), which returns a function that keeps track of what has been passed into it, as well as the accumulator. I'd give more info but that would be the point of the problem set. =)

---

This should do it

def allKeys(d):
    toVisit = []
    toVisit.append(d)
    while (len(toVisit)>0):
        x = toVisit.pop()
        if x._element:
            yield x._element[0]
        if x._left:
            toVisit.append(x._left)
        if x._right:
            toVisit.append(x._right)

For in-order traversal, you need a recursive soln, as given in the wikipedia entry on tree traversal.

---

For tree traversal, usually people do breadth first traversal (BFT) or depth first traversal (DFT).

In BFT you use a queue to memorize where you left off, in DFT you use the stack to memorize where you left off. If you know the nature of queue and stack, it is just a piece of cake to understand the BFT and DFT, otherwise please read Breadth-first search and Depth-first search, by the way, the code to traversal the tree is usually no more than 10 lines which prove how easy they are.