C-EASY-3：二叉树与递归

碎碎念：出这道题主要是为了引入一些基本的算法思想，在中等题中会用到递归的思想，所以在这道题中进行一个简单的引入。你可以使用AI进行辅助，但你至少要弄明白什么是递归，递归回到哪里，递归是怎样的一个过程。并初步认识c语言中的树。

1. 现在先了解什么是树，给树下一个定义。什么是二叉树？该如何定义一个二叉树？
2. 在这一题中我们只讨论二叉树。请你思考，二叉树在c语言中应该如何存储？二叉树有哪些特点？

聪明的你自然会发现，二叉树节点排列紧凑，几乎没有空间浪费，特别是完全二叉树。因此你可以使用顺序表来表示二叉树（即直接使用数组来表示一棵树）

先定义二叉树，为了方便，我们让根节点对应的数组下标为1，则左孩子为2，右孩子为3。根据数学归纳法，很容易找出根节点和对应孩子在树数组中下标对应的关系，根节点为i，左孩子为2i，右孩子为2i+1。

我们要定义树节点和树两个结构体。

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

#define MAX_TREE_SIZE 100
/*
 * 顺序存储二叉树结点
 * - data：结点数据
 * - used：当前位置是否有结点
 */
typedef struct {
    int data;
    bool used;
} SeqTreeNode;

/*
 * 顺序存储二叉树
 * - nodes：结点数组
 * - size：数组最大容量
 */
typedef struct {
    SeqTreeNode nodes[MAX_TREE_SIZE];
    int size;
} SeqBiTree;
/*

接下来请根据结构体定义，补全下面函数，将下面的函数和上方定义放在一个文件中，上传代码文件。并在md文件中写出你的思考过程。

1. void init_tree(SeqBiTree **tree*) 实现初始化二叉树函数，让二叉树的大小为MAX_TREE_SIZE，并将其全部节点设置为空，大小为0。
2. bool set_root(SeqBiTree **tree*, int *value*) 创建根节点，在节点数组1处设置根节点，函数需要传入根节点的data。
3. bool set_left_child(SeqBiTree **tree*, int *parent_node*, int *value*) 创建左孩子，parent_node为对应父节点下标。
4. bool set_right_child(SeqBiTree **tree*, int *parent_node*, int *value*) 创建右孩子。
5. void level_order(SeqBiTree **tree*) 实现层序遍历，按数组下标顺序打印整棵树，节点为空则打印-1，每打印完一层之后换行。
6. 实现以上函数之后，自己在主函数中定义一颗三层的二叉树，并进行层序遍历，看结果是否符合预期。

在第六步的过程中，你会发现，如果你设置很多空节点，那么会有很多的空间被浪费掉。即使顺序二叉树可以根据结点数组实现时间复杂度o(1)的快速查找，但其对于空节点很多的二叉树会浪费大量的空间，是用空间复杂度去换时间复杂度，这在工程中是不允许的。

当二叉树中存在较多空节点的时候，我们选择使用链表来存储二叉树的节点。

我们应该怎样定义二叉树的结构体呢？我们在链表中使用的链条是单向的，一个节点只存储指向下一个节点的指针。在二叉树当中，我们可以定义两个指针，一个指向左孩子一个指向右孩子，这样就可以通过父节点单向的向下传递，和链表类似。

链二叉树的缺点就是查找比较麻烦，需要一层一层向下找，要查找第n层的二叉树也要进行n次操作。

在了解完上面的基础知识以后，让我们来实现链二叉树的基本操作吧。请你新建一个代码文件，然后将这个代码块的内容粘到你的文件中，然后完成下面的题目。

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

typedef struct TreeNode {
    int data;                       // 节点存储的数据
    struct TreeNode *left;          // 左子树指针
    struct TreeNode *right;         // 右子树指针
} TreeNode;

请思考，我们在上一题当中是怎样创建一个链表的？

我们先创建一个节点，再让上一个节点指向这个新节点，这样就可以创建一个链条。在链二叉树中，我们也可以通过这样的操作来创建一棵树。

TreeNode* create_node(int value) 创建一个新的节点，新节点赋值为value，left和right指针都指向NULL。请你实现这个函数。

接下来，请你自己创建一棵树，形如：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

创建树的过程写在代码的主函数里。

完成树的创建以后，你会自然想到，该怎样验证这棵树是否创建正确。要想完成验证，最简单的办法就是打印这棵树。

请你思考，我们应该怎样打印一颗链二叉树呢？

聪明的你会发现，只使用简单的for循环无法实现这个打印函数。请你讲讲问什么无法实现。

为了实现对链二叉树的遍历，我们需要引入递归的思想。

递归就是：一个函数在执行过程中直接或间接调用它自己。

最简单的形式：

void f() {

​    f();  // 函数自己调用自己

}

但这样会无限调用，程序会崩溃。所以真正有用的递归必须有两个部分：

1. 递归条件：什么时候继续调用自己
2. 结束条件：什么时候停止调用自己

通过递归我们就可以实现对二叉树的遍历。

请你自行了解什么是二叉树的前序遍历，中序遍历，后序遍历。然后在上面的链二叉树代码文件中，实现这三个函数。并在主函数中调用这三个函数打印遍历结果。

请你思考上面递归的过程，讲讲为什么只改变printf函数出现的位置就可以实现这三种不同的递归。以前序遍历为例，讲讲二叉树中递归的过程。

相信初步了解递归以后，你一定会觉得递归很神奇，也会产生对递归本质的好奇。那么接下来让我们来了解递归是如何实现的吧。

在探索底层之前，请先实现下面这个函数，看你是否搞明白了递归：

int depth(TreeNode *root, int current_depth, int max_depth) 通过这个函数实现对树的深度的统计。并讲讲为什么后面两个int不需要使用指针变量。

相信你在使用递归的过程中，一定感觉递归和循环有很多相似之处，请你讲讲你对这两种算法的感悟。

递归在底层主要靠函数调用栈实现。请你先自行了解什么是栈。

每调用一次函数，系统都会在栈上创建一份新的“函数调用记录”，也叫栈帧。递归函数虽然是同一个函数，但每递归一次，都会产生一个新的栈帧。

一个栈帧里通常保存：

1. 参数
2. 局部变量
3. 返回地址
4. 一些寄存器的旧值

底层大概是这样：

• factorial(5) 入栈

  factorial(4) 入栈

  factorial(3) 入栈

  factorial(2) 入栈

  factorial(1) 入栈

栈中可以理解为：

• | factorial(1) |

  | factorial(2) |

  | factorial(3) |

  | factorial(4) |

  | factorial(5) |

当执行到 factorial(1)，满足结束条件，开始返回：

• factorial(1) 返回 1，出栈

  factorial(2) 得到结果 2 * 1，返回 2，出栈

  factorial(3) 得到结果 3 * 2，返回 6，出栈

  factorial(4) 得到结果 4 * 6，返回 24，出栈

  factorial(5) 得到结果 5 * 24，返回 120，出栈

也就是：

• 递归调用阶段：不断入栈

  递归返回阶段：不断出栈

  所以递归并不是“复制函数代码”，而是：

  同一份函数代码被多次调用

  每次调用都有自己独立的参数和局部变量

例如：

void test(int n) {

    int x = n;

    printf("%d\n", x);

     if (n > 1) {

         test(n - 1);

     }

}

调用 test(3) 时：

test(3) 的 x 是 3

test(2) 的 x 是 2

test(1) 的 x 是 1

这三个 x 不是同一个变量，而是三个不同栈帧里的局部变量。

为什么递归太深会崩溃？

因为栈空间有限。每递归一次就占用一层栈帧，如果递归层数太多：

栈帧越来越多 -> 栈空间耗尽 -> 栈溢出

例如：

void f() {

     f();

}

它没有结束条件，会一直入栈，最后栈溢出。

递归的底层实现就是普通函数调用；每递归一次，系统就在调用栈上创建一个新的栈帧，保存本次调用的参数、局部变量和返回位置，等函数返回时再逐层出栈。

通过读上面这一大段话，相信你对递归的底层实现有了初步的了解。你可能还是云里雾里的，那么让我们来通过栈和循环模拟一个递归实现吧。

typedef struct Stack {
    TreeNode **arr;
    int top;
    int capacity;
} Stack;
Stack *createStack(int capacity) {
    Stack *stack = malloc(sizeof(Stack));
    stack->arr = malloc(sizeof(TreeNode *) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}
int isEmpty(Stack *stack) {
    return stack->top == -1;
}
void push(Stack *stack, TreeNode *node) {
    if (stack->top == stack->capacity - 1) {
        return;
    }
    stack->arr[++stack->top] = node;
}
TreeNode *pop(Stack *stack) {
    if (isEmpty(stack)) {
        return NULL;
    }
    return stack->arr[stack->top--];
}

void preorderTraversal(TreeNode *root) // 补全这个函数

我在这里帮你写出了栈操作的基本函数。请你阅读并理解上面的栈操作，并书写简单的注释。

接下来将上面的部分粘贴到你的代码文件中，并利用栈操作实现二叉树的前序遍历，不许使用递归。

完成后在主函数中调用这个新的函数。

相信通过这个模拟让你产生了很多体悟。递归的应用很多，在中档题中你会更深入的使用和了解这一基本算法。

提交点这里

出题人：  taaaakoooo

QQ：1748798371

邮箱：1748798371@qq.com