[Lua] 程式設計教學：實作二元搜尋樹 (Binary Search Tree)

樹 (tree) 是一種非線性、階層的資料結構，由於樹有數種變體，大部分教科書都會以二元搜尋樹 (binary search tree) 做為樹的實例。以二元搜尋樹存取資料，往往會比串列更有效率。

由於程式碼略長，我們在這裡展示完整程式碼，讀者可自行觀看。

一般來說，我們會先建立一個內部節點類別：

local Node = {}

Node.__index = Node

function Node:new(data)
    self = {}

    self._data = data
    self.left = nil
    self.right = nil

    setmetatable(self, Node)
    return self
end

function Node:data()
    return self._data
end

接著，建立一個 Tree 物件，將 Node 物件包在裡面：

function Tree:new()
    self = {}
    self._root = nil

    setmetatable(self, Tree)
    return self
end

二元搜尋樹在取得元素時，會利用遞迴的特性，在此處我們額外使用一個內部函式來遞迴走訪元素：

local function contains(node, data)
    if node:data() == data then
        return true
    elseif data < node:data() then

        if node.left ~= nil then
            return contains(node.left, data)
        end
    else
        if node.right ~= nil then
            return contains(node.right, data)
        end
    end

    return false
end

function Tree:contains(data)
    if self._root == nil then
        return false
    end

    return contains(self._root, data)
end

插入元素時，會根據新的資料和現存的元素間的大小來決定插入的位置，日後才能快速搜尋：

local function insert(node, data)
    if data >= node:data() then
        if node.right == nil then
            local nodeNew = Node:new(data)
            node.right = nodeNew
        else
            node.right = insert(node.right, data)         
        end
    else
        if node.left == nil then
            local nodeNew = Node:new(data)
            node.left = nodeNew
        else
            node.left = insert(node.left, data)
        end
    end

    return node
end

function Tree:insert(data)
    if self._root == nil then
        local node = Node:new(data)
        self._root = node
        return
    end

    self._root = insert(self._root, data)
end

移除時，也要根據不同的情境採取不同的措施：

local function remove(node, data)
    if data > node:data() then
        if node.right == nil then
            return node, nil
        else
            node.right = remove(node.right, data)
        end
    elseif data < node:data() then
        if node.left == nil then
            return node, nil
        else
            node.left = remove(node.left, data)
        end
    else
        if node.left == nil and node.right == nil then
            return nil, data
        elseif node.left == nil then
            node = node.right
        elseif node.right == nil then
            node = node.left
        else
            node._data = node.right:data()
            node.right, _ = remove(node.right, node:data())
        end
    end

    return node, data
end

function Tree:remove(data)
    if self._root == nil then
        return nil
    end

    self._root, popped = remove(self._root, data)

    return popped
end