用二叉排序树实现字典类（Python实现）

class Assoc: #定义一个关联类

def __init__(self, key, value):

self.key = key #键（关键码）

self.value = value #值

def __lt__(self,other):#Python解释器中遇到比较运算符<,会去找类里定义的__lt__方法（less than）

return self.key < other.key

def __le__(self, other): #（less than or equal to)

return self.key < other.key or self.key == other.key

def __str__(self):

return 'Assoc({0},{1})'.format(self.key, self.value)#key和value分别替换前面{0},{1}的位置。

class BinTNode:

def __init__(self, name = none, startyear = none, endyear = none):。 def __init__(self, data=none, next=none):。$$\begin{aligned}m~\left(\frac{x_a + x_b}{2}, \frac{y_a + y_b}{2}\right) \\m~\left(\frac{-1 + 3}{2}, \frac{3 - 4}{2}\right) \\m~\left(\frac{2}{2}, \frac{-1}{2}\right) \\m~\left(1, \frac{-1}{2}\right)\end{aligned}$$。

self.data = dat

self.left = left

self.right = right

class DictBinTNode:

def __init__(self, root = None):

self.root = root

def is_empty(self):

return self.root is None

def search(self, key):#检索是否存在关键码key

bt = self.root

while bt is not None:

entry = bt.data

if key < entry.key:

bt = bt.left

elif key > entry.key:

bt = bt.right

else:

return entry.value

return None

if __name__=='__main__':

# t = BinTNode(5, BinTNode(3,BinTNode(2)), BinTNode(8))

t = BinTNode(Assoc(5,'a'),BinTNode(Assoc(3,'b'),BinTNode(Assoc(2,'d'))),BinTNode(Assoc(8,'c')))

dic = DictBinTNode(t)

print(dic.search(3))

复制代码

2、向二叉排序树字典中插入数据的基本算法：

如果二叉树为空，直接将数据插在根结点上 如果小于根结点的值，则转向左子树，若左子树为空，则将数据插在这里。如果大于根结点的值，则转向右子树，若右子树为空，则将数据插在这里。二叉排序树实现 如果等于结点的值，则将结点的关联值直接替换掉。

def insert(self, key, value):

bt = self.root

if bt is None:

self.root = BinTNode(Assoc(key, value))

return

while True:

entry = bt.data

if key < entry.key: #如果小于当前关键码，转向左子树

if bt.left is None: #如果左子树为空，就直接将数据插在这里

bt.left = BinTNode(Assoc(key,value))

return

bt = bt.left

elif key > entry.key:

if bt.right is None:

bt.right = BinTNode(Assoc(key,value))

return

bt = bt.right

else:

bt.data.value = value

return

if __name__=='__main__':

dic.insert(7,'e')

复制代码

图3-18是合并过程，这里需要注意的是：倒排文件里的倒排列表存放顺序，已经按照索引单词字典顺序由低到高进行了排序，增量索引在遍历词典的时候也按照字典序由低到高排列，这样对老的倒排文件只需进行一遍扫描，并可顺序读取，减少了文件操作中比较耗时的磁盘寻道时间，可以有效地增加合并效率。支持无序字典按字符顺序排序、顺序字典随机乱序以及倒（逆）序重组字典。4）二叉树练习：二叉树练习让我复习了很多数据结构的重要知识，尤其是二叉树的深度（先序、中序、后序）优先遍历和广度优先遍历，同时对二叉树添加、删除节点的逻辑、栈、队列和链表有了更深的了解。

def print_all_values(self):

bt, s = self.root, SStack()

while bt is not None or not s.is_empty(): #最开始时栈为空，但bt不为空；bt =bt.right可能为空，栈不为空；当两者都为空时，说明已经全部遍历完成了

while bt is not None:

s.push(bt)

bt = bt.left

bt = s.pop() #将栈顶元素弹出

yield bt.data.value

bt = bt.right #将当前结点的右子结点赋给bt，让其在while中继续压入栈内

if __name__=='__main__':

for i in dic.print_all_values():

print(i)

复制代码

4、有时希望将字典中的键值对取出，只需修改上面函数中的一个语句即可。将yield bt.data.value换为yieldbt.data.key, bt.data.value。

def entries(self):

bt, s = self.root, SStack()

while bt is not None or not s.is_empty():

while bt is not None:

s.push(bt)

bt = bt.left

bt = s.pop()

yield bt.data.key, bt.data.value

bt = bt.right

复制代码

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-96547-1.html