python - 使用 Python 将记录存储在二叉树中

Question

我想将学生记录存储在二叉树中。我正在用 Python 实现它。

学生记录将具有三个值，

StudentName, RollNo, Grade

例子，

John 4 A
Josh 2 B
Kevin 3 A

我可以实现一个二叉树并在其中插入单个值。但是，要存储学生记录，我需要使用三棵二叉树吗？然后如何映射值？

这是一个简单的 B 树在 python 中的实现，具有单值插入。

#!/usr/bin/python

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

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

    def getRoot(self):
        return self.root

    def add(self, val):
        if(self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if(val < node.v):
            if(node.l != None):
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if(node.r != None):
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.v):
            return node
        elif(val < node.v and node.l != None):
            self._find(val, node.l)
        elif(val > node.v and node.r != None):
            self._find(val, node.r)

    def deleteTree(self):
        # garbage collector will do this for us. 
        self.root = None

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.l)
            print str(node.v) + ' '
            self._printTree(node.r)

#     3
# 0     4
#   2      8
tree = Tree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.printTree()
print (tree.find(3)).v
print tree.find(10)
tree.deleteTree()
tree.printTree()

实现它的推荐方法是什么？

我想查询，

Get the rollNo where studentName='John'

输出:-

4

状态(获取所有记录) :-

输出:-

John 4 A
Josh 2 B
Kevin 3 A

Answer 1

如果查找单个记录所需的唯一键是名称，则可以使用按名称排序的树。但是，每个节点都必须存储 while 记录。您要么引入一个具有所有三个字段但定义了 < 的类型, > , 和 == (用于 Tree._find )仅比较名称，或添加对 Tree 的支持用于使用自定义比较器 函数。

后者更可取，因为它避免了为其他代码中的运算符建立奇怪的含义；如果实现 <，一个函数就足够了, 因为你可以写

if less(val,node.v): # ...
elif less(node.v,val): # ...
else: return node  # equal