# I have a problem in building class Tree (Binary Search)
# function DelNode(self, Key) is not exactly
# I Need Help, Please building class Tree (Binary Search)
# Is there any different definition of class Tree
from string import split
class Node:
    def __init__(self):
        self.Key = None
        self.pLeft = None
        self.pRight = None
    def __del__(self):
        del self
 
class Tree:
    def __init__(self):
        self.Root = None
    def __del__a(self):
        if self.Root != None:
            del self.Root.pLeft
            del self.Root.pRight
            del self.Root
    def LNR(self):
        if self.Root != None:
            self.Root.pLeft.LNR()
            print self.Root.Key,
            self.Root.pRight.LNR()
    def InsertNode(self, Key):
        if self.Root != None:
            if self.Root.Key == Key:
                return 0
            elif self.Root.Key > Key:
                return self.Root.pLeft.InsertNode(Key)
            else:
                return self.Root.pRight.InsertNode(Key)
        self.Root = Node()
        if self.Root == None:
            return -1
        self.Root.Key = Key
        self.Root.pLeft = Tree()
        self.Root.pRight = Tree()
        return 1
    def SearchStandFor(self, t1, t2):
        if t2.Root.pLeft.Root != None:
            self.SearchStandFor(t1, t2.Root.pLeft)
        else:
            t1.Root.Key = t2.Root.Key
            t1 = t2
            t2 = t2.Root.pRight
    def DelNode(self, Key):
        if self.Root == None:
            return 0
        if self.Root.Key > Key:
            return self.Root.pLeft.DelNode(Key)
        elif self.Root.Key < Key:
            return self.Root.pRight.DelNode(Key)
        else:# self.Root.Key == Key
            p = self # --> trouble ???
            if self.Root.pLeft.Root == None:
                self.Root = self.Root.pRight.Root
            elif self.Root.pRight.Root == None:
                self.Root = self.Root.pLeft.Root
            else:# Root has 2 children
                self.SearchStandFor(p, self.Root.pRight)
            del p # --> trouble ???
        return 1
 
def ReadFile(strFileName, t):
    OFile = open(strFileName, "r")
    text = OFile.readline()
    OFile.close()
 
    a = split(text, " ")
    for i in range(0,len(a)):
        t.InsertNode(int(a[i]))
 
def main():
    print
    t = Tree()
    ReadFile("TreeIn.txt", t)
    t.LNR() #--> 13 16 18 31 37 40 44 55 59 71 81 108
    print
    t.DelNode(44) # 44 is root, have two children
    t.LNR() #--> 13 16 18 31 37 40 55 55 59 71 81 108
    # I write t.DelNode(13), it don't run exactly, 13 is a node have 1 child (right child)
    # ... and if I don't define function __del__ of clas Node, it runs exactly, why???
 
main()
#content of file TreeIn.txt is "44 18 37 13 31 40 81 59 108 55 71 16"