Modul:Benutzer:Thoken/Algor2

Die Dokumentation für dieses Modul kann unter Modul:Benutzer:Thoken/Algor2/Doku erstellt werden

-- binary search tree
-- konsole> tn=p.treenode(); tn:insert(3,"c"); tn:insert(5,"e"); tn:insert(2,"b"); tn:insert(1,"a"); tn:insert(4,"d");
-- konsole> =tn:search(4)
--   returning  "d"
-- konsole> =tn:list()
--   returning  ";a:1;b:2;c:3;d:4;e:5"
-- konsole> =tn:show()
--   returning         a
--                  b
--               c
--                     d
--                  e
p={}
function p.treenode() -- using code from http://www.mail-archive.com/kragen-hacks@canonical.org/msg00211.html
  return {
    search = function(self, key)
        if self.key == nil then return end -- leafnode case
        if key == self.key then return self.value end -- key match
        if key < self.key then return self.left:search(key) end
        return self.right:search(key) 
    end,
    insert = function(self, key, value)
        if self.key == nil then -- morph into an internal node
          self.key, self.value, self.left, self.right = key, value, p.treenode(), p.treenode()
          return
        end
        if key == self.key then return end -- no key collision handling
        if key < self.key then return self.left:insert(key, value) end
        return self.right:insert(key, value)
    end,
    list = function(self) -- raw value-key list
        if self.key == nil then return "" end
        return self.left:list() .. ";" ..  self.value .. ":" .. self.key .. self.right:list()
    end,
    show = function(self, h) -- show indentation value tree
        if self.key == nil then return "" end
        local h = h or 0; local CR = "\n"; local TAB = "   "
        local indent = (function() local i,s = 1,""; while i<=h do s = s..TAB; i=i+1 end; return s end)()
        return self.left:show(h+1) .. indent .. self.value .. CR .. self.right:show(h+1)
    end
  }
end
return p