数据结构之生成树

;   生成树（Spanning Tree） 从连通图的任何一个顶点出发进行遍历 遍历过程中经过的边加上图的所有顶点构成的子图称为图的生成树 深度优先生成树 由深度优先搜索得到的生成树 简称为DFS生成树 广度优先生成树 由广度优先搜索得到的生成树 简称为BFS生成树 在对无向图进行遍历时 对于连通图 仅需从图中任一顶点出发 进行深度优先搜索或广度优先搜索 便可访问到图中所有顶点 对非连通图 则需从多个顶点出发进行搜索 而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集    lishixinzhi/Article/program/sjjg/201311/23607

两种遍历顺序要结合着分析，才能画出这颗树的图
比如，层次遍历，先访问到A节点，说明A是树的根节点
那么在中序遍历结果里看：
DBGEHJ在A前面，说明这些节点，都在A左子树上
CIF在A的后面，说这些节点，都在A的右子树上
那么，树可以先这样画：
__________A________
________/____\_____
_____DBGEHJ__CIF___
再看层次遍历，A后面是B，说明B是A左子树的根节点
从上图中的先序遍历顺序DBGEHJ中看到：
D在B的前面，说明D在B的左子树上
GEHJ在B的后面，说明它们在B的右子树上
那么，树又可以画成：
_________A________
_______/____\_____
_____B________CIF__
____/__\____________
___D__GEHJ_________
如此循环，直到将整个树都画完全
结果如下：
_____________A_______________
___________/____\_____________
________B_________C__________
______/___\_________\_________
_____D_____E_________F_______
__________/__\_________\______
_________G____H_________I____
_______________\______________
_________________J____________

typedef struct tagTree
{
int data;
struct tagTree child,sibling;
}TreeNode,Tree;
#define MALLOCNODE(p,pointertype) do{\
p=(pointertype)malloc(sizeof(p));memset(p,0,sizeof p);}while(0)
void TransformTree(CTBox orgtree[],int nodeNum,int root,Tree parentNode)
{//ASSERT(orgtree != NULL && root<nodeNum&&parentNode !=NULL)
ChildPtr pchildlist = orgtree[root]firstchild;
Tree p,head,prev;
if(pchildlist!=NULL)
{//创建兄弟链表头结点
prev = head = (Tree)malloc(sizeof(head));
memset(head,0,sizeof head);//ASSERT(head !=NULL)
head->data = orgtree[pchildlist->child]data;
parentNode->child = head;
pchildlist = pchildlist->next;
}
while(pchildlist != NULL)
{//递归构建子树
MALLOCNODE(p,Tree);//ASSERT(p!=NULL)
p->data = orgtree[pchildlist->child]data;
prev->sibling = p;
prev = p;
TransformTree(orgtree,nodeNum,pchildlist->child,p);
pchildlist = pchildlist->next;
}
////////
}
Tree CreateTree(CTBox orgtree[],int nodeNum,int root)
{
Tree head;
if(root<0 || root>=nodeNum) return NULL;//空树
MALLOCNODE(head,Tree);//创建根
if(head==NULL) return NULL;
head->data = orgtree[root]data;
TransformTree(orgtree,nodeNum,root,head);//转换子树
return head;
}

---