树结构

=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