如何在tsearch节点中获取左右子节点及判断树的状态

为什么用LEFT宏和struct node_t会报错 #

这些是GNU C库实现tsearch时的内部私有细节，并没有在标准头文件（比如search.h）中暴露。编译器找不到它们的声明，自然会报隐式声明或不完整类型的错误——毕竟标准的tsearch接口设计就是让你不用关心内部树结构的。

自行遍历树的两种方案 #

方案1：依赖GNU实现的私有结构（不推荐，不可移植） #

如果你只针对GNU libc环境（比如大多数Linux系统），可以自己手动复刻和内部一致的结构体，直接访问节点的左右指针：

#include <search.h>
#include <stdio.h>

// 手动复刻GNU libc内部的node_t结构（需和你系统的search.c源码一致）
struct node_t {
    const void *key;
    struct node_t *left;
    struct node_t *right;
    struct node_t *parent;
};

// 递归遍历树（前序示例）
void traverse_tree(struct node_t *node) {
    if (!node) return;
    printf("Key: %d\n", *(int*)node->key);
    traverse_tree(node->left);
    traverse_tree(node->right);
}

int main() {
    int arr[] = {3,1,4,1,5,9};
    void *root = NULL;
    for (int i=0; i<6; i++) {
        tsearch(&arr[i], &root, (int(*)(const void*,const void*))strcmp);
    }
    // 强制类型转换为我们定义的结构体指针
    traverse_tree((struct node_t*)root);
    return 0;
}

⚠️ 注意：这种做法完全依赖特定版本的libc实现，换个系统或libc版本可能直接崩溃，属于未定义行为，生产环境别用。

方案2：用标准API模拟遍历（推荐，可移植） #

标准的tsearch配套了twalk函数，可以遍历整个树，但它不会直接返回子节点指针。你可以用它先收集所有节点的键值，再基于这些键值处理：

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

int count = 0;
int *keys = NULL;

void collect_keys(const void *node, const VISIT which, const int depth) {
    if (which == preorder || which == leaf) {
        keys = realloc(keys, sizeof(int)*(count+1));
        keys[count++] = *(int*)node;
    }
}

int main() {
    int arr[] = {3,1,4,1,5,9};
    void *root = NULL;
    for (int i=0; i<6; i++) {
        tsearch(&arr[i], &root, (int(*)(const void*,const void*))strcmp);
    }
    // 用twalk收集所有节点的键
    twalk(root, collect_keys);
    // 现在可以基于keys数组做后续处理，比如构建自己可控的二叉树
    for (int i=0; i<count; i++) {
        printf("%d ", keys[i]);
    }
    free(keys);
    return 0;
}

判断树是否平衡的方法 #

平衡树的核心判定规则是：任意节点的左右子树高度差的绝对值不超过1，实现逻辑如下：

1. 对每个节点，递归计算其左、右子树的高度
2. 检查当前节点的左右高度差是否≤1，同时递归验证左右子树是否都满足该条件
3. 所有节点都通过验证，即为平衡树

如果用方案1的私有结构，可以直接写递归函数实现：

int tree_height(struct node_t *node) {
    if (!node) return 0;
    int left_h = tree_height(node->left);
    int right_h = tree_height(node->right);
    return (left_h > right_h ? left_h : right_h) + 1;
}

int is_balanced(struct node_t *node) {
    if (!node) return 1;
    int left_h = tree_height(node->left);
    int right_h = tree_height(node->right);
    if (abs(left_h - right_h) > 1) return 0;
    return is_balanced(node->left) && is_balanced(node->right);
}

如果用方案2的标准API，你可以把收集到的键重新构建一棵自己的二叉搜索树，再用同样的逻辑判断平衡性——毕竟自己的树结构完全可控。

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