多叉树到单链表结构的转换源代码

      由于Animation结构体的定义为单链表形式，需要把多叉树骨骼数据转换为单链表中，十分头疼。

      写之前要把转换的逻辑顺序想清楚，我在这采取深度优先（先深度后宽度）搜索，类似二叉树的前序遍历。把相关的几个函数帖出，区区几十行，但要把逻辑顺序想明白了，或许还有不对的地方。

/********************************************************
函数名称：FindFirstLeaf
功能描述：寻找本节点的叶子节点
参数说明：无

返 回 值：叶子节点
*********************************************************/
Frame_EX* Frame_EX::FindFirstLeaf()
{
 Frame_EX* pFrame = FirstChildHaveSibling();
 if(pFrame == this || pFrame->IsLeaf())
  return pFrame;
 else
  return pFrame->m_pFrameSibling->LastLeaf();
}

//宽度搜索本节点的最后一个兄弟节点，如果没有则返回自身
Frame_EX* Frame_EX::LastSibling()
{
 Frame_EX* pFrame = m_pFrameSibling;
 if(!pFrame)
  return this;

 Frame_EX* pFramePrev;
 while(pFrame)
 {
  pFramePrev = pFrame;
  pFrame = pFrame->m_pFrameSibling;
 }
 return pFramePrev;
}

//深度搜索本节点下第一个有兄弟节点的孩子节点
//如果无孩子节点则返回自身，如果所有孩子节点均无兄弟节点则返回最后一个孩子节点
Frame_EX* Frame_EX::FirstChildHaveSibling()
{
 Frame_EX* pFrame = m_pFrameFirstChild;
 if(!pFrame)
  return this;

 Frame_EX* pFrameAfter = pFrame->m_pFrameFirstChild;

 while(!pFrame->m_pFrameSibling && pFrameAfter)
 {
  pFrame = pFrameAfter;
  pFrameAfter = pFrameAfter->m_pFrameFirstChild;
 }
 return pFrame;
}

//宽度优先（先宽度后深度）搜索本节点下最后一个叶子节点
Frame_EX* Frame_EX::LastLeaf()
{
 if(IsLeaf())
  return this;

 Frame_EX* pFrame;
 pFrame = LastSibling();  //先宽度
 pFrame = pFrame->FirstChildHaveSibling(); //后深度

 return pFrame->LastLeaf();
}

 

/********************************************************
函数名称：AddAnimationRecursive
功能描述：递归创建骨骼动画
参数说明：pFramePrev  动画链表中上一级动画相关联的骨骼
    pFrame   待加入到链表中的骨骼动画

返 回 值：无
*********************************************************/
void SkeletonAnimation::AddAnimationRecursive(Frame_EX* pFramePrev, Frame_EX* pFrame)
{
 if(!pFrame)
  return;

 LPAnimation pAnimation = new Animation();
 pAnimation->pBoneName = pFrame->m_name;
 pAnimation->pBone = pFrame;

 //加入当前动画集合，pFramePrev为NULL加入到m_pAnimationSet中
 if(!pFramePrev)
 {
  pAnimation->pNext = m_pAnimationSet->pAnimations;
  m_pAnimationSet->pAnimations = pAnimation;
  m_pAnimationSet->nAnimation++;
 }
 else
 {
  pAnimation->pNext = NULL;
  m_pAnimationSet->Find(pFramePrev)->pNext = pAnimation;
  m_pAnimationSet->nAnimation++;
 }

 if(pFrame->m_pFrameFirstChild)
  AddAnimationRecursive(pFrame, pFrame->m_pFrameFirstChild);

 if(pFrame->m_pFrameSibling)
  AddAnimationRecursive(pFrame->FindFirstLeaf(), pFrame->m_pFrameSibling);
}

责任编辑 webmaster

相关链接

数据结构之 2-3-4 树

Linux内核常用数据结构和操作

读核笔记:数据结构之红黑树

判断单链表是否有环-步长法证明

程序员数据结构笔记

C程序单链表面试题详解

逆置动态单链表

数据结构的变长字段设计