C语言实现二叉树-03版

来源:网页教学基地 时间:2017-01-11 09:02:42  浏览次数:0

我们亲爱的项目经理真是有创意,他说你给我写得二叉树挺好的;

功能还算可以:插入节点,能够删除节点;

可是有时候我们只是需要查找树的某个节点是否存在;

所以我希望你能够给我一个find功能;

还有就是,我在跟BOSS交流的时候,他根本不相信你已经把链表写成树的结构啦;

他希望你能够更明显的把树的结构打印出来;

所以,你需要实现一个show功能;

这应该不难吧;

Problem

我们需要实现的其实是遍历的两个变体;

首先确定我们的思路,想到都是需要遍历的;

那么我们是不是又想到了有递归的方式和非递归的方式呢;

int find_recursive(Node *root, int data)
{
    //TODO
}

我们首先实现的是递归的,大致的结构应该是这样的;

还记得吗?递归的前面几行一般是递归的结束条件;

因此,我们的代码应该是这样的:

int find_recursive(Node *root, int data)
{
    if(root == NULL)
        return 0;
}

其次,我们应当考虑找到目标的时候,应该是怎么确定的呢?

应该是root->data 与参数data相等的时候,我们希望程序返回啦;

因此,我们需要的代码可能会是这样的;

int find_recursive(Node *root, int data)
{
    if(root == NULL){
        return 0;
    }else if(root->data == data){
        return 1;
    }
}

那,在当前的节点上如果没有找到目标呢;

我们需要的应该是确定往左找还是往右找;

所以需要把代码写成如下的形式;

int find_recursive(Node *root, int data)
{
    if(root == NULL){
        return 0;
    }else if(root->data == data){
        return 1;
    }else{
        int dir = root->data < data;
        return find_recursive(root->link[dir],data);
    }
}

dir的值只能是0或者1,代表的意义是什么大家应该很清楚啦;

它的作用是什么也应该很清楚啦;

最后执行递归;

通常我们需要客户操作的是树,因此我们需要一个包装函数;

int find(Tree *tree,int data)
{
    return find_recursive(tree->root,data);
}

好啦,我们可以测试一下啦;

我首先把需要用到得代码附上;

 

#include <stdio.h>
#include <stdlib.h> #include <time.h> typedef struct _node { int data; struct _node *link[2]; }Node; typedef struct _tree{ struct _node *root; }Tree; Tree * init_tree() { Tree *temp = (Tree*)malloc(sizeof(Tree)); temp->root = NULL; return temp; } Node * make_node(int data) { Node *temp = (Node*)malloc(sizeof(Node)); temp->link[0] = temp->link[1] = NULL; temp->data = data; return temp; } int insert(Tree *tree, int data) { if(tree->root == NULL){ tree->root = make_node(data); }else{ Node * it = tree->root; int dir ; for(;;){ dir = it->data < data; if(it->data == data){ return 0; }else if(it->link[dir] == NULL){ break; } it = it->link[dir]; } it->link[dir] = make_node(data); } return 1; }

测试主函数代码如下:

int main(void)
{
    Tree * tree = init_tree();
    insert(tree,6);
    insert(tree,7);
    insert(tree,5);
    insert(tree,8);
    printf("looking for %d...%s\n",6,find(tree,6) ? "Got it":"Not exist");
    printf("looking for %d...%s\n",9,find(tree,9) ? "Got it":"Not exist");
    return 0;
}

运行结果如下:

\

好啦!可能对于客户来说,这样把查询的数据写死啦,并把那么好;

别人可能想查某个数据就输入某个数据,可能更实用;

这是非常简单的功能,我不会去讲解,但是也附上一份简单的实现;

大家写的肯的能够更加漂亮;

void tips(){
    time_t curTime;
    struct tm *ts;
    time_t testTime = time(&curTime);
    ts = localtime(&curTime);
    //struct tm *tsgm = gmtime(&curTime);
    puts("*************************************************************");
    printf("Date:%s",asctime(ts));
    puts("Please input right cmd");
    puts("1)Search");
    puts("2)Quit");
    puts("*************************************************************");
}

int search(Tree *tree)
{
    char cmd;
    int isExist;
    int target;
    tips();
    while((cmd=getchar())!=EOF){
        if(cmd=='1'){
            puts("-------------------------------------------------------------");
            printf("Please input the target:");
            scanf("%d",&target);
            isExist=find(tree,target);
            if(isExist){
                 printf("Target %d is exists \n",target);
            puts("-------------------------------------------------------------");
                 puts("\n");
                 continue;
                //break;
            }else{
                 puts("Target Not exitst");
            puts("-------------------------------------------------------------");
                 puts("\n");
                 continue;
                //break;
            }
        }else if(cmd=='2'){
            puts("bye~");
            break;
        }else{
        tips();
        }
    }
    return 1;
}

运行结果如下:

\

这个可能用户体验要较好些;

注意别忘记包涵头文件time.h

好啦查询工作算是完成啦;

接下来是下一个任务;

Problem

 为啦更加形象的表明我们一直在写得是一棵树;

我想有必要show也就是秀秀我们的成果啦;

这次咱们先看要实现的效果,如下图;

\

我们的树根就是8,而~符合代表就是叶子啦;

这样旋转90°的树可能你不一定喜欢;

但是,如果你想再旋转90度的话你就自己想想吧;

好啦,接下来就是实现啦;

不管它咱们显示,咱们始终记住,我们需要遍历;

为简单,我们使用递归实现;

void structure_recursive(Node *root,int level)
{
    if(root == NULL){
        //TODO
    }else{
        //TODO;
    }
}

这个遍历方式结构就怎么简单;

但是请思考思考,我们的输出到终端上得数据是先大的,然后是小的;

显然是只有中序遍历才能得到按正确的大小顺序输出;

所以我们需要记住这点哈;

void structure_recursive(Node *root,int level)
{
    if(root == NULL){
        //TODO
    }else{
        structure_recursive(root->link[1],level + 1);
        printf("%d\n",root->data);
        structure_recursive(root->link[0],level + 1);
    }
}

你会发现,我首先写else部分,仔细看看else部分你会发现我们的中序遍历很明显啦;

可是呢!!它又有别于我们前面写得中序遍历方式,我们首先从右子树下手啦;

以前都是从左子树的,这就是为什么我们输出的结果是从大到小往下的啦;

好啦!TODO到底应该写成什么样子呢?

想想要是我们一直递归到最后要是递归一次我们就得增加一个level的计数;

到最后发现叶子是NULL我们就直接输出level个tab然后跟一个~表示叶子;

所以代码如下:

void structure_recursive(Node *root,int level)
{
   int i;
if(root == NULL){ for(i = 0;i<level;i++){ putchar('\t'); } puts("~"); }else{ structure_recursive(root->link[1],level + 1); printf("%d\n",root->data); structure_recursive(root->link[0],level + 1); } }

这里已经差不多完事啦,但是我们先去写一个包装函数;

void structure(Tree *tree)
{
    structure_recursive(tree->root,0);
}

注意包装函数里面的0表示是从最左边开始打印的;

我们先不去完善我们的structure_recursive函数,我们直接测试,看看结果;

\

 

这个可不是我们想看到的结果哈;

原因是什么呢;

我们还没有完善我们的函数呢;

void structure_recursive(Node *root,int level)
{
    int i;
    if(root == NULL){
        for(i = 0;i<level;i++){
            putchar('\t');
        }   
        puts("~");
    }else{
        structure_recursive(root->link[1],level + 1); 
        for(i = 0;i < level;i++){
            putchar('\t');
        }   
        printf("%d\n",root->data);
        structure_recursive(root->link[0],level + 1); 
    }   
}

好啦,我们的效果出来啦;

\

好啦!工作完成啦;

总结一下吧;

不,还没有到总结的时候;

明天的任务还有呢:

我们的树不能一直老想着用递归实现,在很多时候它是受限制的;

递归对空间要求特别多,所以我们下次想想有没有非递归的方法实现其他的函数;

最后附上我们今天所有代码吧:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct _node {
    int data;
    struct _node *link[2];
}Node;

typedef struct _tree{
    struct _node *root;
}Tree;

Tree * init_tree()
{
    Tree *temp = (Tree*)malloc(sizeof(Tree));
    temp->root = NULL;
    return temp;
}

Node * make_node(int data)
{
    Node *temp = (Node*)malloc(sizeof(Node));
    temp->link[0] = temp->link[1] = NULL;
    temp->data = data;
    return temp;
}

int insert(Tree *tree, int data)
{
    if(tree->root == NULL){
        tree->root = make_node(data);
    }else{
        Node * it = tree->root;
        int dir ;
        for(;;){
            dir = it->data < data;
            if(it->data == data){
                return 0;
            }else if(it->link[dir] == NULL){
                break;
            }
            it = it->link[dir];
        }
        it->link[dir] = make_node(data);
    }
    return 1;
}
int remove_node(Tree *tree, int data)
{
    if(tree->root != NULL)
    {
        Node *p = NULL;
        Node *succ;
        Node *it = tree->root;
        int dir;
        for(;;){
            if( it == NULL){
                return 0;
            }else if(it->data == data){
                break;
            }
            dir = it->data < data;
            p = it;
            it = it->link[dir];
        }
/***********************************************************************/

        if(it->link[0] != NULL && it->link[1] != NULL){
            p = it;
            succ = it->link[1];
            while(succ->link[0] != NULL){
                p = succ;
                succ = succ->link[0];
            }
            it->data = succ->data;
            p->link[p->link[1] == succ] = succ->link[1];
            free(succ);
/***********************************************************************/
        }else{  /*it->link[0] == NULL || it->link[1] == NULL */
            dir = it->link[0] == NULL;
            if( p == NULL){
                tree->root = it->link[dir];
            }else{
                p->link[p->link[1] == it] = it->link[dir];
            }
            free(it);
        }
    }

    return 1;
}
int find_recursive(Node *root, int data)
{
    if(root == NULL){
        return 0;
    }else if(root->data == data){
        return 1;
    }else{
        int dir = root->data < data;
        return find_recursive(root->link[dir],data);
    }
}

int find(Tree *tree,int data)
{
    return find_recursive(tree->root,data);
}

void tips(){
    time_t curTime;
    struct tm *ts;
    time_t testTime = time(&curTime);
    ts = localtime(&curTime);
    //struct tm *tsgm = gmtime(&curTime);
    puts("*************************************************************");
    printf("Date:%s",asctime(ts));
    puts("Please input right cmd");
    puts("1)Search");
    puts("2)Quit");
    puts("*************************************************************");
}
int search(Tree *tree)
{
    char cmd;
    int isExist;
    int target;
    tips();
    while((cmd=getchar())!=EOF){
        if(cmd=='1'){
            puts("-------------------------------------------------------------");
            printf("Please input the target:");
            scanf("%d",&target);
            isExist=find(tree,target);
            if(isExist){
                 printf("Target %d is exists \n",target);
            puts("-------------------------------------------------------------");
                 puts("\n");
                 continue;
                //break;
            }else{
                 puts("Target Not exitst");
            puts("-------------------------------------------------------------");
                 puts("\n");
                 continue;
                //break;
            }
        }else if(cmd=='2'){
            puts("bye~");
            break;
        }else{
        tips();
        }
    }
    return 1;
}

void structure_recursive(Node *root,int level)
{
    int i;
    if(root == NULL){
        for(i = 0;i<level;i++){
            putchar('\t');
        }
        puts("~");
    }else{
        structure_recursive(root->link[1],level + 1);
        for(i = 0;i < level;i++){
            putchar('\t');
        }
        printf("%d\n",root->data);
        structure_recursive(root->link[0],level + 1);
    }
}

void structure_recursive(Node *root,int level)
{
    int i;
    if(root == NULL){
        for(i = 0;i<level;i++){
            putchar('\t');
        }
        puts("~");
    }else{
        structure_recursive(root->link[1],level + 1);
        for(i = 0;i < level;i++){
            putchar('\t');
        }
        printf("%d\n",root->data);
        structure_recursive(root->link[0],level + 1);
    }
}

void structure(Tree *tree)
{
    structure_recursive(tree->root,0);
}

int main(void)
{
    Tree * tree = init_tree();
    insert(tree,8);
    insert(tree,10);
    insert(tree,11);
    insert(tree,6);
    insert(tree,7);
    insert(tree,5);
    structure(tree);
    return 0;
}

 

最近相关