python实现二叉查找树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python实现二叉查找树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2941字，纯文字阅读大概需要5分钟。

内容图文

# -*- coding: cp936 -*-
#---------------------------------------------
#                                             
# author  chile                                   
# version  1.0                                
# date  2014-02-17                                       
# desc 二叉树                      
#                                             
#                                            
#                                            
#---------------------------------------------
class bintree:
    def __init__(self):
        self.root = None
        
    # 前驱节点
    def treePredecessor(self,entry):
        if entry.left != None:
            return self.maxTree(entry.left)
        preNode = entry.parent
        tempNode = entry
        while preNode != None and preNode.right.value != entry.value:
            tempNode = preNode
            preNode = preNode.parent
        return preNode
        
    
    #后继节点      
    def treeSuccessor(self,entry):
        if entry.right != None:
            return self.minTree(entry.right)
        preNode = entry.parent
        tempNode = entry
        while preNode != None and preNode.left.value != entry.value:
            tempNode = preNode
            preNode = preNode.parent
        return preNode
    
    def add(self,value):
        tempNode = self.root
        parentNode = None
        entry = bintree.entry(value = value)
        while tempNode != None:
            parentNode = tempNode
            if cmp(value,parentNode.value) < 0:
                tempNode = tempNode.left
            else:
                tempNode = tempNode.right
        if parentNode == None:
            self.root = entry
        elif cmp(value,parentNode.value) < 0:
            parentNode.left = entry
            entry.parent = parentNode
        else:
            parentNode.right = entry
            entry.parent = parentNode
    
    #这里删除是全部删除节点（包括所有子节点）
    def remove(self,value):
        root = self.root
        parentNode = None
        if value == root.value:
            root.left = None
            root.right = None
        while root != None:
            parentNode = root.parent
            if value == root.value:
                root.left = None
                root.right = None
                if parentNode.left != None and parentNode.left.value == value:
                    parentNode.left = None
                    break
                else:
                    parentNode.right = None
                    break
            elif cmp(value,root.value) < 0:
                root = root.left
            else:
                root = root.right
    
    #查找节点
    def search(self,value):
        root = self.root
        while root != None and root.value != value:
            if cmp(value,root.value) < 0:
                root = root.left
            else:
                root = root.right
        return root
    
    #最小值的节点，其实就是找左边的叶子节点
    def minTree(self,root):
        entry = root
        while entry.left != None:
            entry = entry.left
        return entry
    
    #最大值的节点
    def maxTree(self,root):
        entry = root
        while entry.right != None:
            entry = entry.right
        return entry
                
    
    #中序遍历
    def iterator(self,root):
        if root != None:
            self.iterator(root.left)
            print root.value
            self.iterator(root.right)
        
    
    class entry:
        def __init__(self, value=None):
            self.left = None
            self.right = None
            self.parent = None
            self.value = value
            
arr = [15,5,3,12,10,13,6,7,16,20,18,23]
tree = bintree()
for val in arr:
    tree.add(val)
 
tree.iterator(tree.root)
node = tree.search(16)
print node.left , node.right , node.parent.value
print tree.maxTree(node).value
print tree.treePredecessor(node).value
print tree.treeSuccessor(node).value
#print tree.maxTree() , tree.minTree()

内容总结

以上是互联网集市为您收集整理的python实现二叉查找树全部内容，希望文章能够帮你解决python实现二叉查找树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端