二叉搜索树

定义

一棵二叉树，对于该树上的每个节点，都有该左节点的值不大于该节点的值，右节点的值不小于该节点的值。

节点结构

class Node(object):
    def __init__(self,parent,lchild,rchild,value):
        self.parent=parent
        self.lchild=lchild
        self.rchild=rchild
        self.value=value

查找节点

这里给出两种方法，实质都是递归，就是循环

#查找
#用while循环
#x为根节点，k为要查找的值
def tree_search(x,k):
    p=x
    while p!=None:
        if k<p.value:
            p=p.lchild
        elif k>p.value:
            p=p.rchild
        else:
            return p
    return p

#使用递归
def tree_search_2(x,k):
    if x==None or x.value==k:
        return x
    if x.value<k:
        return tree_search_2(x.rchild,k)
    else:
        return tree_search_2(x.lchild,k)

查找后继节点

#查找节点x的后继节点
#主要分为以下几种情况：x有右节点；x没有右节点但为父节点的左子树；x没有右节点但为父节点的右子树
#x有右节点，找出右节点下的最小节点即为后继节点
#x没有右节点但为父节点的左子树，很简单，父节点即为后继节点
#x没有右节点但为父节点的右子树，向上遍历，直到该节点为该节点的父节点的左子树(此节点为大于x的最小的节点)或者该节点的父节点为空(不存在大于x的节点)，则该节点为后继节点
def tree_successor(x):
    if x.rchild!=None:
        p=x
        while p.lchild!=None:
            p=p.lchild
        return p
    elif x.parent==None or x.parent.lchild==x:
        return x.parent
    else:
        y=x.parent
        while y!=None and y.rchild==x:
            x=y
            y=y.parent
        return y

插入

一直走到叶子结点或者叶子节点的父节点

#插入
#t为根节点，z为要插入的节点
def tree_insert(t,z):
    p=t
    while p!=None:
        if z.value>p.value:
            p=p.rchild
        else:
            p=p.lchild
    y=p.parent
    z.parent=y
    if z.value>y.value:
        y.rchild=z
    else:
        y.lchild=z

删除

#t为根节点，z为要删除的节点；（这个问题就是找到z的后继节点，然后将后继节点放置到z的位置）
#分几种情况：z没有子节点；z只有左子树；z只有右字树；z既有左子树又有右子树
#z没有子节点：直接删除即可
#z只有左子树：将左子树移到z的位置
#z只有右子树：将右子树移到z的位置
#z既有左子树又有右子树：后继节点在右子树，遍历找到后继节点y，
#    y的孩子只有两种情况，一种是没有孩子，一种是只有右孩子；
#    没孩子就直接将y替换z，如果有右孩子，将右孩子和置于y的位置，y置于z的位置

#下面有很多重复代码，没有简化，是为了更清楚
def tree_delete(t,z):
    if z.lchild==None and z.rchild==None:
        z=None
    elif z.lchild == None:
        p=z.rchild
        z.value=p.value
        z.rchild=p.rchild
        z.lchild=p.lchild
        p=None
    elif z.rchild == None:
        p=z.lchild
        z.value=p.value
        z.rchild=p.rchild
        z.lchild=p.lchild
        p=None
    else:
        y=tree_successor(z)
        if y.rchild==None:
            z.value=y.value
            y=None
        else:
            z.value=y.value
            p=y.rchild
            y.value=p.value
            y.lchild=p.lchild
            y.rchild=p.rchild
            p=None