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 树遍历的结果出乎意料

我尝试在插入密钥时通过 pdb 进行调试，密钥已正确插入，但在遍历树时，一些节点被跳过，因为它们被标记为 '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 ()

Inorder树走不工作

Inorder tree walk not working

python

algorithm

binary-search-tree

data-structures