定义数据类型#

#define bool int

typedef struct Node
{
    int id;
    struct Node *l;
    struct Node *r;
} Node;

打印树的函数#

让chatGPT写一个打印树形状的函数, 方便检验是否创建成功.

void printTree(Node *root, int depth)
{
    if (root == NULL)
    {
        return;
    }

    // 递归打印右子树,增加缩进
    printTree(root->r, depth + 1);

    // 打印当前节点,并根据深度增加缩进
    for (int i = 0; i < depth; i++)
    {
        printf("    "); // 每个深度级别缩进4个空格
    }
    printf("%d\n", root->id);

    // 递归打印左子树,增加缩进
    printTree(root->l, depth + 1);
}

创建一颗完全二叉树#

随便先创建一颗二叉树. 基于数组模拟, 先尝试创建一颗 size 为 n 的完全二叉树.(输入$n_总$来创建二叉树)

• 结点生成函数

Node *makeNode(int id)
{
    Node *node;
    node = (Node *)malloc(sizeof(Node));
    node->id = id;
    node->l = node->r = NULL;
    return node;
}

• 树生成函数

Node *makeTree(int size)
{
    void **arr = malloc(sizeof(void *) * (size + 1));
    free(arr[0]);
    // 用于存储结点指针的指针数组, 以便于批量创建结点
    // 为了对齐下标和id, 在这里多申请一块空间
    for (int i = 1; i <= size; i++)
    {
        arr[i] = makeNode(i);
    }
    for (int i = 1; i <= size; i++)
    {
        if (2 * i <= size)
            ((Node *)arr[i])->l = ((Node *)arr[2 * i]);
        // 当左子id<n, 作为一颗完全二叉树来说左子一定存在. 当左子存在, 将l指向左子.
        if (2 * i + 1 <= size)
            ((Node *)arr[i])->r = ((Node *)arr[2 * i + 1]);
        // 当右子id<n, 作为一颗完全二叉树来说右子一定存在. 当右子存在, 将r指向右子
    }
    printTree((Node *)arr[1], 0);
    Node *root = arr[1];
    free(arr);
    return root;
}

定义访问行为#

void visit(Node *any_node)
{
    printf("%d ", any_node->id);
}

先序遍历#

// 王道-先序遍历
void PreOrderTR(Node *root)
{
    if (!root)
        return;
    visit(root);
    PreOrderTR(root->l);
    PreOrderTR(root->r);
}

中序遍历#

// 王道-中序遍历
void InOrderTR(Node *root)
{
    if (!root) // 退出的边界条件, 目前访问的指针不为空. 否则走
        return;
    InOrderTR(root->l);
    visit(root);
    InOrderTR(root->r);
}

后序遍历#

void PastOrderTR(Node *root)
{
    if (!root)
        return;
    PastOrderTR(root->l);
    PastOrderTR(root->r);
    visit(root);
}

(严蔚敏版)先序遍历#

严蔚敏数据结构书上的代码通过多个 if 嵌套来保证每一步的操作必须成功才能继续进行,而不是直接递归到左、右子树.这样能确保递归的每一步都受到严格控制, 返回0就直接跳出去或者报错.

// 严蔚敏-先序遍历
bool PreOrderTR_2(Node *root, bool (*visitnode)(Node *))
{
    if (root)
    {
        if (visitnode(root))
            if (PreOrderTR_2(root->l, visitnode))
                if (PreOrderTR_2(root->r, visitnode))
                    return 1;
    }
    else
        return 1;
    // 在这种写法中必须要有一个返回值
}

bool visitnode(Node *any_node)
{
    printf("%d ", any_node->id);
    return 1;
}