- #!/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
- 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
- #该片段来自于http://www.codesnippet.cn/detail/150720134582.html
来源: http://www.codesnippet.cn/detail/150720134582.html