binary tree implemention

#__author__ = 'one'

import random

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.p = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def length(self):
        return self.size

    def inorder(self, node):
        if node == None:
            return None
        else:
            self.inorder(node.left)
            print node.key,
            self.inorder(node.right)

    def search(self, k):
        node = self.root
        while node != None:
            if node.key == k:
                return node
            if node.key > k:
                node = node.left
            else:
                node = node.right
        return None

    def minimum(self, node):
        x = None
        while node.left != None:
            x = node.left
            node = node.left
        return x

    def maximum(self, node):
        x = None
        while node.right != None:
            x = node.right
            node = node.right
        return x

    def successor(self, node):
        parent = None
        if node.right != None:
            return self.minimum(node.right)
        parent = node.p
        while parent != None and node == parent.right:
            node = parent
            parent = parent.p
        return parent

    def predecessor(self, node):
        parent = None
        if node.left != None:
            return self.maximum(node.left)
        parent = node.p
        while parent != None and node == parent.left:
            node = parent
            parent = parent.p
        return parent

    def insert(self, k):
        t = TreeNode(k)
        parent = None
        node = self.root
        while node != None:
            parent = node
            if node.key > t.key:
                node = node.left
            else:
                node = node.right
        t.p = parent
        if parent == None:
            self.root = t
        elif t.key < parent.key:
            parent.left = t
        else:
            parent.right = t
        return t


    def delete(self, node):
        if node.left == None:
            self.transplant(node, node.right)
        elif node.right == None:
            self.transplant(node, node.left)
        else:
            succ = self.minimum(node.right)
            if succ.p != node:
                self.transplant(succ, succ.right)
                succ.right = node.right
                succ.right.p = succ
            self.transplant(node, succ)
            succ.left = node.left
            succ.left.p = succ

    def transplant(self, node, newnode):
        if node.p == None:
            self.root = newnode
        elif node == node.p.left:
            node.p.left = newnode
        else:
            node.p.right = newnode
        if newnode != None:
            newnode.p = node.p


#bst = BinaryTree()
#a = [random.randrange(1, 15) for i in range(16)]
#print a
#for i in a:
#    bst.insert(i)
#bst.inorder(bst.root)

#print
#z = TreeNode(None)
#z = bst.minimum(bst.root)
#print "the miniest number: ", z.key
#y = TreeNode(None)
#y = bst.maximum(bst.root)
#print "the maxiest number: ", y.key
#print

#w = TreeNode(None)
#w = bst.search(10)
#print "{} is in the tree".format(w.key)
#print


#u = TreeNode(None)
#u = bst.successor(w)
#v = TreeNode(None)
#v = bst.predecessor(w)
#print u.key
#print v.key
#print

#bst.delete(w)
#bst.inorder(bst.root)
#print

运行以后在新节点z, y, w, u, v上有时可以完好运行有时还是会出现

print u.key
AttributeError: 'NoneType' object has no attribute 'key'

这个要怎么改才行

---

经常会出现 AttributeError 是因为你自己作死，每次用随机数初始化树结构，每当树里面不存在 10 或者出现左子树/右子树为空的时候 bst 的方法就有可能返回 None，加上你没有检查返回值就直接调用 key 属性，当然就错了。

此外，python 用法上问题较多，看起来是才接触 python 不久吧。记住在 python 里面不需要声明变量类型，大量存在 w = TreeNode(None) 这种代码，我觉得你应该是想“声明”一个 TreeNode 变量然后使用吧，这是不必要。另外 python 2 里面定义 class 应该始终从 object 派生，比如 class TreeNode(object): ，这需要注意一下。

算法方面问题不是很大，要说错误的地方就是 minimum/maximum 都没有考虑 node 某个子树不存在的情况，比如 node.left == None 时 minimum 应该返回 node 本身。