二叉排序树的查找、插入、创建、结点删除python实现（大话数据结构版本）

青旅半醒 2022-03-02 11:06 245阅读 0赞

## 定义结点 ##

首先定义一个二叉链表结点结构的定义

class Node(object):
        """节点定义，包括数据项、左孩子、右孩子"""
        def __init__(self, data):
            self.data = data
            self.lchild = None
            self.rchild = None

## 查找 ##

def searchTree(T, key, f, p):
        """查找
            T:树；
            key：查找的节点
            f：指向T的双亲，初始值为None
            p：若未查找到，则返回最后一个访问的叶子结点；若查找到，则返回搜索到的结点"""
        if not T:
            """T为空树，查找失败
                p为空树的双亲结点，即访问的最后一个结点"""
            p = f
            return False, p
        elif key == T.data:
            """查找成功
                p为当前查找的结点"""
            p = T
            return True, p
        elif key > T.data:
            """查找右子树"""
            return searchTree(T.rchild, key, T, p)
        else:
            """查找左子树"""
            return searchTree(T.lchild, key, T, p)

## 插入 ##

def insertTree(T, key):
        """插入"""
        is_exist, p = searchTree(T, key, None, None) #返回key是否已存在以及查找时访问的最后一个结点p
        if not is_exist:
            """key在树中不存在，插入"""
            s = Node(key)
            if p == None:
                """p为空代表树为空"""
                T = s  #s作为根节点插入
            elif key > p.data:
                p.rchild = s # s放到p节点的右孩子
            else:
                p.lchild = s # s作为p节点的左孩子
            print("节点 %s 已加入" %key)
            return T
        else:
            """key已存在，无需插入"""
            print("节点 %s 已存在" %key)
            return T

## 创建 ##

此时创建时，可以调用上述两个函数【查找】，【插入】，先查找，不存在则插入

def createTree(NodeList):
        """创建二叉排序树, NodeList为待插入数据的列表"""
        T = None
        for i in range(len(NodeList)):
            T = insertTree(T, NodeList[i])
        return T

## 删除结点 ##

删除结点时，从最后一个函数看起，如果树中不存在该结点，则删除失败，只有树中存在该结点时才删除

第二个函数执行的操作是找到要删除的结点，然后对该结点进行删除

第一个函数执行的操作是删除结点T：

1.若结点T的左子树为空，则用T的右子树替代T，即为删除了T结点

2.若结点T的右子树为空，则用T的左子树替代T，即为删除了T结点

3.若结点T的左右子树均不为空，则从T的子树中找一个结点s代替T，最后再把s结点删除，那么这个s结点怎么找呢？s结点需要比T的左孩子大比T的右孩子小，并且是右子树必须为空的结点，那么循环找到T的左子树的右节点，直到找到尽头，这个结点就是我们要找的s结点。

def Delete(T):
        """删除结点T"""
        if T.lchild == None:
            """左子树为空"""
            T = T.rchild
        elif T.rchild == None:
            """右子树为空"""
            T = T.lchild
        else:
            """左右子树均不为空"""
            p = T
            s = T.lchild
            while s.rchild:
                p = s
                s = s.rchild
            T.data = s.data
            if p != T:
                p.rchild = s.lchild
            else:
                """此时p = T,说明用的T的左孩子来替代T"""
                p.lchild = s.lchild
    
    def DeleteNode(T, key):
        if key == T.data:
            Delete(T)
        elif key > T.data:
            DeleteNode(T.rchild, key)
        else:
            DeleteNode(T.lchild, key)
        return T
    
    def DeleteNodeFromTree(T, key):
        bull, p = searchTree(T, key, None, None)
        if not bull:
            print("这棵树中不存在结点 %s, 删除失败"%key)
            return T
        else:
            return DeleteNode(T, key)