7-2 二叉查找树的构建及序列化PTA

7-2 二叉查找树（Binary Search Tree, BST）的构建通常涉及以下几个步骤：

**构建过程：**
1. **初始化**：如果你从空开始，创建一个新的根节点。
2. **插入元素**：对于给定的序列，从根节点开始遍历，如果当前节点为空，则将新元素作为新的根节点；否则，比较新元素值与当前节点值的大小关系，如果是较小的值则向左子节点递归，反之向右子节点递归，直到找到合适的位置插入元素。
3. **保持性质**：每次插入后，确保满足BST的特性：左子树的所有节点都小于根节点，右子树的所有节点都大于根节点。

**序列化过程（Serialization）：**
在二叉查找树的序列化中，通常会将每个节点表示为一个字符串，包含节点值和其子节点的引用。一种常见的方法是使用前序遍历（Root-Left-Right），按照“值-左子树-右子树”的顺序生成序列。例如，假设有这样的树结构：

   5
 / \
3   8
 \     \
  2   9

序列化后的结果可能是：“5,3,2,null,8,null,9”。

**相关问题--:**
1. 二叉查找树如何保证搜索效率？
2. 序列化过程中为什么要使用前序遍历？
3. 如何在反序列化时重构原来的二叉查找树？

相关问题

7-2 二叉查找树的构建及序列化

7-2 二叉查找树（Binary Search Tree，BST），也称二叉搜索树，是一种特殊的二叉树，它的每个节点包含一个键值和两个指向子节点的指针，左子树的所有节点的键值都小于该节点的键值，右子树的所有节点的键值都大于该节点的键值。构建BST通常从空开始，每次插入新元素时按照这个规则调整结构。

构建过程：
1. 初始化一个空的根节点。
2. 当有新的元素需要插入时，如果根节点为空，则直接将新元素作为根节点；否则，比较新元素的值与当前节点的值。
3. 如果新元素的值小于当前节点，就在当前节点的左子树递归地插入；反之，在右子树插入。
4. 这样就保证了每个节点的左子树始终是小于其值的元素集合，右子树是大于其值的元素集合。

序列化BST通常是将树转换成一个线性的数据结构，例如数组或字符串，以便存储或传输。一种常见的方法是前序遍历（Root -> Left -> Right）记录节点的路径。例如，对于树：

      5
     / \
    3   8
   / \   \
  2   4   9

序列化结果可能是 `[5,3,2,4,8,9]` 或者 `"5,3,2,4,8,9,"`，取决于是否包含终止符。

7-2 二叉查找树的构建及序列化（C语言）

在C语言中，构建二叉查找树（Binary Search Tree，BST）通常从根节点开始，然后递归地插入新元素。构建过程如下：

1. 创建一个结构体表示二叉树的节点，包含整数值、左孩子指针和右孩子指针：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

2. 插入函数`insertNode`，它会比较新值与当前节点值，如果新值小于当前值，就将其放在左子树；反之，放在右子树，并递归处理子节点：

TreeNode* insertNode(TreeNode** root, int val) {
    if (*root == NULL) {
        *root = (TreeNode*)malloc(sizeof(TreeNode));
        (*root)->val = val;
        return *root;
    }
    if (val < (*root)->val)
        (*root)->left = insertNode(&(*root)->left, val);
    else
        (*root)->right = insertNode(&(*root)->right, val);
    return *root;
}

3. 序列化BST到数组的过程，可以采用先序遍历（根-左-右），将每个节点的值存储起来，形成序列：

void inorderTraversal(TreeNode* root, int* arr, int& i) {
    if (root != NULL) {
        inorderTraversal(root->left, arr, i);
        arr[i++] = root->val;
        inorderTraversal(root->right, arr, i);
    }
}

// 序列化函数
void serializeBST(TreeNode* root, int* result) {
    int len = 0;
    inorderTraversal(root, result, len);
    result[len] = -1; // 标志序列结束
}

4. 要恢复二叉树，从序列的第一个非负数开始，重建节点结构。