Python二叉树算法实现

Python #二叉树 #算法2012-11-25 22:34
很简单的二叉树，代码如下：
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import os
class Node(object):
    """docstring for Node"""
    def __init__(self, v = None, left = None, right=None, parent=None):
        self.value = v
        self.left = left
        self.right = right
        self.parent = parent
class BTree(object):
    """docstring for BtTee """
    def __init__(self):
        self.root = None
        self.size = 0
    def insert(self, node):
        n = self.root
        if n == None:
            self.root = node
            return
        while True:
            if node.value <= n.value:
                if n.left == None:
                    node.parent = n
                    n.left = node
                    break
                else:
                    n = n.left
            if node.value > n.value:
                if n.right == None:
                    n.parent = n
                    n.right = node
                    break
                else:
                    n = n.right
    def find(self, v):
        n = self.root # http://yige.org
        while True:
            if n == None:
                return None
            if v == n.value:
                return n
            if v < n.value:
                n = n.left
                continue
            if v > n.value:
                n = n.right
    def find_successor(node):
        '''查找后继结点'''
        assert node != None and node.right != None
        n = node.right
        while n.left != None:
            n = n.left
        return n

    def delete(self, v):
        n = self.find(v)
        print "delete:",n.value
        del_parent = n.parent
        if del_parent == None:
            self.root = None;
            return
        if n != None:
            if n.left != None and n.right != None:
                succ_node = find_successor(n)
                parent = succ_node.parent
                if succ_node == parent.left:
                    #if succ_node is left sub tree
                    parent.left = None
                if succ_node == parent.right:
                    #if succ_node is right sub tree
                    parent.right = None
                if del_parent.left == n:
                    del_parent.left = succ_node
                if del_parent.right == n:
                    del_parent.right = succ_node
                succ_node.parent = n.parent
                succ_node.left = n.left
                succ_node.right = n.right

                del n
            elif n.left != None or n.right != None:
                if n.left != None:
                    node = n.left
                else:
                    node = n.right
                node.parent = n.parent
                if del_parent.left == n:
                    del_parent.left = node
                if del_parent.right == n:
                    del_parent.right = node
                del n
            else:
                if del_parent.left == n:
                    del_parent.left = None
                if del_parent.right == n:
                    del_parent.right = None
                
                
    def tranverse(self):
        def pnode(node):
            if node == None:
                return
            if node.left != None:
                pnode(node.left)
            print node.value
            if node.right != None:
                pnode(node.right)
        pnode(self.root)

def getopts():
	import optparse, locale
	parser = optparse.OptionParser()
	parser.add_option("-i", "--input", dest="input", help=u"help name", metavar="INPUT")
	(options, args) = parser.parse_args()
	#print options.input
	return (options.input)

if __name__ == '__main__':
	
    al = [23, 45, 67, 12, 78,90, 11, 33, 55, 66, 89, 88 ,5,6,7,8,9,0,1,2,678]
    bt = BTree()
    for x in al :
        bt.insert(Node(x))
    bt.delete(12)
    bt.tranverse()
    n = bt.find(12)
    if n != None:
        print "find valud:",n.value
Python 基础

Python 高级

Python二叉树算法实现

相关文章
