python - Inorder树走不工作

Question

我正在尝试用 python 练习 BST 树实现，以下是我的代码，

import pdb

class Node():
    def __init__(self, parent=None, key=None):
        self.parent = parent if parent != None else None
        self.left = None
        self.right = None
        self.key = key if key != None else None

class BST():
    def __init__(self):
        self.root = Node() 

    def insertKey (self, key):
        #pdb.set_trace()
        # transverse till we find empty position
        if (self.root.key == None):
            self.root.key = key
        else:
            node = self.root
            while (node.left != None and node.right != None):
                if node.key < key:
                    node = node.right
                else:
                    node = node.left
            #we have node either left or right is empty
            if node.key < key:
                node.right = Node (node, key)
            else:
                node.left = Node (node, key)

    def inOrder (self, node):
        #pdb.set_trace()
        if node != None:
            self.inOrder (node.left)
            print node.key
            self.inOrder (node.right)

    def printLeft (self, node):
        if node != None:
            self.printLeft (node)
            print node.key

    def debugAll (self):
        self.inOrder (self.root)
        #self.printLeft (self.root)

    def fromArray (self, numbers):
        srt = sorted(numbers)
        print srt
        length = len(srt)
        mid = length/2
        rootEle = srt[mid]
        self.insertKey (rootEle)
        for i in range (1, mid+1):
            try:
                #pdb.set_trace()
                self.insertKey (srt[mid-i])
                self.insertKey (srt[mid+i])
            except IndexError:
                pass

bst = BST()
bst.fromArray ([1,2,4,3,6,5,10,8,9])
bst.debugAll ()

然而，inOrder 树遍历的结果是出乎意料的

1
4
5
6
10

我尝试在插入 key 时通过 pdb 进行调试， key 已正确插入，但在遍历树时，一些节点被跳过，因为它们被标记为“NoneType”。可能是我在这里错过了一些语言细节。

Answer 1

首先，您下面的代码不正确:

        while (node.left != None and node.right != None):
            if node.key < key:
                node = node.right
            else:
                node = node.left

如果 左侧或右侧节点不存在，它将停止下降。

编辑:如果您像这样修改循环，它就可以工作。可以更好地优化，但这只是一个开始...

class Node():
    def __init__(self, parent=None, key=None):
        self.parent = parent if parent != None else None
        self.left = None
        self.right = None
        self.key = key if key != None else None

class BST():
    def __init__(self):
        self.root = Node()

    def insertKey (self, key):
        #pdb.set_trace()
        # transverse till we find empty position
        if (self.root.key == None):
            self.root.key = key
        else:
            node = self.root
            while 1:
                if node.key < key:
                    if node.right is None:
                        node.right = Node(node, key)
                        break
                    else:
                        node = node.right
                else:
                    if node.left is None:
                        node.left = Node(node, key)
                        break
                    else:
                        node = node.left

    def inOrder (self, node):
        #pdb.set_trace()
        if node != None:
            self.inOrder (node.left)
            print node.key
            self.inOrder (node.right)

    def printLeft (self, node):
        if node != None:
            self.printLeft (node)
            print node.key

    def debugAll (self):
        self.inOrder (self.root)
        #self.printLeft (self.root)

    def fromArray (self, numbers):
        srt = sorted(numbers)
        print srt
        length = len(srt)
        mid = length/2
        rootEle = srt[mid]
        self.insertKey (rootEle)
        for i in range (1, mid+1):
            try:
                #pdb.set_trace()
                self.insertKey (srt[mid-i])
                self.insertKey (srt[mid+i])
            except IndexError:
                pass

bst = BST()
bst.fromArray ([1,2,4,3,6,5,10,8,9])
bst.debugAll ()