我们亲爱的项目经理真是有创意，他说你给我写得二叉树挺好的；
功能还算可以：插入节点，能够删除节点；
可是有时候我们只是需要查找树的某个节点是否存在；
所以我希望你能够给我一个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 ",6,find(tree,6) ? "Got it":"Not exist"); printf("looking for %d...%s ",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 ",target); puts("-------------------------------------------------------------"); puts(" "); continue; //break; }else{ puts("Target Not exitst"); puts("-------------------------------------------------------------"); puts(" "); 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 ",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(' '); } puts("~"); }else{ structure_recursive(root->link[1],level + 1); printf("%d ",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(' '); } puts("~"); }else{ structure_recursive(root->link[1],level + 1); for(i = 0;i < level;i++){ putchar(' '); } printf("%d ",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 ",target); puts("-------------------------------------------------------------"); puts(" "); continue; //break; }else{ puts("Target Not exitst"); puts("-------------------------------------------------------------"); puts(" "); 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(' '); } puts("~"); }else{ structure_recursive(root->link[1],level + 1); for(i = 0;i < level;i++){ putchar(' '); } printf("%d ",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(' '); } puts("~"); }else{ structure_recursive(root->link[1],level + 1); for(i = 0;i < level;i++){ putchar(' '); } printf("%d ",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; }