Python中的二叉树中序遍历

Question

我认为我没有正确遍历它，当它需要 return 一个新列表时它 returning 是空的。我被困了一段时间，仍然需要做所有其他的遍历。将为所需的输出提供单元测试，但我的单元测试可能是错误的。

def inorder(self):

    print("in INOrDER is entered")
    temp = [None]


    if self.__left:
        temp = temp.append(self.__left)
        return self.__left.inorder() 
    elif self.__right: 
        temp = temp.append(self.__right)
        return self.__right.inorder() 
    return temp


def test_inorder(self):
    bt = family_tree()
    bt.add(20, "melanie")
    bt.add(10, "edwin")
    bt.add(30, "junior")
    bt.add(25, "dora")
    bt.add(35, "kate")
    x = bt.inorder()

    expected = '''(10, 'edwin'),(20, 'melanie'),(25, 'dora'),(30, 'junior'),(35, 'kate')'''
    self.assertEquals(str(x), expected)
    t = family_tree(bt)
    self.assertEquals(str(t), expected)

Answer 1

中序遍历需要下降到两个子树（如果存在），并访问中间的根；你的代码 returns 在遍历一个子树后，跳过另一个子树和根。

Answer 2

你的实现有两个问题：

temp = [None]

以上语句创建了一个包含 None 项的列表：

x = len(temp) # x value will be 1

第二个问题是你的方法附加逻辑；您 return 值而不是追加它们。

这是基于您的代码的实现：

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

    result.append(self.__value)

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

    return result

Python中的二叉树中序遍历

Binary tree inorder traversal in Python

python

binary-tree

inorder

data-structures