4. 树与二叉搜索树

习题

#30006

⚡4⏳4

实现不透明的整数二叉搜索树：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct IntBst IntBst;

typedef enum {
    INT_BST_OK,
    INT_BST_INVALID,
    INT_BST_OUT_OF_MEMORY
} IntBstResult;

IntBst *int_bst_create(void);
void int_bst_destroy(IntBst *tree);
IntBstResult int_bst_insert(
    IntBst *tree,
    int64_t key,
    bool *out_inserted
);
bool int_bst_contains(const IntBst *tree, int64_t key);
bool int_bst_inorder(
    const IntBst *tree,
    int64_t *out_keys,
    size_t capacity,
    size_t *out_count
);

要求：

1. 每个结点的左子树键严格小于结点键，右子树键严格大于结点键；重复插入应成功返回并设置 *out_inserted = false。
2. 树拥有全部结点；int_bst_destroy(NULL) 必须安全。
3. 插入参数无效、分配失败或大小计算溢出时返回相应状态，树和 *out_inserted 保持不变。
4. 中序遍历必须按非递减顺序写入 out_keys；容量不足、参数无效时不得修改输出对象。
5. 空树的中序遍历允许 out_keys == NULL；out_count 必须非空。
6. 查找时间复杂度为 $O(h)$，其中 $h$ 为树高；中序遍历时间复杂度为 $O(n)$。

#30007

⚡5⏳4

验证一个用数组保存的二叉搜索树。结点编号为 0 到 count - 1，SIZE_MAX 表示空孩子：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    int64_t key;
    size_t left;
    size_t right;
} BstNode;

bool bst_validate(
    const BstNode *nodes,
    size_t count,
    size_t root
);

要求：

1. count == 0 时只有 root == SIZE_MAX 才合法；非空树的根必须是有效下标。
2. 所有孩子下标必须有效或为 SIZE_MAX，不能出现环、共享子树或无法从根到达的结点。
3. 对每个结点，左子树所有键严格更小，右子树所有键严格更大；不得通过 key - 1 或 key + 1 构造边界。
4. 参数无效时返回 false；不要求修改输入数组。
5. 时间复杂度为 $O(n)$，额外空间复杂度为 $O(n)$。