字典树的检索

　　字典树通过把键分解成字符列表在字典树中检索位置，在对应的节点中获得键对应的值。实现步骤如下：

　　(1)把键分解成字符列表。

　　(2)遍历字符列表，在字典树中找到健对应的节点（在每个节点的下级节点中用二叉树检索)。

　　(3)获得节点的值。

　　程序代码：

　　运行结果：

　　字典树的删除

　　（１）叶节点的删除：如果删除的是叶节点，在该节点被移除后它的父节点变成了叶节点并且值（value）为空，那需要连带移除，直到出现非空值节点或非叶节点。

　　（２）非叶节点的删除：只把它的值（value）置空。

　　程序代码：

　　运行结果：

　　练习１： 合并附录１～３成一个模块，把下面的单词加进字典树并统计出现次数，查询核对“written"的次数，然后每删除一个遍历一下，直到全部删除。

john escott has written many books for readers of all ages and particularly enjoys writing crime and mystery thrillers he was born in the west of england but now lives on the south coast when he is not writing he visits second-hand bookshops watches videos of old hollywood movies and takes long walks along empty beaches he has written kidnap a pretty face and retold  william tell and other stories and white fang

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社

附录１：字典树添加和遍历（文件：字典树.py）

#（１）字典树节点类
class TrieNode:  #多叉树和二茬树的节点
    def __init__(self,char=None):
        self.char = char  #节点字符
        self.value = None  #节点值
        self.pointers = self.createPointers() #下级节点指针集合（二叉树）
        #下级节点集合中用二叉树快速查找
        self.left = None  #左指针
        self.right = None #右指针
    def createPointers(self):  #创建下级节点指针集合，采用方法以便于覆盖
        return SortTree()
    def addChar(self,char):  #在下级记得集合中查找或创建字典树节点
        tnode = self.pointers.add(char)
        return tnode    
    def display(self,lst):  #中序遍历方法
        if self.left!=None:  #如果左指针不为空
            self.left.display(lst)  #递归调用左节点遍历
        lst.append(self)  #节点本身
        if self.right!=None:  #如果右指针不为空
            self.right.display(lst)  #递归调用右节点遍历
#（２）节点中下级指针集合类（二叉搜索树结构）
class SortTree:
    def __init__(self):
        self.root = None
        self.length = 0  #节点数
    def createNode(self, char=None):  #创建节点函数，使用方法以备覆盖
        return TrieNode(char)
    def add(self,char):  #在节点下级指针集合中添加节点
        if self.root!=None:
            node = self.root
            while True:
                if char<node.char:  #如果传入的字符值小于节点本身的字符值
                    if node.left!=None:  #如果左指针不为空，往下循环
                        node = node.left
                    else:  #如果左指针为空，加上新节点
                        node.left = self.createNode(char)
                        node = node.left
                        self.length += 1
                        break
                elif char>node.char:  #如果传入字符大于节点本身字符值
                    if node.right!=None:  #如果右指针不为空，循环往下
                        node = node.right
                    else:  #如果右指针为空，直接加上新字符节点
                        node.right = self.createNode(char)
                        node = node.right
                        self.length += 1
                        break
                else: #如果传入字符与节点本身字符相等，此字符节点已找到
                    break  
        else:  #添加根节点，也就是上级节点的第一个下级节点
            node = self.createNode(char)
            self.root = node
            self.length += 1
        return node   
    def display(self):  #中序遍历
        lst = []
        self.root.display(lst)
        return lst
#（３）字典树类
class TrieTree:
    def __init__(self):
        self.root = self.createTrieNode()  #根节点是无字符的
    def createTrieNode(self, char = None):  #使用方法以备覆盖
        return TrieNode(char)
    def put(self,key,value):  #压入键值对
        slist = list(key)  #把键分解为字符列表
        tnode = self.root  #从根节点开始
        key = ''
        for char in slist:  #把键中字符逐个取出
            key = "%s%s"%(key,char)  #组合路径
            print(key)  #打印路径
            tnode = tnode.addChar(char)  #把字符逐个插入字典树中
        tnode.value = value  #把值保存在最后路径中        
    def display(self):  #遍历
        key = ""  
        self.__display(self.root, key)
    def __display(self, node, key):  #递归遍历
        key  += "" if node.char == None else node.char   #组合关键词
        print("上级键:", key, "值:", node.value)  #打印上级节点
        if node.pointers.length > 0:  #下级指针集合中有记录
            lst = node.pointers.display()  #获取下级集合
            dlen = len(lst)
            print("序号\t键\t值\t下级集合")
            for i in range(dlen):
                nd = lst[i]
                dw =  "有" if nd.pointers.length > 0 else "无"  #是否有下级集合
                print("%d\t%s\t%s\t%s"  % (i,key+nd.char,str(nd.value),dw)) #打印一行
            dnum = input("请输入下级序号：")
            if dnum != None and dnum != "":
                dnum = int(dnum)
                if dnum>-1 and dnum < dlen:
                    self.__display(lst[dnum], key)  

附录２：字典树检索

from 字典树 import *
#（１）字典树节点类
class SearchTrieNode(TrieNode):  
    def createPointers(self):  #覆盖创建集合方法
        return SearchSortTree() #下级节点指针集合（二叉树）
    def getChar(self,char): #根据字符获取节点
        tnode = self.pointers.get(char)  #具体右下级集合实现
        return tnode     
#（２）节点中下级指针集合类（二叉搜索树结构）
class SearchSortTree(SortTree):
    def createNode(self, char=None):  #覆盖创建节点方法
        return SearchTrieNode(char)
    def get(self,char):  #在集合中获取字符的节点
        if self.root!=None:
            node = self.root
            while True:
                if char<node.char:  #如果传入的值比节点值小，左下行
                    if node.left!=None:
                        node = node.left
                    else:
                        node = None
                        break
                elif char>node.char:   #如果传入的值比节点值大，右下行
                    if node.right!=None:
                        node = node.right
                    else:  
                        node = None
                        break
                else:  #如果传入的值和节点值相等，次字符节点被找到
                    break
            else:
                node = None
            return node
#（３）字典树类
class SearchTrieTree(TrieTree):  
    def createTrieNode(self, char = None):  #覆盖创建字典树节点方法
        return SearchTrieNode(char)
    def get(self,key):  #从字典树中根据键获取值
        slist = list(key)  #把键分解为字符列表
        tnode = self.root
        for char in slist:
            tnode = tnode.getChar(char)
            if tnode==None:  #返回为空，说明字典树中无此键
                break
        if tnode!=None:
            return tnode.value
        else:
            return None

附录３：字典树节点删除

from  字典树 import *
#（１）字典树节点类
class TrieNodeRemove(TrieNode):  #多叉树和二叉树的节点  
    def createPointers(self):  #覆盖创建集合方法
        return SortTreeRemove() #下级节点指针集合（二叉树）
    def getRemove(self, char):
        return self.pointers.getRemove(char)     
    def removeNode(self, fatherNode, cflag, node):
        self.pointers.removeNode(fatherNode, cflag, node)
#（２）节点中下级指针集合类（二叉搜索树结构）增加删除功能
class SortTreeRemove(SortTree):   
    def createNode(self, char=None):  #覆盖创建节点方法
        return TrieNodeRemove(char)
    def getRemove(self,char):  #在节点下级指针集合中删除节点
        if self.root!=None:
            node = self.root
            fatherNode = None  #二叉树父节点
            cflag = 0 #类别：0根，1左，2右
            while True:
                if char<node.char:  #如果传入的字符值小于节点本身的字符值
                    if node.left!=None:  #如果左指针不为空，往下循环                    
                        fatherNode = node  #保留父节点
                        cflag = 1
                        node = node.left
                    else:  #如果左指针为空，返回
                        return None,None,None
                elif char>node.char:  #如果传入字符大于节点本身字符值
                    if node.right!=None:  #如果右指针不为空，循环往下
                        fatherNode = node  #保留父节点
                        cflag = 2
                        node = node.right
                    else:  #如果右指针为空，返回
                        return None,None,None
                else:  #如果传入字符与节点本身字符相等，此字符节点已找到
                    break                 
            return fatherNode,  cflag, node
        else:
            return None,None,None
    def removeNode(self, fatherNode, cflag, node):  #移除节点
        if node.pointers.length > 0:  #如果节点下级指针集合不为空，非叶节点
            node.value = None
            return
        if node.left == None and node.right == None:  #二叉树中是叶节点
            self.replace(fatherNode,cflag, None)
        elif node.right == None:  #node.left != None
            temp = node.left
            node.left = None
            self.replace(fatherNode,cflag, temp)
        elif node.left == None: #node.right != None
            temp = node.right
            node.right = None
            self.replace(fatherNode,cflag, temp)
        else: #node.left != None and node.right != None 右树最小值代替
            tempNode = self.__removeMin(node, node.right)  #右树最小值
            self.replaceNode(node,tempNode)
        self.length -= 1
    def replace(self, fatherNode,cflag, node):  #替代连接
        if cflag == 0:
            self.root = node
        elif cflag == 1:
            fatherNode.left = node
        else:
            fatherNode.right = node
    def replaceNode(self, node1, node2):  #替代数据：字符，值，下级指针集
        node1.char = node2.char
        node1.value = node2.value  #节点值
        node1.pointers = node2.pointers #下级节点指针集合（二叉树）
        node2.pointers = None  #清除字典指针集，以备回收
    def __removeMin(self, fatherNode, node):  #删除出右树最小值
        father =  fatherNode
        cflag = 2
        while node.left != None:  #下行找到最小值
            father = node
            cflag = 1
            node = node.left
        self.replace(father,cflag,node.right)
        node.right = None
        return node                          
#（３）字典树类
class TrieTreeRemove(TrieTree):
    def createTrieNode(self, char = None):  #覆盖创建字典树节点方法
        return TrieNodeRemove(char)
    def remove(self,key):  #删除键
        slist = list(key)  #把键分解为字符列表
        fatherNode, cflag, tnode = None, 0, self.root  #从根节点开始
        key = ''
        path = [(fatherNode, cflag, tnode)]  #路径
        for char in slist:  #把键中字符逐个取出
            key = "%s%s"%(key,char)  #组合路径
            print(key)  #打印路径
            fatherNode, cflag, tnode = tnode.getRemove(char)  #获取下级
            if tnode == None:  #关键字不在字典中
                break
            else:
                path.append((fatherNode, cflag, tnode))  #节点加入路径
        if tnode != None and len(path)>1:  #删除
            upNode = path[-2][2]  #上级节点
            upNode.removeNode(fatherNode, cflag, tnode)
            for i in range(-2, -len(path), -1):  #不能到-len(path)-1，否则upNode出界
                (fatherNode, cflag, tnode) = path[i]
                if tnode.value != None or tnode.pointers.length>0:
                    break  #值不空或有分支的节点，删除终止
                upNode = path[i-1][2]  #上级节点
                upNode.removeNode(fatherNode, cflag, tnode)