【C语言】【数据结构】菜鸟学习日志（四） 用二叉树实现非递归排序

标签：des   get   int   文件   数据   c   

　　唉，由于要备战考研，这篇博文可能是我这一年最后一次更新啦！

　　其实断断续续的也没有写很多，而且大多都是很初级、很简单的东西，没有和大家分享什么高阶的东西。这也正应了我们《菜鸟学习日志》的标题嘛！

　　不过说回来我还是很喜欢写博文的。一方面总结学到的知识，以后也可以自己看看别做了就忘了；另一方面，写博文也让我在学习的过程中更加认真，以免分享了错误的知识。

　　写的东西好不好呢是一说，好像有一些点击量，不过看的人估计也不多。只是我还算乐在其中吧！

　　大学生活说到底过得有点浪了，导致我苦逼地走向了考研的不归路……

　　这次分享的博文也没什么高深的东西。今年和我一起选修了C语言的同学一看就明白为什么我要写这个了~

　　反正很简单，我也不多解释了了，直接上代码。代码中已经给出了详细的注释，全是干货。

　　这个代码算是写的比较健壮一些了，如果你觉得太麻烦也可以精简掉一些部分。

　　另外，如果有什么不明白或者可以改进的地方，都可以给我留言！

　　更多的博文，我们明年见吧！：）

-------------------------------------------

/*
binary_tree.c
将给定文件中的数据按照中序由小到大的顺序在二叉树中排序，再写入到文件中
这个程序采用非递归的算法（老师要求）
假设源文件和目标文件是两个不同的文件
假设文件中的数据为整型数
假设数据之间用空格符隔开
假设没有重复的数据
*/
#include
#include
#define SFILE "/home/arcane/C_learning/binary_tree/num_1"    //源文件
#define OFILE "/home/arcane/C_learning/binary_tree/num_2"    //目标文件
#define MAXNODES 50                        //栈能存放的最大节点数

//定义了二叉树节点的结构体
struct node
{
    int data;
    struct node *plc;
    struct node *prc;
};
//用于遍历时存放节点的栈（数组）
struct node *nodes[MAXNODES];
//记录栈中节点的个数
int count = 0;
//用于创建节点
struct node *createNode(int data);
//根据值的大小在二叉树中插入节点
struct node *addNode(int value, struct node *pn);
//栈操作，压栈
int push(struct node *pn);
//栈操作，出栈
struct node *pop();

int main(void)
{
    FILE *fp;            //文件指针
    struct node *proot = NULL;    //指向根节点的指针
    struct node *pn;        //指向任意节点的指针
    struct node *p;            //用于辅助释放分配的空间
    char ch;            //记录从文件中读取的字符
    int num = 0;            //计算和记录从文件中读出的数字
    char s[10];            //用于将num转换为字符串
    int k=0;

    //把数据按顺序读入二叉树
    //打开文件
    if((fp = fopen(SFILE, "r")) == NULL)
    {
        printf("文件打开失败！\n");
        exit(1);
    }
    //读取数字并建立二叉树
    while ((ch = getc(fp)) != EOF)
    {
        if (ch == ‘ ‘)
        {
            if (proot == NULL)
                proot = createNode(num);
            else
                addNode(num,proot);
                
            num = 0;
        }
        else
            num = num * 10 + (ch - ‘0‘);    //字符是一个一个读入的，这里计算了被空格隔开的单个数字
    }
    //关闭文件
    fclose(fp);              

    //将二叉树按中序写入文件,顺便释放给树分配的空间
    //打开目标文件
    if((fp = fopen(OFILE, "w")) == NULL)
    {
        printf("文件打开失败！\n");
        exit(1);
    }

    //用循环而非递归的中序遍历，其中用到了栈
    pn = proot;
    while(1)
    {
        if(pn->plc != NULL)        //左子树存在
        {
            if(push(pn) == 1)
            {
                printf("栈溢出！\n");
                exit(1);
            }
            pn = pn->plc;
        }
        else                //左子树不存在
        {
            //把节点的值转换成字符串，并写入文件中
            sprintf(s, "%d", pn->data);
            fputs(s,fp);
                    
            
            if(pn->prc != NULL)    //右子树存在
            {
                putc(‘ ‘, fp);
                p = pn;        //中序遍历，当开始考虑右子树前，这个节点的信息已经写入文件了，所以可以释放了
                pn = pn->prc;
                free(p);
                k++;
            }
            else            //右子树不存在
            {
                free(pn);    //左右子树都不存在，这个节点可以释放了
                k++;
                if((pn = pop()) != NULL)
                {
                    putc(‘ ‘, fp);
                    pn->plc = NULL;
                }
                else
                    break;
            }
        }
    }
    //关闭目标文件
    fclose(fp);

    return 0;
}

/*
创建一个节点
其值为 value，左右节点为 NULL
*/
struct node *createNode(int value)
{
    struct node *pn = (struct node *)malloc(sizeof(struct node));
    pn->data = value;
    pn->plc = pn->prc = NULL;

    return pn;
}

/*
向给定的二叉树中插入一个值为 value 的节点
规则是按中序由小到大的顺序
*/
struct node *addNode(int value, struct node *pn)
{
    struct node *p = pn;

    //利用循环而非递归的插入
    while(1)
    {
        if(p == NULL)        //二叉树不存在
            return createNode(value);

        if(value data)    //属于二叉树的左子树
        {
            if(p->plc == NULL)
            {
                p->plc = createNode(value);
                return p->plc;
            }
            else
            {
                p = p->plc;
            }
        }
        else            //属于二叉树的右子树
        {
            if(p->prc == NULL)
            {
                p->prc = createNode(value);
                return p->prc;
            }
            else
            {
                p = p->prc;
            }
        }
    }
}

/*
压栈操作
成功返回0,失败返回1
*/
int push(struct node *pn)
{
    if(count == (MAXNODES - 1))
        return 1;

    nodes[count] = pn;
    count++;
    return 0;
}

/*
出栈操作
成功返回节点指针，失败返回NULL
*/
struct node *pop()
{
    if(count > 0)
        return nodes[--count];

    return NULL;
}

【C语言】【数据结构】菜鸟学习日志（四） 用二叉树实现非递归排序,搜素材,soscw.com

【C语言】【数据结构】菜鸟学习日志（四） 用二叉树实现非递归排序

标签：des   get   int   文件   数据   c   

原文地址：http://www.cnblogs.com/arcane/p/3704447.html