如何在打印二叉搜索树节点时标注其父节点及左右位置？

嘿，我明白你的需求——想在遍历BST时，清晰显示每个节点的父节点和它是左/右子节点的信息，而且不想因为这个需求大改现有代码对吧？其实不用给节点加父指针也能搞定，下面我给你两种可行的C语言实现方案：

方案1：修改递归遍历函数，传递父节点信息 #

你已经熟悉递归的中序遍历，只需要给遍历函数加两个额外参数：父节点的值和当前节点的位置标识（比如用' '表示根节点，'L'表示左子节点，'R'表示右子节点）。这样在遍历每个节点时，就能直接打印出它的父节点和位置信息了。

代码示例： #

首先是基础的BST节点定义：

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 插入节点到BST
Node* insert(Node* root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

然后是修改后的中序遍历函数：

// 带父节点信息的中序遍历
void inorderWithParent(Node* root, int parentVal, char pos) {
    if (root == NULL) return;
    
    // 递归左子树，当前节点作为父节点，位置是L
    inorderWithParent(root->left, root->data, 'L');
    
    // 打印当前节点信息：根节点直接打印值，子节点带父节点和位置
    if (pos == ' ') {
        printf("%d ", root->data);
    } else {
        printf("%d (%d %c) ", root->data, parentVal, pos);
    }
    
    // 递归右子树，当前节点作为父节点，位置是R
    inorderWithParent(root->right, root->data, 'R');
}

主函数调用时，根节点的父节点值可以随便填（因为不会用到），位置传' '：

int main() {
    Node* root = NULL;
    // 插入题目中的节点：70、90、50、60、80、40
    root = insert(root, 70);
    root = insert(root, 90);
    root = insert(root, 50);
    root = insert(root, 60);
    root = insert(root, 80);
    root = insert(root, 40);
    
    printf("带父节点信息的中序遍历结果：\n");
    inorderWithParent(root, 0, ' '); // 根节点无父节点，pos传空格
    printf("\n");
    
    // 别忘了释放内存，这里省略，实际项目中要加
    return 0;
}

运行结果会是：

40 (50 L) 50 (70 L) 60 (50 R) 70 80 (90 L) 90 (70 R) 

方案2：层序遍历（广度优先）带父节点信息 #

你之前尝试层序遍历崩溃，大概率是因为队列操作没处理好空节点，或者没正确传递父节点信息。我们可以给队列里的元素增加父节点值和位置标识，用一个辅助结构体来存储这些信息。

代码示例： #

首先定义队列元素的结构体：

// 队列元素：存储节点指针、父节点值、位置标识
typedef struct QueueItem {
    Node* node;
    int parentVal;
    char pos;
} QueueItem;

// 队列的简单实现
typedef struct Queue {
    QueueItem* items;
    int front;
    int rear;
    int capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->rear = 0;
    queue->items = (QueueItem*)malloc(sizeof(QueueItem) * capacity);
    return queue;
}

// 入队操作
void enqueue(Queue* queue, Node* node, int parentVal, char pos) {
    if (queue->rear == queue->capacity) {
        printf("队列满了\n");
        return;
    }
    queue->items[queue->rear].node = node;
    queue->items[queue->rear].parentVal = parentVal;
    queue->items[queue->rear].pos = pos;
    queue->rear++;
}

// 出队操作
QueueItem dequeue(Queue* queue) {
    QueueItem item = queue->items[queue->front];
    queue->front++;
    return item;
}

// 判断队列是否为空
int isQueueEmpty(Queue* queue) {
    return queue->front == queue->rear;
}

然后是层序遍历函数：

// 带父节点信息的层序遍历
void levelOrderWithParent(Node* root) {
    if (root == NULL) return;
    
    // 创建队列，容量设为足够大（比如100）
    Queue* queue = createQueue(100);
    // 根节点入队，父节点值0，位置空格
    enqueue(queue, root, 0, ' ');
    
    while (!isQueueEmpty(queue)) {
        QueueItem item = dequeue(queue);
        Node* current = item.node;
        
        // 打印当前节点信息
        if (item.pos == ' ') {
            printf("%d ", current->data);
        } else {
            printf("%d (%d %c) ", current->data, item.parentVal, item.pos);
        }
        
        // 左子节点入队，父节点是当前节点，位置L
        if (current->left != NULL) {
            enqueue(queue, current->left, current->data, 'L');
        }
        // 右子节点入队，父节点是当前节点，位置R
        if (current->right != NULL) {
            enqueue(queue, current->right, current->data, 'R');
        }
    }
    
    // 释放队列内存
    free(queue->items);
    free(queue);
}

主函数里调用这个函数：

int main() {
    // 插入节点的代码和之前一样
    Node* root = NULL;
    root = insert(root, 70);
    root = insert(root, 90);
    root = insert(root, 50);
    root = insert(root, 60);
    root = insert(root, 80);
    root = insert(root, 40);
    
    printf("带父节点信息的层序遍历结果：\n");
    levelOrderWithParent(root);
    printf("\n");
    
    // 释放BST内存（省略，实际要实现）
    return 0;
}

运行结果会是：

70 50 (70 L) 90 (70 R) 40 (50 L) 60 (50 R) 80 (90 L) 

为什么不用父指针？ #

给节点加父指针确实能实现需求，但需要在插入节点时额外维护父节点的指向，增加了代码复杂度，而且如果后续有删除节点的操作，还要处理父指针的更新，容易出错。而上面两种方案不需要修改原有节点结构，只是在遍历过程中传递信息，更轻量、更灵活。

如果之前层序遍历崩溃，检查下是不是队列没初始化好，或者入队了空节点——上面的代码里只有当子节点不为空时才入队，避免了空指针访问的问题。

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