Project1

标题: 树结构 [打印本页]

作者: hide秀 时间: 2008-9-24 17:14
标题: 树结构
如：暗黑式的技能加点和梦幻模拟战的转职 {/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 时间: 2008-9-24 17:58
看不太懂

有什么用呢

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

作者: 做游戏的新手 时间: 2008-9-24 18:21
不太懂哎..

作者: 一路一风尘 时间: 2008-9-24 18:29
提示: 作者被禁止或删除内容自动屏蔽

作者: ygshoward 时间: 2008-9-24 19:52
不明白樓主講緊乜。

作者: yangff 时间: 2008-9-24 21:41
在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-25 04:02

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

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

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

作者: 轮回者 时间: 2008-9-25 05:13
同lS
不过，LZ的东西还是有用的~
至少不用写一遍树了~

作者: hide秀 时间: 2008-9-25 06:56

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

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

作者: 越前リョーマ 时间: 2008-9-27 04:47
看不大懂啊…… = =

作者: yangff 时间: 2008-9-29 01:26

以下引用越前リョーマ于2008-9-26 20:47:45的发言：

看不大懂啊…… = =

离散数学的图论理有说。。。

作者: dbshy 时间: 2008-9-29 03:37

以下引用yangff于2008-9-28 17:26:06的发言：

以下引用越前リョーマ于2008-9-26 20:47:45的发言：

看不大懂啊…… = =

离散数学的图论理有说。。。

高中时学过,好难,基本上看不懂,好象当时还学了什么组合数学

作者: ONEWateR 时间: 2008-11-23 05:27
发布完毕
http://rpg.blue/web/htm/news1199.htm
vip += 2

作者: 松谷修三 时间: 2008-11-24 01:12
{/jy}那个提供一下范例可以不？{/hx}

作者: 越前リョーマ 时间: 2008-11-24 01:23
我记得这个东西难的是自动化的排版吧……

作者: hcy910 时间: 2008-11-26 23:09
呃....那啥，看不懂...怎么用啊？

作者: 一路一风尘 时间: 2009-6-12 08:00
提示: 作者被禁止或删除内容自动屏蔽

作者: DeathKing 时间: 2009-7-5 23:43
强帖一个，顶一下，希望LZ整理一下帖子，最好附带个工程……

作者: dna_7086 时间: 2009-7-16 01:34
提示: 作者被禁止或删除内容自动屏蔽

作者: RPG极品菜鸟 时间: 2009-9-4 18:26
提示: 作者被禁止或删除内容自动屏蔽

欢迎光临 Project1 (https://rpg.blue/)