了解传奇算法，先从二叉搜索树开始

萧山财神

二叉搜索树（Binary Search Tree, BST）是一种常用的数据结构，它具有以下性质：

1. 每个节点都有一个键值。
2. 左子树中所有节点的键值都小于根节点的键值。
3. 右子树中所有节点的键值都大于根节点的键值。
4. 左右子树也分别是二叉搜索树。

下面是一个用 Lua 编写的二叉搜索树实现示例：

二叉搜索树实现

-- 定义节点类
Node = {}
Node.__index = Node

function Node:new(key, value)
    local node = {
        key = key,
        value = value,
        left = nil,
        right = nil
    }
    setmetatable(node, Node)
    return node
end

-- 定义二叉搜索树类
BST = {}
BST.__index = BST

function BST:new()
    local bst = {
        root = nil
    }
    setmetatable(bst, BST)
    return bst
end

-- 插入节点
function BST:insert(key, value)
    local newNode = Node:new(key, value)
    if self.root == nil then
        self.root = newNode
    else
        self:_insertNode(self.root, newNode)
    end
end

function BST:_insertNode(node, newNode)
    if newNode.key < node.key then
        if node.left == nil then
            node.left = newNode
        else
            self:_insertNode(node.left, newNode)
        end
    else
        if node.right == nil then
            node.right = newNode
        else
            self:_insertNode(node.right, newNode)
        end
    end
end

-- 查找节点
function BST:find(key)
    return self:_findNode(self.root, key)
end

function BST:_findNode(node, key)
    if node == nil then
        return nil
    elseif key < node.key then
        return self:_findNode(node.left, key)
    elseif key > node.key then
        return self:_findNode(node.right, key)
    else
        return node.value
    end
end

-- 删除节点
function BST:remove(key)
    self.root = self:_removeNode(self.root, key)
end

function BST:_removeNode(node, key)
    if node == nil then
        return nil
    elseif key < node.key then
        node.left = self:_removeNode(node.left, key)
        return node
    elseif key > node.key then
        node.right = self:_removeNode(node.right, key)
        return node
    else
        -- 节点有两个子节点
        if node.left ~= nil and node.right ~= nil then
            local minNode = self:_findMinNode(node.right)
            node.key = minNode.key
            node.value = minNode.value
            node.right = self:_removeNode(node.right, minNode.key)
            return node
        -- 节点只有一个子节点或没有子节点
        else
            if node.left ~= nil then
                return node.left
            else
                return node.right
            end
        end
    end
end

function BST:_findMinNode(node)
    while node.left ~= nil do
        node = node.left
    end
    return node
end

-- 中序遍历
function BST:inOrderTraversal()
    self:_inOrderTraversal(self.root)
end

function BST:_inOrderTraversal(node)
    if node ~= nil then
        self:_inOrderTraversal(node.left)
        print(node.key, node.value)
        self:_inOrderTraversal(node.right)
    end
end

-- 测试二叉搜索树
local bst = BST:new()

bst:insert(50, "Value 50")
bst:insert(30, "Value 30")
bst:insert(70, "Value 70")
bst:insert(20, "Value 20")
bst:insert(40, "Value 40")
bst:insert(60, "Value 60")
bst:insert(80, "Value 80")

print("中序遍历结果:")
bst:inOrderTraversal()

print("查找键 70:", bst:find(70))  -- 输出: Value 70
print("查找键 25:", bst:find(25))  -- 输出: nil

bst:remove(70)
print("删除键 70 后的中序遍历结果:")
bst:inOrderTraversal()

解释

1. Node类：定义了二叉搜索树的节点类，包含键、值、左子节点和右子节点。

   • new 方法：创建一个新的节点实例。

2. BST类：定义了二叉搜索树类，包含根节点。

   • new 方法：创建一个新的二叉搜索树实例。
   • insert 方法：插入一个键值对。
   • _insertNode 方法：递归地将新节点插入到正确的位置。
   • find 方法：查找一个键对应的值。
   • _findNode 方法：递归地查找节点。
   • remove 方法：删除一个键值对。
   • _removeNode 方法：递归地删除节点，并维护树的性质。
   • _findMinNode 方法：查找子树中的最小节点。
   • inOrderTraversal 方法：中序遍历树，并打印键值对。
   • _inOrderTraversal 方法：递归地进行中序遍历。

3. 测试代码：创建一个二叉搜索树实例，插入一些键值对，进行查找、删除操作，并输出中序遍历结果。

输出

运行上述代码将输出以下内容：

中序遍历结果:
20  Value 20
30  Value 30
40  Value 40
50  Value 50
60  Value 60
70  Value 70
80  Value 80
查找键 70: Value 70
查找键 25: nil
删除键 70 后的中序遍历结果:
20  Value 20
30  Value 30
40  Value 40
50  Value 50
60  Value 60
80  Value 80

这个简单的二叉搜索树实现可以根据实际需求进行调整，例如支持更多的操作、优化性能等。通过合理的二叉搜索树算法，可以实现高效的数据存储和查找操作。

简单男孩

大佬牛牛牛

zheshankkk

66666666666666666