数据结构C语言实现系列[8]——树

转载数据结构C语言实现系列[8]——树

#include <stdio.h>
#include <stdlib.h>
#define kk 3        /* 定义树的度 */
#define MS 10        /* 定义在建立树的存储结构时的栈空间大小 */
#define MQ 10        /* 定义在树的按层遍历算法中的队列空间大小 */
typedef char elemType;

/************************************************************************/
/*                   　　  以下是关于树操作的4个简单算法                 */
/************************************************************************/
struct GTreeNode{
    elemType data;
    struct GTreeNode *t[kk];
    struct GTreeNode *parent;
};
/* 建立树的存储结构 */
void createGTree(struct GTreeNode* *gt, char *a)
{
    struct GTreeNode *s[MS];    /* 数组s作为存储树中结点指针的栈使用 */
    int d[MS];  /* 数组d作为存储孩子结点链接到双亲结点指针域的序号栈使用 */
    int top = -1;    /* top作为两个栈的栈顶指针，初值为-1表示栈空 */
    struct GTreeNode *p;        /* 定义p为指向树结点的指针 */
    int i = 0, j;        /* i指示扫描字符串a中的当前字符位置 */
    *gt = NULL;        /* 初始将树根指针置空 */

    while(a[i] != 'o'){/* 每次循环处理一个字符，直到字符串结束为止 */
        switch(a[i]){
            /* 对空格不作处理 */
            case ' ':
                break;
            /* 处理左括号时，让p指针进s栈，０进d栈，表明待扫描的孩子
            结点将被链接到s栈顶元素所指结点的第一个指针域*/
            case '(':
                top++;
                s[top] = p;
                d[top] = 0;
                break;
            /* 处理右括号时，让s和d退栈 */
            case ')':
                top--;
                break;
        /* 处理逗号时，让待读入的孩子的结点链接到s栈顶元素所指结点
               的下一个指针域*/
            case ',':
                d[top]++;
                break;
            /* 此处处理的必然是字符元素 */
            default:
                /* 根据a[i]字符生成新结点 */
                p = malloc(sizeof(struct GTreeNode));
                p->data = a[i];
                for(j = 0; j < kk; j++){/* 用kk表示树的深度k */
                    p->t[j] = NULL;
                }
                if(NULL == *gt  ){
                    *gt = p;        /* 使结点p成为树根 */
                }else{
                    s[top]->t[d[top]] = p;/* 链接到双亲结点对应
                    的指针域 */
                }
                break;
        }
        i++;        /* 准备处理下一个字符 */
    }
    return;
}

/* 2.树的遍历 */
/* 先根 */
void preRoot(struct GTreeNode *gt)
{
    int i;
    if(gt != NULL){
        printf("%c ", gt->data);    /* 访问根结点 */
        for(i = 0; i < kk; i++){
            preRoot(gt->t[i]);        /* 递归遍历每一棵子树 */
        }
    }
    return;
}

/* 后根 */
void postRoot(struct GTreeNode *gt)
{
    int i;
    if(gt != NULL){
        for(i = 0; i < kk; i++){
            postRoot(gt->t[i]);        /* 递归遍历每一棵子树 */
        }
        printf("%c ", gt->data);    /* 访问根结点 */
    }

}

/* 按层 */
void levelOrder(struct GTreeNode *gt)
{
    struct GTreeNode *p;
    int i;
    struct GTreeNode *q[MQ];    /* 队列用的数组q，存放根结点 */
    int front = 0, rear = 0;
    /* 将整棵树的树根指针入队 */
    if(gt != NULL){
        rear = (rear + 1 % MQ);
        q[rear] = gt;
    }
    /* 当队列非空时执行循环 */
    while(front != rear){
        front = (front + 1) % MQ;        /*  */
        /* 删除队首元素，输出队首元素所指结点的值 */
        p = q[front];
        printf("%c ", p->data);
        /* 非空的孩子结点的指针依次进队 */
        for(i = 0; i < kk; i++){
            if(p->t[i] != NULL){
                rear = (rear + 1) % MQ;
                q[rear] = p->t[i];
            }
        }
    }
    return;
}

/* 3.从树中查找结点 */
elemType *findGTree(struct GTreeNode *gt, elemType x)
{
    /* 若树空则返回NULL */
    if(gt == NULL){
        return NULL;
    }else{
        elemType *p;
        int i;
        /* 若查找成功返回结点值域的地址 */
        if(gt->data == x){
            return &(gt->data);
        }
        /* 向每棵子树继续查找，返回得到的值域地址 */
        for(i = 0; i < kk; i++){
            if(p = findGTree(gt->t[i], x)){
                return p;
            }
        }
        return NULL;        /* 查找不成功返回NULL */
    }
}

/* 树的输出 */
void printGTree(struct GTreeNode *gt)
{
    if(gt != NULL){
        int i;
        printf("%c", gt->data);
        /* 判断gt结点是否有孩子 */
        for(i = 0; i < kk; i++){
            if(gt->t[i] != NULL){
                break;
            }
        }
        /* 有孩子时才执行条件语句体的向下递归调用 */
        if(i < kk){
            printf("(");
            printGTree(gt->t[0]);        /* 输出第一棵子树 */
            /* 输出其余各个子树 */
            for(i = 1; i < kk; i++){
                printf(",");
                printGTree(gt->t[i]);
            }
            printf(")");
        }
    }
    return;
}

/* 5.求树的深度 */
int depthGTree(struct GTreeNode *gt)
{
    int i, max;
    /* 空树的深度为0 */
    if(gt == NULL){
        return 0;
    }
    /* 求非空树的深度，max的初值为0 */
    max = 0;
    for(i = 0; i < kk; i++){
        int d = depthGTree(gt->t[i]);/* 计算出一棵子树的深度并赋值给d */
        if(d > max){
            max = d;
        }
    }
    return max + 1;        /* 返回非空树的深度，它等于各子树的最大深度加1 */
}

/* 6.清除树中的所有结点，使之成为一棵空树 */
void clearGTree(struct GTreeNode* *gt)
{
    if(*gt != NULL){
        int i;
        for(i = 0; i < kk; i++){
            clearGTree(&((*gt)->t[i]));
        }
        free(*gt);
        *gt = NULL;
    }
    return;
}



/************************************************************************/

int main(int argc, char *argv[])
{
    char ch;
    struct GTreeNode *gt = NULL;
    char b[50];        /* 用于存入k叉树广义表的字符数组 */
    printf("输入一棵%d叉树的广义表字符串： ", kk);
    scanf("%s", b);
    createGTree(&gt, b);
    printf("先根遍历：");
    preRoot(gt);
    printf(" ");
    printf("后根遍历：");
    postRoot(gt);
    printf(" ");
    printf("按层遍历：");
    levelOrder(gt);
    printf(" ");
    printf("按广义表的形式输出：");
    printGTree(gt);
    printf(" ");
    printf("树的深度为：%d ", depthGTree(gt));
    printf("输入待查找的字符：");
    scanf(" %c", &ch);
    if(findGTree(gt, ch)){
        printf("查找成功！ ");
    }else{
        printf("查找失败！ ");
    }
    clearGTree(&gt);
    return 0;
}