实现二叉搜索树 [英] Implementing binary search tree

问题描述

我非常抱歉因为天真。我试图实现一个二叉搜索树在python（学习python的一部分）。我试图谷歌它，但我不能指出我在哪里已经失败。我有兴趣知道的不是一个实现，但为什么我的代码不工作。任何帮助都非常感激。

I am extremely sorry for being so naive. I am trying to implement a binary search tree in python (part of learning python in a way). I tried to google it, but I am unable to point out where I have faltered. What I am interested in knowing is not an implementation, but why my code is not working. Any help is really appreciated.

代码如下 -

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()

推荐答案

一个二进制插入：

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def binary_insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                binary_insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                binary_insert(root.r_child, node)

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

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

---

---

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

---

---

     3
    / \
   1   7
      /
     5

---

---

print "in order:"
in_order_print(r)

print "pre order"
pre_order_print(r)

in order:
1
3
5
7
pre order
3
1
7
5

这篇关于实现二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！