lua构造完美二叉树

渴望飞翔的猪

发布于 2022-07-17 10:48:10

4120

发布于 2022-07-17 10:48:10

文章被收录于专栏：葵花宝典007

杂话：

最近这几天闲来无事，公司的游戏马上要上线了，觉得最近几个月自己的状态都不是很好，刚公司招来的一个嘴强王者实习期完被劝退了(手动滑稽)主要是他自己也没有目标吧，打算把公司项目的一些代码看一遍，的确是有点纠结，函数跳来跳去的，不过我还是必须要弄懂，最后想了想还是从自己感兴趣的地方开始看。

进入正题：

有个现金赛的需求，基本流程就是海选出32强，然后分四组8个人，俩俩pk赛，最后的4个人进行冠亚军争霸，由于数据结构的构造不到位，导致各种状态很难管理。最后也gg了，交给了别人来接手. 其实第一眼看到这种流程的比赛，就应该想起数状图的形式，就应该想起用树的结构来管理各部分的节点的。然后每个节点包括二个人的战斗的各种状态，发给客户端的数据就是把整个树的结构都推过去，这样也灵活管理，要是策划想改X强也不用改多少逻辑。

    重点是今天下用lua来写构造一个二叉树，中间有个小坑，感觉自己弱的数据结构没学好啊，以后还是要多看看别人的代码，虽然我现在也不想看书，之前也问过公司的一个人，写代码这种东西，还是强调实干，看那么多书，然并卵，又不是去教书。

function CreateTree(dep)
    local root = {lchild =nil,rchild = nil,parent=nil,seq = 1,dep = 1}
    CreateNode(root,dep)
    return root
end 

function CreateNode(node,dep)
    if node.dep >= dep then
        return
    end

    local lnode= {parent = node,lchild =nil,rchild =nil,seq = 2*node.seq ,dep = node.dep+1}  --这里有个小坑，第一次写的时候没有前面加local 导致出问题
    local rnode = {parent = node,lchild =nil,rchild =nil,seq = 2*node.seq + 1,dep = node.dep+1}
    CreateNode(lnode,dep)
    CreateNode(rnode,dep)
    node.lchild = lnode
    node.rchild = rnode
end 


function PrintTree(node,run_func)
    --先序列
    io.write(node.seq)
    if node.lchild then
        PrintTree(node.lchild)  
    end
    if node.rchild then
        PrintTree(node.rchild)  
    end
end 

local tree =CreateTree(3)
PrintTree(tree)
print()

看了公司人的另外一种写法，其实是一样，不过还是规范些吧。

function CreateTree(dep)
    local root = {lchild =nil,rchild = nil,parent=nil,seq = 1,dep = 1}
    root.lchild = CreateNode(root,0,dep)    
    root.rchild = CreateNode(root,1,dep)    
    return root
end


function CreateNode(node,position,dep)
    if node.dep >= dep then
        return
    end 

    local new_node= {parent = node,lchild =nil,rchild =nil,seq = 0,dep = node.dep+1}
    new_node.seq = (position == 0 and node.seq*2 or node.seq*2+1)
    new_node.lchild = CreateNode(new_node,0,dep)
    new_node.rchild = CreateNode(new_node,1,dep)

    return new_node
end

function PrintTree(node)
    --先序列
    io.write(node.seq)
    if node.lchild then
        PrintTree(node.lchild)  
    end 
    if node.rchild then
        PrintTree(node.rchild)  
    end 
end

local tree =CreateTree(3)
PrintTree(tree)
print()

以后没事还是多谢谢博客，起码感觉上是对自己的总结

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017-12-05，如有侵权请联系 cloudcommunity@tencent.com 删除

lua