Home >Backend Development >Python Tutorial >Python implements binary search tree

Python implements binary search tree

巴扎黑
巴扎黑Original
2016-12-08 10:32:001394browse

# -*- 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()

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn