【算法】【python实现】二叉搜索树插入、删除、查找

2023-08-15 14:58:16

二叉搜索树

定义：如果一颗二叉树的每个节点对应一个关键码值，且关键码值的组织是有顺序的，例如左子节点值小于父节点值，父节点值小于右子节点值，则这棵二叉树是一棵二叉搜索树。

类（TreeNode）：定义二叉搜索树各个节点

在该类中，分别存放节点本身的值，以及其左子节点，右子节点，父节点的值。

class TreeNode(object):

    def __init__(self,val):

        self.value = val    #存值

        self.left = None    #存本节点的左子节点

        self.right = None   #存本节点的右子节点

        self.father = None  #存本节点的父节点

类（BST）：定义二叉搜索树的各种功能方法

此类用于存放定义二叉树的插入，删除，搜索等方法。

class BST(object):

    def __init__(self,nodeList):

        self.root = None

        for node in nodeList:

            self.bfs_insert(node)

注：self.bfs_insert(node)中的bfs_insert方法在后面实现。放在构造函数中的目的是将一个列表生成一个二叉搜索树列表。

方法（bfs_insert）：实现插入功能

第一步：将根节点（self.root）设置成当前位置节点（cur），即从根节点开始遍历。根节点的父节点（father）初始设置为None。

def bfs_insert(self,node):

    cur = self.root      #设置当前节点为根节点

    father = None        #设置根节点的父节点为None

第二步：查找可以插入的位置

1. 当前位置节点（cur）的值与待插入节点（node）的值相等，返回-1（代表无法进行插入操作）。并将父节点（father）值修改为当前位置节点（cur），代表该节点已经遍历完成。

if cur.value == node.value:

    return -1

father = cur

2.当前位置节点（cur）的值大于待插入节点（node）的值时，表示待插入节点（node）需继续在当前位置节点的左子树中继续查找。故把当前位置节点（cur）的左节点赋值给当前位置节点（cur），作为下一个要访问的节点对象。

if node.value < cur.value:

    cur = cur.left

3.当前位置节点（cur）的值小于待插入节点（node）的值时，表示待插入节点（node）需继续在当前位置节点的右子树中继续查找。故把当前位置节点（cur）的右节点赋值给当前位置节点（cur），作为下一个要访问的节点对象。

if node.value > cur.value:

    cur = cur.right

第三步：找到插入位置后，将其设置为待插入值（node）的父节点

node.father = father

第四步：插入操作

1.父节点的值为空（即要插入的是个空二叉树），将待插入节点（node）赋值给根节点（root）。

if father == None:

    self.root = node

2.待插入节点（node）的值小于父节点（father）的值，将其放到父节点的左子节点

if node.value <father.value:

    father.left = node

3.待插入节点（node）的值大于父节点（father）的值，将其放到父节点的右子节点

if node.value >father.value:

    father.right = node

插入功能代码汇总：

def insert(self,node):

    father = None

    cur = self.root

    while cur != None:

         if cur.value == node.value:

         	return -1

         father = cur

         if node.value < cur.value:

         	cur = cur.left

         else:

         	cur = cur.right

    node.father = father

    if father == None:

        self.root = node

    elif node.value < father.value:

        father.left = node

    else:

        father.right = node

方法（bfs）：生成二叉搜索树列表

利用队列先进先出的特性，将一个二叉搜索树存放到列表中。

def bfs(self):

    if self.root == None:

        return None

    retList = []

    q = queue.Queue()

    q.put(self.root)

    while q.empty() is not True:

        node = q.get()

        retList.append(node.value)

        if node.left != None:

            q.put(node.left)

        if node.right != None:

            q.put(node.right)

    return retList

示例：针对如下二叉搜索树，遍历存放到一个列表过程

ps：蓝色：二叉树列表 retList 橙色：队列 q

方法（bfs_search）：实现查找功能

第一步：将根节点（self.root）设置成当前位置节点（cur），即从根节点开始遍历。

def search(self,value):

    cur = self.root

如果cur值不为None，执行第二步。否则执行第三步

第二步：对比要查找的值（value）与当前位置节点（cur）的值的大小

1. 如果当前位置节点（cur）的值等于要查找的值（value），返回当前位置节点（cur）。

if cur.value == value:

    return cur

2. 如果当前位置节点（cur）的值小于要查找的值（value），返回当前位置节点（cur）。

if cur.value < value:

    cur = cur.right

3. 如果当前位置节点（cur）的值小于要查找的值（value），返回当前位置节点（cur）。

if cur.value > value:

    cur = cur.left

第三步：如果cur的值为None，返回空。即查找的二叉搜索树为空树。

return None

查找功能代码汇总：

def search(self,value):

    cur = self.root

    while cur != None:

        if cur.value == value:

            return cur

        elif cur.value < value:

            cur = cur.right

        else:

            cur = cur.left

    return None

方法（bfs_delete）：实现删除功能

第一步：将待删除节点（node）的父节点赋值给father变量。

def delete(self,node):

    father = node.father

第二步：判断待删除节点（node）的左子树是否为空

1. 待删除节点（node）的左子树为空

if node.left == None:

a) 待删除节点（node）为根节点

将待删除节点（node）的右子节点置为新的根节点（root），且其如果为非空，将其父节点（node.right.father）赋值为空。

if father == None:

    self.root = node.right

    if node.right != None:

        node.right.father = None

b) 待删除节点（node）为其父节点的左子节点

待删除节点（node）的右子节点（node.right）取代其原来的位置，成为其父节点新的左子节点（father.left）。且其右子节点（node.right）不为空，将待删除节点（node）的父节点赋值给它的父节点（node.right.father）

if father.left == node:

    father.left = node.right

    if node.right != None:

        node.right.father = father

c) 待删除节点（node）为其父节点的右子节点

待删除节点（node）的右子节点（node.right）取代其原来的位置，成为其父节点新的右子节点（father.right）。且其右子节点（node.right）不为空，将待删除节点（node）的父节点赋值给它的父节点（node.right.father）

if father.right == node:

    father.right = node.right

    if node.right != None:

        node.right.father = father

2. 待删除节点（node）的左子树不为空

第一步：将待删除节点（node）的右子树挂到其左子树最后一层的右子节点下

a) 将待删除节点的左子节点（node.left）存到临时变量tmpNode中

tmpNode = node.left

b) 递归找到node.left的最后一层右子节点

while tmpNode.right != None:

    tmpNode = tmpNode.right

c) 将待删节点的右子树（node.right）挂到node.left的最后一层右子节点下

tmpNode.right = node.right

d) 将node.right的父节点设置为待删节点左子树中的最后一层的右子节点

if node.right != None:

    node.right.father = tmpNode

第二步：开始删除node

1.待删除节点为根节点

将待删除节点的左子节点（node.left）设置为根节点（self.root），并将其父节点设置为空。

if father == None:

    self.root = node.left

    node.left.father = None

2.待删除节点为根节点的左子节点

待删除节点的左子节点（node.left）取代待删节点的位置，并将其父节点设置为待删除节点的父节点。

if father.left == node:

    father.left = node.left

    node.left.father = father

3. 待删除节点为根节点的右子节点

待删除节点的左子节点（node.left）取代待删节点的位置，并将其父节点设置为待删除节点的父节点

if father.right == node:

    father.right = node.left

    node.left.father = father

删除功能代码汇总：

def delete(self,node):

    father = node.father

    if node.left == None:

        if father == None:

            self.root = node.right

            if node.right != None:

                node.right.father = None

        elif father.left == node:

            father.left = node.right

            if node.right != None:

                node.right.father = father

        else:

            father.right = node.right

            if node.right != None:

                node.right.father = father

        return 'delete successfully'

    tmpNode = node.left

    while tmpNode.right != None:

        tmpNode = tmpNode.right

    tmpNode.right = node.right

    if node.right != None:

        node.right.father = tmpNode

    if father == None:

        self.root = node.left

        node.left.father = None

    elif father.left == node:

        father.left = node.left

        node.left.father = father

    else:

        father.right = node.left

        node.left.father = father

    node = None

    return 'delete successfully'

综上，二叉搜索树代码

# encoding=utf-8

import queue

class TreeNode(object):

    def __init__(self,val):

        self.value = val

        self.left = None

        self.right = None

        self.father = None

class BST(object):

    def __init__(self,nodeList):

        self.root = None

        for node in nodeList:

            self.bfs_insert(node)

    def bfs_insert(self,node):

        father = None

        cur = self.root

        while cur != None:

            if cur.value == node.value:

                return -1

            father = cur

            if node.value < cur.value:

                cur = cur.left

            else:

                cur = cur.right

        node.father = father

        if father == None:

            self.root = node

        elif node.value < father.value:

            father.left = node

        else:

            father.right = node

    def bfs(self):

        if self.root == None:

            return None

        retList = []

        q = queue.Queue()

        q.put(self.root)

        while q.empty() is not True:

            node = q.get()

            retList.append(node.value)

            if node.left != None:

                q.put(node.left)

            if node.right != None:

                q.put(node.right)

        return retList

    def bfs_search(self,value):

        cur = self.root

        while cur != None:

            if cur.value == value:

                return cur

            elif cur.value < value:

                cur = cur.right

            else:

                cur = cur.left

        return None

    def bfs_delete(self,node):

        father = node.father

        if node.left == None:

            if father == None:

                self.root = node.right

                if node.right != None:

                    node.right.father = None

            elif father.left == node:

                father.left = node.right

                if node.right != None:

                    node.right.father = father

            else:

                father.right = node.right

                if node.right != None:

                    node.right.father = father

            return 'delete successfully'

        tmpNode = node.left

        while tmpNode.right != None:

            tmpNode = tmpNode.right

        tmpNode.right = node.right

        if node.right != None:

            node.right.father = tmpNode

        if father == None:

            self.root = node.left

            node.left.father = None

        elif father.left == node:

            father.left = node.left

            node.left.father = father

        else:

            father.right = node.left

            node.left.father = father

        node = None

        return 'delete successfully'

if __name__ == '__main__':

    varList = [24,34,5,4,8,23,45,35,28,6,29]

    nodeList = [TreeNode(var) for var in varList]

    bst = BST(nodeList)

    print (bst.bfs())

    node = bst.bfs_search(34)

    bst.bfs_delete(node)

    print (bst.bfs())

码农公寓