题目描述

【说明】

一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如，题图(a)所示的树的孩子-兄弟表示如题图(b)所示。

函数LevelTraverse()的功能是对给定树进行层序遍历。例如，对题图所示的树进行层序遍历时，节点的访问次序为：D B A E F P C。 对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如下表所示。

函数原型	说明
void InitQueue(Queue *Q)	初始化队列
Bool IsEmpty(Queue Q)	判断队列是否为空，若是则返回TRUE，否则返回FALSE
void EnQueue(Queue *Q,TreeNode p)	元素入队
void DeQueue(Queue *Q,TreeNode *p)	元素出队

Bool、Status类型定义如下：

typedef enum {
    FALSE = 0,TRUE = 1
} Bool;
typedef enum {
    OVERFLOW = -2,
    UNDERFLOW = -1,
    ERROR = 0,
    OK = 1
} Status;

树的二叉链表定义如下：

typedef struct Node {
    char data;
    struct Node *firstchild,*nextbrother;
}Node,*TreeNode;

【函数】

Status LevelTraverse(TreeNode root){
    /*层序遍历树，树采用孩子-兄弟表示法，root是树根节点的指针*/
    Queue tempQ;
    TreeNode ptr,brotherptr;
    if(!root){
        return ERROR;
    }
    (1);
    brotherptr = root -> nextbrother;
    while(brotherptr){
        EnQueue(&tempQ,brotherptr);
        (2);
    }/*end-while*/
    while((3)){
        (4);
        printf("%c\t",ptr->data);
        if((5)) continue;
        (6);
        brotherptr=ptr->firstchild->nextbrother;
        while(brotherptr){
            EnQueue(&tempQ,brotherptr);
            (7);
        }/*end-while*/
    }/*end-while*/
    return OK;
}

分析

起初我看到这道题其实还是很蒙的，当时愣是没看明白是怎么回事，就放到了现在，又翻开看看，仔细读了一遍题意，原来我先开始都没明白这个函数是干什么的。

也就是，现在有一棵树，这个数是多少叉的不知道，已经用用孩子-兄弟法存储好了，也就是图(b)的那个二叉树，要模拟在原树图(a)上进行层序遍历，LevelTraverse()函数的作用就是这个。

首先来看这两个图，任意叉树转换孩子-兄弟法的规则是什么？这个要先搞明白。结合两个图，发现了这样的规则：对于一个节点来说，它的左节点是他的孩子，它的右节点是它的兄弟，一个兄弟就是在一层上，那么只要找到这个节点的第一个孩子节点，就能够找到这个孩子节点的所有兄弟，这一层次就算遍历完了，每个兄弟也有可能有孩子，将兄弟的孩子遍历完，就是下一层次，直到遍历所有节点。

这其实就是一个队列结构，有很强的先后关系，只有通过根节点才能找到它的所有孩子，输出，并将这些孩子保存到一个队列中，即这一层次遍历完，将这些孩子保存到一个队列中，孩子再找孩子，按照这个规则，入队出队，就行了，队列为空也就证明遍历完了。

【答案】

(1):EnQueue(&tempQ,root);
/*这里函数传来了根节点，根节点入队，参数需要指针形式，传入地址即可*/
(2):brotherptr=brotherptr->nextbrother;
/*寻找该节点的所有兄弟*/
(3):!IsEmpty(tempQ)
/*当队列为空的时候则证明所有节点遍历完*/
(4):DeQueue(&tempQ,&ptr);
/*该行下面是一个输出语句，很明显上面要进行出队*/
(5):!ptr->firstchild
/*这里要屏蔽掉没有孩子的节点*/
(6):EnQueue(&tempQ,ptr->firstchild)
/*孩子节点入队*/
(7):brotherptr=brotherptr->nextbrother;
/*和(2)一样，都是遍历兄弟节点，然后执行入队操作*/

开始的时候，还是没有好好读清楚题意，没搞清楚规则，函数的作用，现在分析一遍，又清晰了一些，以后做题要注意一些这些毛病。