C语言实现二叉树-04版

二叉树，通常应当是研究其他一些复杂的数据结构的基础。因此，通常我们应该精通它，而不是了解；当然，可能并不是每个人都认同这种观点，甚至有些人认为理解数据结构就行了！根本没有必要去研究如何实现，因为大多数高级语言已经包含了非常好用的实现接口，直接调用即可。我曾经很难理解为什么有些同学那么的努力去学习算法，然后参加ACM比赛，我甚至连最基本的斐波那契也无法实现。但是我任然心里嘲笑他们，因为我当时正在学习Linux系统编程。我觉得自己做的才是正确的有意义的事。其实，现在我觉得算法是一个程序员的基本素质高低的体现；

好啦！扯远啦，继续我们的二叉树04版本；

我很想在这个版本就终结了，但是二叉树实在太多内容啦；

故事是这样开始的：

项目经理说，你看你上次写的二叉树展示的功能很形象嘛！

我都不用在过多解释，BOSS就看出来是树的结构啦；

所以，我们都很相信你接下来的任务也会完成的很好的；

Task

1，我们需要一个销毁整棵树的功能；

2，我们需要三种常见的遍历方式；

3，我们还需要一种叫做水平遍历的功能；

4，我们需要你给我讲讲如何对树进行旋转；

Problem

树的销毁，是对每一个节点的释放；

因此，我们需要遍历每一个节点；

但是和查找遍历不同，我们会删除掉节点，因此我们一定要想清楚先释放哪个；

一定不要“打草惊蛇”让其他节点跑啦；

Solution

理解的结构才能很好的销毁它，先看看下面的图吧；

我们显然不应该先删除3节点；

我们应该是先删除叶子节点；

所以我们可以使用一种叫做后序遍历的方式解决；

我们要删除的是这样一颗树，我们都知道，树的操作一般都可以用递归解决；

因此，首先思考递归怎么解决吧；

void destroy_recursive(Node *root)
{
    if(root != NULL){
        //TODO
    }
} 

我们知道，只有这个节点不为空，才能够说对其进行销毁；

所以，首先要习惯判空，然后进行下一步；

void destroy_recursive(Node *root)
{
    if(root != NULL){
        free(root);
    }
} 

这样写，或许这是你的第一想法。但是想想，对那棵树而言你只是把树的根砍啦；

你没有上树去摘果子，这就照成浪费啦（大量的内存泄露）；

void destroy_recursive(Node *root)
{
    if(root != NULL){
        destroy_recursive(root->link[0]);
        destroy_recursive(root->link[1]);
        free(root);
    }  
}

这样做得话，你就顺利的从树根到树顶，把所有的果子摘下来后；

还把上面的树枝砍啦，一直到当年下到地面上得时候把根也抛啦；

任务就完成啦；

但是，你的函数由于是一个递归的裸函数，所以你需要把它包装一下；

void destroy(Tree *tree)
{  
    destroy_recursive(tree->root);
}

这个函数我们待会在测试吧，就好比刚发明的炸弹最后等我们研究透再点火；

不然炸了我们都不知道怎么再造；

Problem

刚才，我们已经使用过递归遍历啦；

显然递归解决树的问题真是手到擒来；

对于三种常见的遍历也是非常简单的，而且是非常相似的；

void preorder_recursive(Node *root)
{  
    if(root != NULL){
        printf("%d\n",root->data);
        preorder_recursive(root->link[0]);
        preorder_recursive(root->link[1]);
    }
}  
   
void preorder(Tree *tree)
{  
    preorder_recursive(tree->root);
}

上面是前序遍历，如果你已经知道中序和后序怎么写，你最好暂时不要往下看啦；

中序遍历：

void inorder_recursive(Node *root)
{      
    if(root != NULL){
        inorder_recursive(root->link[0]);
        printf("%d\n",root->data);
        inorder_recursive(root->link[1]);
    }
}

void inorder(Tree *tree)
{
    inorder_recursive(tree->root);
}

后序遍历：

void postorder_recursive(Node *root)
{
    if(root != NULL){
        postorder_recursive(root->link[0]);
        postorder_recursive(root->link[1]);
        printf("%d\n",root->data);
    }
}

void postorder(Tree *tree)
{
    postorder_recursive(tree->root);
}

好啦任务又完成啦一个；

Problem

水平遍历就比较特殊啦，我们不能够使用递归解决啦；

void level_order(Tree *tree)
{
    Node *it = tree->root;
    Node *queue[10];
    int current = 0;
    int after_current = 0;
    if(it == NULL){
        return ;
    }   
    //TODO

}

首先解释一下我们的局部变量，这些变量是请来协助大家解决问题的；

自我介绍一下吧；

hey，我叫queue数组，我的类型是Node类型，因为我将存储Node类型的数据，我的功能是保存你当前访问到的节点；

hello，我叫current，的类型是基本类型，我主要负责记录当前在树的哪一个节点上；

wow，我叫after_current，我不好意思来晚啦。我的工作很简单，就是负责跟在current后面记录它走过的最新节点之前的一个；

我们再看看我们的实施方案吧，先把图再打开；

水平访问无法是

第一层，3

第二层，1，4

第三层，0，2

好啦，我们已经知道要实现的效果啦；

current你先和queue把当前的it记录一下；

我们的it待会可能要改变自己啦；

queue[current++]=it;

current说，我已经记录下来啦，并且我现在准备记录下一条信息，我现在已经是1“岁”啦；

void level_order(Tree *tree)
{
    Node *it = tree->root;
    Node *queue[10];
    int current = 0;
    int after_current = 0;
    if(it == NULL){
        return ;
    }
    
    queue[current++] = it;
    while(current != after_current){
        //TODO
    }
}

after_current很不耐烦的对while说，你到底要干什么，你难道非得让我和current比较吗？你明明知道他提前比我长了一岁；

while很亲切的说不用担心，你只要按照我的方式你会赶上它的；

void level_order(Tree *tree)
{
    Node *it = tree->root;
    Node *queue[10];
    int current = 0;
    int after_current = 0;
    if(it == NULL){
        return ;
    }

    queue[current++] = it;
    while(current != after_current){
        it = queue[after_current++];
        printf("%d\n",it->data);
        //TODO
    }             
} 

果然，after_current也长啦一岁；

此时，current不高兴啦，他头也不回的往前走啦；

抱歉，请您再看看这一份图，此时current应该走到哪呢？

它可以选择先从左边走也可以先从右边走；

假设先从左边吧；

void level_order(Tree *tree)
{
    Node *it = tree->root;
    Node *queue[10];
    int current = 0;
    int after_current = 0;
    if(it == NULL){
        return ;
    }

    queue[current++] = it;
    while(current != after_current){
        it = queue[after_current++];
        printf("%d\n",it->data);
        if(it->link[0] != NULL){
            queue[current++] = it->link[0];
        }
        //TODO
    }
}

好啦current开心的笑啦！它又比after_current大一岁啦；

while说小伙子不用骄傲，看看能不能继续往前走；

   while(current != after_current){
        it = queue[after_current++];
        printf("%d\n",it->data);
        if(it->link[0] != NULL){
            queue[current++] = it->link[0];
        }        
                 
        if(it->link[1] != NULL){
            queue[current++] = it->link[1];
        }
    }

不知不觉又长了一岁；现在current已经是2岁的小伙子；

哈哈，queue也很高兴自己现在保存啦三个数字啦；

queue == {3,1,4}

现在after_current不高兴啦，为什么它那么快就长了两岁啦；

while拍拍它肩膀说你不要着急，你继续走走看；

it = queue[after_current++];

哈哈，它很高兴，自己现在长了一岁啦；

it现在已经指向啦1号节点；

我们从图可以看到it的左右子树不为空，所以current将会连续又长两岁；

而将会是 queue == {3,1,4,0,2}

 此时，after_current也没有哭闹啦，它很快又遇见啦；

it = queue[after_current++];

而此时it是4，4没有左右孩子，所以我们的current不再增长；

current已经长大成人了不会再长啦；

而此时after_current还是慢慢成长；

直到current==after_current，while结束啦；

此时所有的数据已经遍历完成；

好啦！我们分析一下存在的问题，queue为什么指定为10呢,其实你只要大于等于4都能够运行。

但是，这是在我们已经知道节点只有那么一点，而不需要那么多的空间；

因此，这种硬编码在实际的应用会出现问题的，我们可能需要链表的方式来实现这个queue而不是固定数组；

好啦，这个先到这啦，下一个任务；

Problem

我们需要简单解释一下树的旋转；

这个其实很容易；

看看下面几幅图吧

好啦，这个是右旋一次的结果。更多东西下次再聊；

吃饭去啦；

Thanks:)