公告:本站提供编程开发方面的技术交流与分享,打造最佳教程网,希望能为您排忧解难!

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

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

更新时间:2013-03-16 22:50:55 |
#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栈,0进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;
}
最佳教程网

最大的技术交流平台 www.goodxyx.com© CopyRight 2011-2013, All Rights Reserved

浙ICP备11033019号