构造二叉排序树非递归算法 c语言

构造二叉排序树非递归算法通常通过迭代的方式来实现，也称为层序遍历。这种方法避免了递归带来的函数调用栈开销，适用于数据量较大的情况。以下是使用C语言的一个简单示例：

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

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

// 插入节点到已排序的二叉搜索树
Node* insert(Node* root, int value) {
    if (root == NULL) {
        // 如果根节点为空，创建新节点
        return (Node*) malloc(sizeof(Node));
    }

    if (value < root->data) {
        // 将值小于当前节点的元素插入左子树
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        // 否则插入右子树
        root->right = insert(root->right, value);
    }
    
    return root;
}

// 非递归构建二叉排序树
Node* buildBST(int arr[], int start, int end) {
    if (start > end)
        return NULL;

    int mid = (start + end) / 2; // 找到中间位置
    Node* root = insert(NULL, arr[mid]); // 创建根节点

    // 对左半部分和右半部分递归地应用此过程
    root->left = buildBST(arr, start, mid - 1);
    root->right = buildBST(arr, mid + 1, end);

    return root;
}

int main() {
    int arr[] = {5, 3, 7, 1, 4, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* bst = buildBST(arr, 0, n - 1);
    // ... 这里可以添加更多操作，如打印或遍历二叉树
    return 0;
}