BInary search tree transversals

问题:

I am confused on the recursion in binary search tree transversals, I'm just lost since i need to return a list at the end and don't get how to save the values.It adds values like this shown below and I don't get what data stype is used to save the values like that also I don't think I'm moving through the tree correctly here is my code for , not sure if my unittest is correct either

def inorder(self):

    print("IN INORDER_______________________________")
    print("Printing self.value" + str(self.__value))
    result = []

    if self.__left:
        print("theres self.left")
        print(self.__value)
        #result = result + self.__left 
        #print(result)
        return self.__left.inorder()
        result 
        print(result + "RESULTS")

    if self.__right:

        print("theres self.right")
        print(self.__value)
        return self.__right.inorder()  

    return result



def test_inorder(self):
    bt = family_tree()
    bt.add(15, "jim")
    bt.add(20, "jamie")
    bt.add(25, "fred")
    bt.add(35, "howard")
    bt.add(30, "kc")
    x = bt.inorder()

    expected = '''(15, 'jim'),(20, 'jamie'),(25, 'fred'),(30, 'howard'),(35, 'kc')'''
    self.assertEquals(str(x), expected)
    t = family_tree(bt)
    self.assertEquals(str(t), expected)

回答1:

There is a problem in your inorder implementation ; you return the values instead of connect them together.

Here is my implementation based on your code:

def inorder(self):
    result = []
    if self.__left:
        result += self.__left.inorder()

    result.append(self.__value)

    if self.__right:
        result += self.__right.inorder()

    return result