树结构

hide秀

如：暗黑式的技能加点和梦幻模拟战的转职 {/wx}
节点属性可自行添加 如:requireSkillPoint,requireLevel 等
这个范例只定义了基本的属性 名称,父节点名称,层 等

=begin
   
   树结构
   
   作者: 秀秀
   
   树结构示意图

            (父树)(0层)
               ●
              /  \               
             /    \               
            /      \  
           ●      ●   (子树)(1层)
          /      / | \  
         /      ● ● ●(子树)(2层)
        ●         |      
                   ●   (子树)(3层)
                   /\   
                 ●  ● (子树)(4层)

=end

  #--------------------------------------------------------------------------
  # ● 树的类
  #--------------------------------------------------------------------------
class Tree
  def initialize
    @topTree = nil
    @sonTrees = []
    @layerStruct = {}
  end
  
  #--------------------------------------------------------------------------
  # ● 建立父结点
  #    idName   为id标示
  #--------------------------------------------------------------------------
  def createTopTree(idName)
    return if @topTree != nil
    @topTree = CreateTopTree.new(idName)
    @layerStruct[@topTree.layer] = []
    @layerStruct[@topTree.layer] << @topTree.idName
    return
  end

  #--------------------------------------------------------------------------
  # ● 建立一个子树
  #    fatherLinkId    为父联结点标号
  #    idName          建立的为子树标号
  #--------------------------------------------------------------------------
  def createSonTree(fatherLinkIdName,idName)
    #----------------------
    # 遍历所有IdName  
    # 判断标号是否存在重名
    # 判断父标号是否存在   
    #----------------------
    @layerStruct.values.each{|n|
      break if n.include?(idName)
      if n.include?(fatherLinkIdName)
        @nowLayer = @layerStruct.rKey(n) + 1
        break
      end  
    }
    if @nowLayer == nil
      return  
    end
    @sonTrees << CreateSonTree.new(idName,@nowLayer,fatherLinkIdName)
    if @layerStruct[@nowLayer] == nil
       @layerStruct[@nowLayer] = []
    end  
    @layerStruct[@nowLayer] << idName
  end  
  
  #--------------------------------------------------------------------------
  # ● 删除一个结点
  #--------------------------------------------------------------------------
  def deleteALinkPoint(idName)
    return if idName == @topTree.idName
    # 如果存在删除此结点
    # 并且删除包含的全部子结点
    if checkIdNameExist?(idName)
      @tempId = []
      # 删除此结点
      @layerStruct.clone.values.each do |n|
        if n.include?(idName)
          @layerStruct[@layerStruct.rKey(n)].delete(idName)
        end
      end  
      @sonTrees.clone.each do |n|
        @sonTrees.delete(n) if n.idName == idName
        @tempId << idName if [email protected]?(idName)
        @tempId << n.idName if @tempId.include?(n.fatherLinkIdName)
      end

      # 删除所有子结点
      @sonTrees.clone.each do |n|
        @sonTrees.delete(n) if @tempId.include?(n.idName)
      end  

      @needDelete = []
      @layerStruct.clone.values.each{|n|
        n.each{|m|
          if @tempId.include?(m)
            @needDelete << m
          end
        }
        @needDelete.each{|k|
          @layerStruct[@layerStruct.rKey(n)].delete(k)
        }
      }  

      # 如果value为空 则删除key
      @layerStruct.clone.values.each do |n|
        if @layerStruct[@layerStruct.rKey(n)].empty?
          @layerStruct.delete(@layerStruct.rKey(n))
        end  
      end
      @needDelete.clear
      @tempId.clear
      return
    end

  end
  

  #--------------------------------------------------------------------------
  # ●指向上级父结点
  #--------------------------------------------------------------------------
  def pointFather(idName)
    return if idName == @topTree.idName
    @sonTrees.each do |n|
      if n.idName == idName
        @name = n.fatherLinkIdName
        break
      end  
    end  
    return @name
  end  
  
  #--------------------------------------------------------------------------
  # ●检查结点是否存在
  #--------------------------------------------------------------------------
  def checkIdNameExist?(idName)
    @layerStruct.values.each{|n|
      return true if n.include?(idName)
    }
    return false
  end
  
  #--------------------------------------------------------------------------
  # ●返回此结点当前所在层
  #--------------------------------------------------------------------------
  def rNowlayer(idName)
    return if idName == @topTree.idName
    @sonTrees.each do |n|
      if n.idName == idName
        @layer = n.layer
        break
      end  
    end  
    return @layer
  end
  
  #--------------------------------------------------------------------------
  # ●获取当前层上的节点数
  #--------------------------------------------------------------------------
  def rNowLayer_idCount(layer)
    return @layerStruct[layer].length
  end

  #--------------------------------------------------------------------------
  # ●获取树的总层数
  #--------------------------------------------------------------------------
  def rAll_layer_count
    return @layerStruct.keys.size
  end
  
  #--------------------------------------------------------------------------
  # ●获取树的总节点数
  #--------------------------------------------------------------------------
  def rAll_Id_count
    return @sonTrees.length + 1
  end


  #--------------------------------------------------------------------------
  # ●获取当前结点的最近子结点ID集合
  #--------------------------------------------------------------------------
  def rNowID_sonID_Count(idName)
    names = []
    @sonTrees.each{|n|
    names << n.idName if n.fatherLinkIdName == idName
    }
    return names
  end  
  
  #--------------------------------------------------------------------------
  # ●显示当前树结构
  #--------------------------------------------------------------------------
  def showTreeStru
    return @layerStruct
  end  
end

  #--------------------------------------------------------------------------
  # ● 建立一个祖先
  #--------------------------------------------------------------------------
class CreateTopTree
  attr_reader     :idName
  attr_reader     :layer      
  def initialize(name)
    @idName = name
    @layer = 0
  end
end

  #--------------------------------------------------------------------------
  # ● 建立子结点
  #--------------------------------------------------------------------------
class CreateSonTree < CreateTopTree
  attr_reader     :idName
  attr_reader     :layer
  attr_reader     :fatherLinkIdName
  def initialize(name,layer,fatherName)
    super(name)
    @layer = layer
    @fatherLinkIdName = fatherName
  end
end

class Hash < Object
  def rKey(avalue)
    self.each_pair{|key, value|
    if avalue == value
      @temp = key
      break
    end
    }
    if @temp != nil
      return @temp
    else
      return nil
    end  
  end
end

#--------------------------------------------------------------------------
# ● 以下是测试
#--------------------------------------------------------------------------
@t = Tree.new
@t.createTopTree("洋葱战士")

@t.createSonTree("洋葱战士","战士")
@t.createSonTree("洋葱战士","见习魔法师")
@t.createSonTree("洋葱战士","盗贼")

@t.createSonTree("战士","骑士")
@t.createSonTree("战士","圣骑士")

@t.createSonTree("见习魔法师","黑魔法师")
@t.createSonTree("见习魔法师","白魔法师")

@t.createSonTree("盗贼","刺客")
@t.createSonTree("盗贼","忍者")

# 检查是否存在节点 盗贼
p @t.checkIdNameExist?("盗贼")
# 显示节点 战士 下的子节点
p @t.rNowID_sonID_Count("战士")
# 显示节点 见习魔法师的当前层(第几次专职)
p @t.rNowlayer("见习魔法师")
# 显示忍者的父职业
p @t.pointFather("忍者")
# 显示职业结构
p @t.showTreeStru
# 删除节点 "见习魔法师"
@t.deleteALinkPoint("见习魔法师")
# 再显示职业结构
p @t.showTreeStru

cmzjbczzf

看不太懂

有什么用呢

（虽然明知我的游戏用不上）

做游戏的新手

不太懂哎..

ygshoward

不明白樓主講緊乜。

yangff

在pascal里用point。
2X树：
class Tree
def lt
  return @lt
end
def rt
  return @rt
end
def lt=(v)
  @lt = v
end
def rt=(v)
  @rt = v
end
def va
  return @va
end
def va=(value)
  @va = value
end
end

tt = Tree.new
a = [0,1,2,3,4,5]
make(0)
def make(n,t)
a.va=a[n]
if n+1 <= a.size-1
t.lt=Tree.new
t.rt = Tree.new
make(n+1,t.lt)
if n+2 <= a.size-1
make(n+2,t.rt)
end
end
end
差不多是这样的………………
树还是pascal方便

dbshy

以下引用一路一风尘于2008-9-24 10:29:50的发言：

这个数据建立的本身倒不难，
只是一但涉及到技能排列与光标切换刷新的界面，除非是规则的矩阵，否则就麻烦了— —

深有同感，以前自己写仿暗黑技能树的时候，结构不难，就是写界面刷新和技能排列的时候
好麻烦 = =

轮回者

同lS
不过，LZ的东西还是有用的~
至少不用写一遍树了~

hide秀

深有同感，以前自己写仿暗黑技能树的时候，结构不难，就是写界面刷新和技能排列的时候
好麻烦 = =

用这个其实很简单 把节点自定义属性 如图标文件名,技能等级，威力等 定义为 attr_accessor
然后 更新遇到升级 需要refresh的时候 更新所有节点信息。。。- -