数据结构考研分类复习真题 第六章 答案 (五)[28]

[题目分析]此树看作度为的有序树先将根结点入队列当队列不空重复以下动作结点出队若结点有两个子女先将第二（右）子女入队列并转向第一子女若结点有一个子女则入队列如此下去直到碰到叶子结点或只有一个子女的结点再重复上述动作直至队列为空定义树结构如下

typedef struct node

{ElemType data; struct node *firstchild *secondchild; }*Tree;

void TreeTravers(Tree t) //按字母顺序输出树中各结点的值

{Tree pQ[]; //Q为队列元素是树结点指针容量是够大

if (t)

{QueueInit(Q); QueueIn(Qt); //根结点入队

while(!QueueEmpty(Q))

{p=QueueOut(Q); //出队

while (p>firstchild && p>secondchild) //当有双子女时

{QueueIn(Qp>secondchild);printf(p>data);//访问结点

p=p>firstchild;}// 沿第一子女向下

if (p>firstchild){printf(p>data); QueueIn(Qp>firstchild)} //一个子女树入队

if (!p>firstchild && !p>secondchild) printf(p>data);//访问叶子结点

}//while(!QueueEmpty(Q))

}//if

}//算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []