Heim > Backend-Entwicklung > Python-Tutorial > Python implementiert einen binären Suchbaum

Python implementiert einen binären Suchbaum

巴扎黑
Freigeben: 2016-12-08 10:32:00
Original
1421 Leute haben es durchsucht

# -*- 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()
Nach dem Login kopieren

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage