Python은 두 갈래 정렬 트리의 검색, 삽입, 삭제를 실현합니다

코드:

import sys
import gc
sys.path.append("F:\Workspace")
from Algorithm.TreeNode import TreeNode


def SearchBST(t: TreeNode, key: int)->bool:
    if t is None:
        return False
    if key == t.val:
        return True
    elif key < t.val:
        return SearchBST(t.left, key)
    else:
        return SearchBST(t.right, key)


def InsertBST(t: TreeNode, key: int)->TreeNode:
    new_t = TreeNode(key, None, None)
    if t is None:
        t = new_t
    else:
        if key < t.val:
            t.left = InsertBST(t.left, key)
        elif key > t.val:
            t.right = InsertBST(t.right, key)
    return t


def DeleteBST(t: TreeNode, key: int)->bool:
    if t is None:
        return False
    else:
        if key == t.val:
            return Delete(t)
        elif key < t.val:
            return DeleteBST(t.left, key)
        else:
            return DeleteBST(t.right, key)


def Delete(p: TreeNode)->bool:
    if p.right is None:  #      ，       
        q = p
        p = p.left
        del q
    elif p.left is None:  #      ，       
        q = p
        p = p.right
        del q
    else:                 #         
        q, s = p, p.left
        while s.right:
            q = s
            s = s.right
        p.val = s.val
        if q != p:
            q.right = s.left
        else:
            q.left = s.left
        del s
    gc.collect()
    return True


def inorder_traversal(t: TreeNode):
    if t is None:
        return
    inorder_traversal(t.left)
    print(t.val, end=" ")
    inorder_traversal(t.right)


if __name__ == '__main__':
    root = TreeNode(62,
                    TreeNode(58, TreeNode(47, TreeNode(35, None, TreeNode(37, None, None)), TreeNode(51, None, None)), None),
                    TreeNode(88, TreeNode(73, None, None), TreeNode(99, TreeNode(93, None, None), None))
                    )
    print("         ：", end=" ")
    inorder_traversal(root)
    print()
    print("  47     ：", SearchBST(root, 47))
    print("    49   ：", InsertBST(root, 49))
    print("         ：", end=" ")
    inorder_traversal(root)
    print()
    print("    47   ：", DeleteBST(root, 47))
    print("         ：", end=" ")
    inorder_traversal(root)

출력:

         ： 35 37 47 51 58 62 73 88 93 99 
  47     ： True
    49   ： 
         ： 35 37 47 49 51 58 62 73 88 93 99 
    47   ： True
         ： 35 37 49 51 58 62 73 88 93 99