从二叉搜索树中检索

Question

我正在用python开发一个二叉查找树。但是我的检索方法并不像我希望的那样工作。只有当我想检索根节点时，它才返回正确的值，对于所有其他节点，它都不返回任何值。

下面是我的节点类的代码:

class Treenode:
    def __init__(self, item=None, left=None, right=None):
        self.item = item
        self.pleft = left
        self.pright = right
        self.parent = None

    def __str__(self):
        return str(self.item)

我的二叉树代码：

from Treenode import *
class Bintree:
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self, item):
        self.size += 1
        if self.root == None:
            self.root = Treenode(item)
        else:
            self.insertnode(self.root, item)

    def insertnode(self,node,item):
        if node.pleft == None and node.pright == None:
            if item > node.item:
                newnode = Treenode(item)
                node.pright = newnode
                newnode.parent = node
            else:
                newnode = Treenode(item)
                node.pleft = newnode
                newnode.parent = node
        else:
            if item > node.item:
                if node.pright != None:
                    self.insertnode(node.pright, item)
                else:
                    newnode = Treenode(item)
                    node.pright = newnode
                    newnode.parent = node 
            else:
                if node.pleft != None:
                    self.insertnode(node.pleft, item)
                else:
                    newnode = Treenode(item)
                    node.pleft = newnode
                    newnode.parent = node                  

    def print_inorder(self, root):
        if root == None:
            pass
        else:
            self.print_inorder(root.pleft)
            print(root.item)
            self.print_inorder(root.pright)

    def print_postorder(self, root):
        if root == None:
            pass
        else:
            self.print_postorder(root.pleft)
            self.print_postorder(root.pright)
            print(root.item)

    def print_preorder(self, root):
        if root == None:
            pass
        else:
            print(root.item)
            self.print_preorder(root.pleft)
            self.print_preorder(root.pright)

    def retrieve(self, node, item):
        if node == None:
            return 'Empty Tree'
        else:
            if node.item == item:
                return str(node)
            elif node.item > item:
                self.retrieve(node.pleft, item)
            elif node.item < item:
                self.retrieve(node.pright, item)

所以Bintree中的最后一个方法为除Root之外的所有值返回Not，但它应该返回节点的值。

填充树：

import BinTree
t = BinTree.Bintree()
t.insert(10)
t.insert(8)
t.insert(15)
t.insert(2)
t.insert(0)
t.insert(25)
t.insert(1)
t.insert(10)
t.print_preorder(t.root)
print('-----------------------')
t.print_inorder(t.root)
print('-----------------------')
t.print_postorder(t.root)
print('-----------------------')
temp = t.retrieve(t.root, 10)
print(temp)

Answer 1

您的问题是没有在代码的所有路径中返回值，因此没有看到任何路径。打印不返回值的内容时，将打印“无”。将检索方法更改如下：

def retrieve(self, node, item):
    if node == None:
        return 'Empty Tree'
    else:
        if node.item == item:
            return str(node)
        elif node.item > item:
            return self.retrieve(node.pleft, item)
        elif node.item < item:
            return self.retrieve(node.pright, item)