二叉树场景下指针意外置空的触发场景分析（附C代码）

在常规二叉树操作中，存在如下C语言函数fun：

void fun(Node **root)
{
    printf("%p\n", *root); // 此处打印非空内存地址
    if (*root == NULL || (*root)->left == NULL)
        return;
    Node *p = (*root)->left;

    p->parent = (*root)->parent;
    printf("%p", *root); // 此处打印root为nil
    //...
}

已知树中仅包含3、2、1三个节点，且全部作为左子树添加，以下是该异常场景的触发逻辑与最小可复现代码：

触发场景与核心原因 #

触发时机 #

当向该左链二叉树（根为3，左子节点为2；2的左子节点为1）**添加第三个节点（值为1）**时，会触发fun函数中两次打印结果矛盾的异常。

关键逻辑链 #

1. 调用触发：添加节点1时，add函数完成节点初始化后调用fun1。此时节点1的父节点是2，节点2的父节点是3，满足fun1中(*root)->parent->parent非空的判断条件，因此调用fun(&((*root)->parent->parent))。
2. 指针指向的特殊性：传入fun的参数是&(节点2->parent)——即指向节点2的parent字段的指针，该字段当前存储的是节点3的地址，因此fun中第一次printf会打印节点3的非空地址。
3. 意外修改指针指向的变量：在fun中，p被赋值为节点3的左子节点（即节点2），随后执行p->parent = (*root)->parent：(*root)->parent是节点3的parent字段（值为NULL），这行代码直接将节点2的parent字段设置为NULL。而root指针恰好指向节点2的parent字段，因此第二次printf打印的就是被修改后的NULL。

最小可复现代码 #

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

typedef struct Node
{
    int data;
    struct Node *left, *right, *parent;

} Node;

void fun(Node **root)
{
    printf("%p\n", *root); // here it prints a non nil memory address
    if (*root == NULL || (*root)->left == NULL)
        return;
    Node *p = (*root)->left;

    p->parent = (*root)->parent;
    printf("%p", *root); // here it prints root as nil
    //...
}
void fun1(Node **root)
{
    if (*root && (*root)->parent && (*root)->parent->parent)
    {
        fun(&((*root)->parent->parent));
    }
}
void add(Node **root, Node *parent, int data)
{
    if (*root == NULL)
    {
        *root = (Node *)malloc(sizeof(Node));
        (*root)->data = data;
        (*root)->left = (*root)->right = NULL;
        (*root)->parent = parent;
        fun1(root);
        return;
    }

    if (data < (*root)->data)
        add(&((*root)->left), *root, data);
    else if (data > (*root)->data)
        add(&((*root)->right), *root, data);
}

int main()
{
    Node *root = NULL;
    add(&root, NULL, 3);
    add(&root, NULL, 2);
    add(&root, NULL, 1);
    return 0;
}

内容的提问来源于stack exchange，提问作者Vojin