logo标签列表

如何在Python中实现二叉搜索树？

pythonoopclassdata-structuresbinary-search-tree
53
这是我迄今为止得到的内容，但它没有起作用：
class Node:
    rChild,lChild,data = None,None,None

    def __init__(self,key):
        self.rChild = None
        self.lChild = None
        self.data = key

class Tree:
    root,size = None,0
    def __init__(self):
        self.root = None
        self.size = 0

    def insert(self,node,someNumber):
        if node is None:
            node = Node(someNumber)
        else:
            if node.data > someNumber:
                self.insert(node.rchild,someNumber)
            else:
                self.insert(node.rchild, someNumber)
        return

def main():
    t = Tree()
    t.root = Node(4)
    t.root.rchild = Node(5)
    print t.root.data #this works
    print t.root.rchild.data #this works too
    t = Tree()
    t.insert(t.root,4)
    t.insert(t.root,5)
    print t.root.data #this fails
    print t.root.rchild.data #this fails too

if __name__ == '__main__':
     main()
2
paste the error messages too. - N 1.1
1
@Rohit，“我感兴趣的不是实现，而是为什么我的代码不起作用。”但是你的代码不起作用是因为你的实现不正确。在你的主函数中使用“search”没有太多意义。作为一种友好的建议，也许你可以先编写一个简单的树创建程序，然后对其进行一些前序和后序遍历。谢谢。 - eat
2
@Lennart，@N 1.1 - 对不起。问题出在二叉搜索树的插入上。如果你看一下主函数，前五行按预期工作，但接下来的五行却没有。 @kriegar - 谢谢你提到这个 :) @eat - 我想我找到了我的错误。感谢你指出这一点。 - chochim
@Rohit 我想指出，在插入方法中，if和else的语句是相同的，如果你决定修改而不是重写你的代码，请确保仔细查看它。 - dting
现有的平衡二叉搜索树实现：https://dev59.com/aHNA5IYBdhLWcg3wC5Xh - Ciro Santilli OurBigBook.com
显示剩余2条评论
18个回答
1

这是一个紧凑、面向对象的、递归实现:

    class BTreeNode(object):
        def __init__(self, data):
            self.data = data
            self.rChild = None
            self.lChild = None

    def __str__(self):
        return (self.lChild.__str__() + '<-' if self.lChild != None else '') + self.data.__str__() + ('->' + self.rChild.__str__() if self.rChild != None else '')

    def insert(self, btreeNode):
        if self.data > btreeNode.data: #insert left
            if self.lChild == None:
                self.lChild = btreeNode
            else:
                self.lChild.insert(btreeNode)
        else: #insert right
            if self.rChild == None:
                self.rChild = btreeNode
            else:
                self.rChild.insert(btreeNode)


def main():
    btreeRoot = BTreeNode(5)
    print 'inserted %s:' %5, btreeRoot

    btreeRoot.insert(BTreeNode(7))
    print 'inserted %s:' %7, btreeRoot

    btreeRoot.insert(BTreeNode(3))
    print 'inserted %s:' %3, btreeRoot

    btreeRoot.insert(BTreeNode(1))
    print 'inserted %s:' %1, btreeRoot

    btreeRoot.insert(BTreeNode(2))
    print 'inserted %s:' %2, btreeRoot

    btreeRoot.insert(BTreeNode(4))
    print 'inserted %s:' %4, btreeRoot

    btreeRoot.insert(BTreeNode(6))
    print 'inserted %s:' %6, btreeRoot

上述main()的输出结果是：
inserted 5: 5
inserted 7: 5->7
inserted 3: 3<-5->7
inserted 1: 1<-3<-5->7
inserted 2: 1->2<-3<-5->7
inserted 4: 1->2<-3->4<-5->7
inserted 6: 1->2<-3->4<-5->6<-7
1

一个简单的、递归的方法，只使用一个函数和一个值数组：

class TreeNode(object):

    def __init__(self, value: int, left=None, right=None):
        super().__init__()
        self.value = value
        self.left = left
        self.right = right

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


def create_node(values, lower, upper) -> TreeNode:
    if lower > upper:
        return None

    index = (lower + upper) // 2

    value = values[index]
    node = TreeNode(value=value)
    node.left = create_node(values, lower, index - 1)
    node.right = create_node(values, index + 1, upper)

    return node


def print_bst(node: TreeNode):
    if node:
        # Simple pre-order traversal when printing the tree
        print("node: {}".format(node))
        print_bst(node.left)
        print_bst(node.right)



if __name__ == '__main__':
    vals = [0, 1, 2, 3, 4, 5, 6]
    bst = create_node(vals, lower=0, upper=len(vals) - 1)
    print_bst(bst)

如您所见，我们只需要一个递归方法create_node。在每个create_node方法调用中，我们传入完整的values数组，但是我们会在每次递归调用时更新lower和upper索引值。
然后，使用lower和upper索引值，我们计算出当前节点的index值，并将其捕获在value中。这个value是当前节点的值，我们用它来创建一个节点。
接下来，我们通过递归调用函数来设置left和right的值，直到递归调用的结束状态，即lower大于upper为止。
重要提示：我们在创建树的左侧时更新upper的值。相反，在创建树的右侧时，我们更新lower的值。
希望这能帮助到您！
谢谢您提供的解决方案。只有一个快速的问题：对于实现您的解决方案，初始的 vals 数组是否应该始终排序？ - SereneWizard
1
这是一个可行的解决方案。
class BST:
    def __init__(self,data):
        self.root = data
        self.left = None
        self.right = None

    def insert(self,data):
        if self.root == None:
            self.root = BST(data)
        elif data > self.root:
            if self.right == None:
                self.right = BST(data)
            else:
                self.right.insert(data)
        elif data < self.root:
            if self.left == None:
                self.left = BST(data)
            else:
                self.left.insert(data)

    def inordertraversal(self):
        if self.left != None:
            self.left.inordertraversal()
        print (self.root),
        if self.right != None:
            self.right.inordertraversal()

t = BST(4)
t.insert(1)
t.insert(7)
t.insert(3)
t.insert(6)
t.insert(2)
t.insert(5)
t.inordertraversal()
0
以下代码基于 @DTing 的回答和我从课堂上学到的内容，使用 while 循环来插入（在代码中指示）。
class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val


def binary_insert(root, node):
    y = None
    x = root
    z = node
    #while loop here
    while x is not None:
        y = x
        if z.data < x.data:
            x = x.l_child
        else:
            x = x.r_child
    z.parent = y
    if y == None:
        root = z
    elif z.data < y.data:
        y.l_child = z
    else:
        y.r_child = z


def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print(root.data)
    in_order_print(root.r_child)


r = Node(3)
binary_insert(r, Node(7))
binary_insert(r, Node(1))
binary_insert(r, Node(5))

in_order_print(r)
0

另一个 Python 二叉搜索树解决方案

class Node(object):
    def __init__(self, value):
        self.left_node = None
        self.right_node = None
        self.value = value

    def __str__(self):
        return "[%s, %s, %s]" % (self.left_node, self.value, self.right_node)

    def insertValue(self, new_value):
        """
        1. if current Node doesnt have value then assign to self
        2. new_value lower than current Node's value then go left
        2. new_value greater than current Node's value then go right
        :return:
        """
        if self.value:
            if new_value < self.value:
                # add to left
                if self.left_node is None:  # reached start add value to start
                    self.left_node = Node(new_value)
                else:
                    self.left_node.insertValue(new_value)  # search
            elif new_value > self.value:
                # add to right
                if self.right_node is None:  # reached end add value to end
                    self.right_node = Node(new_value)
                else:
                    self.right_node.insertValue(new_value)  # search
        else:
            self.value = new_value

    def findValue(self, value_to_find):
        """
        1. value_to_find is equal to current Node's value then found
        2. if value_to_find is lower than Node's value then go to left
        3. if value_to_find is greater than Node's value then go to right
        """
        if value_to_find == self.value:
            return "Found"
        elif value_to_find < self.value and self.left_node:
            return self.left_node.findValue(value_to_find)
        elif value_to_find > self.value and self.right_node:
            return self.right_node.findValue(value_to_find)
        return "Not Found"

    def printTree(self):
        """
        Nodes will be in sequence
        1. Print LHS items
        2. Print value of node
        3. Print RHS items
        """
        if self.left_node:
            self.left_node.printTree()
        print(self.value),
        if self.right_node:
            self.right_node.printTree()

    def isEmpty(self):
        return self.left_node == self.right_node == self.value == None


def main():
    root_node = Node(12)
    root_node.insertValue(6)
    root_node.insertValue(3)
    root_node.insertValue(7)

    # should return 3 6 7 12
    root_node.printTree()

    # should return found
    root_node.findValue(7)
    # should return found
    root_node.findValue(3)
    # should return Not found
    root_node.findValue(24)

if __name__ == '__main__':
    main()
0

你的代码存在问题，至少其中一个问题就在这里：

def insert(self,node,someNumber):
    if node is None:
        node = Node(someNumber)
    else:
        if node.data > someNumber:
            self.insert(node.rchild,someNumber)
        else:
            self.insert(node.rchild, someNumber)
    return

你看到语句 "if node.data > someNumber:" 和相关的 "else:" 语句后面都有相同的代码。也就是说，无论 if 语句是 true 还是 false，你都会执行相同的操作。

我建议你可能打算在这里做不同的事情，也许其中一个应该说 self.insert(node.lchild, someNumber)？

0
    def BinaryST(list1,key):
    start = 0
    end = len(list1)
    print("Length of List: ",end)

    for i in range(end):
        for j in range(0, end-i-1):
            if(list1[j] > list1[j+1]):
                temp = list1[j]
                list1[j] = list1[j+1]
                list1[j+1] = temp

    print("Order List: ",list1)

    mid = int((start+end)/2)
    print("Mid Index: ",mid)

    if(key == list1[mid]):
        print(key," is on ",mid," Index")

    elif(key > list1[mid]):
        for rindex in range(mid+1,end):
            if(key == list1[rindex]):
                print(key," is on ",rindex," Index")
                break
            elif(rindex == end-1):
                print("Given key: ",key," is not in List")
                break
            else:
                continue

    elif(key < list1[mid]):
        for lindex in range(0,mid):
            if(key == list1[lindex]):
                print(key," is on ",lindex," Index")
                break
            elif(lindex == mid-1):
                print("Given key: ",key," is not in List")
                break
            else:
                continue


size = int(input("Enter Size of List: "))
list1 = []
for e in range(size):
    ele = int(input("Enter Element in List: "))
    list1.append(ele)

key = int(input("\nEnter Key for Search: "))

print("\nUnorder List: ",list1)
BinaryST(list1,key)
0
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinaryTree:
    def __init__(self, root=None):
        self.root = root

    def add_node(self, node, value):
        """
        Node points to the left of value if node > value; right otherwise,
        BST cannot have duplicate values
        """
        if node is not None:
            if value < node.value:
                if node.left is None:
                    node.left = TreeNode(value)
                else:
                    self.add_node(node.left, value)
            else:
                if node.right is None:
                    node.right = TreeNode(value)
                else:
                    self.add_node(node.right, value)
        else:
            self.root = TreeNode(value)

    def search(self, value):
        """
        Value will be to the left of node if node > value; right otherwise.
        """
        node = self.root
        while node is not None:
            if node.value == value:
                return True     # node.value
            if node.value > value:
                node = node.left
            else:
                node = node.right
        return False

    def traverse_inorder(self, node):
        """
        Traverse the left subtree of a node as much as possible, then traverse
        the right subtree, followed by the parent/root node.
        """
        if node is not None:
            self.traverse_inorder(node.left)
            print(node.value)
            self.traverse_inorder(node.right)


def main():
    binary_tree = BinaryTree()
    binary_tree.add_node(binary_tree.root, 200)
    binary_tree.add_node(binary_tree.root, 300)
    binary_tree.add_node(binary_tree.root, 100)
    binary_tree.add_node(binary_tree.root, 30)
    binary_tree.traverse_inorder(binary_tree.root)
    print(binary_tree.search(200))


if __name__ == '__main__':
    main()
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接