用顺序和二叉链表作存储结构1 以回车’n为输入结束标志输入数列L生成一棵二叉排

序树T，要求按照输入顺序建树，即每个结点的左子树为其前一个输入的结点，右子树为其后一个输入的结点。若没有前一个或后一个结点，则对应子树为空。

输入示例：1 2 3 4 5 6 7 8 9

输出示例：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

/
8 9

二叉链表存储结构代码实现：

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

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

// 创建节点
TreeNode* createNode(int val) {
    TreeNode *node = (TreeNode*) malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 生成二叉排序树
TreeNode* buildTree() {
    TreeNode *root = NULL, *p, *pre;
    int val;
    scanf("%d", &val);
    while (val != '\n') {
        p = createNode(val);
        if (root == NULL) {
            root = p;
        } else {
            pre = root;
            while (1) {
                if (val < pre->val) {
                    if (pre->left == NULL) {
                        pre->left = p;
                        break;
                    } else {
                        pre = pre->left;
                    }
                } else {
                    if (pre->right == NULL) {
                        pre->right = p;
                        break;
                    } else {
                        pre = pre->right;
                    }
                }
            }
        }
        scanf("%d", &val);
    }
    return root;
}

// 中序遍历输出
void inorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    TreeNode *root = buildTree();
    inorderTraversal(root);
    return 0;
}

顺序存储结构代码实现：

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

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int length;
} SeqList;

// 初始化顺序表
void initList(SeqList *L) {
    L->length = 0;
}

// 插入元素
void insert(SeqList *L, int val) {
    L->data[L->length++] = val;
}

// 生成二叉排序树
void buildTree(SeqList *L, int cur, int len) {
    if (cur >= len) {
        return;
    }
    int val = L->data[cur];
    int left = 2 * cur + 1, right = 2 * cur + 2;
    if (left < len && L->data[left] < val) {
        L->data[cur] = L->data[left];
        L->data[left] = val;
        buildTree(L, left, len);
    }
    if (right < len && L->data[right] < val) {
        L->data[cur] = L->data[right];
        L->data[right] = val;
        buildTree(L, right, len);
    }
    buildTree(L, cur + 1, len);
}

// 中序遍历输出
void inorderTraversal(SeqList *L, int cur) {
    if (cur >= L->length) {
        return;
    }
    inorderTraversal(L, 2 * cur + 1);
    printf("%d ", L->data[cur]);
    inorderTraversal(L, 2 * cur + 2);
}

int main() {
    SeqList L;
    initList(&L);
    int val;
    scanf("%d", &val);
    while (val != '\n') {
        insert(&L, val);
        scanf("%d", &val);
    }
    buildTree(&L, 0, L.length);
    inorderTraversal(&L, 0);
    return 0;
}
``