输入结点，创建二叉排序树，中序遍历输出，插入一个结点，再中序遍历输出。。。书上算法都有，链一下，看看最后能否实现。

可以的，输入结点，创建二叉排序树，中序遍历输出，插入一个结点，再中序遍历输出的过程如下：
首先，我们输入结点并创建二叉排序树，根结点为输入的第一个节点。然后，我们进行中序遍历输出树的结点，即先遍历左子树，输出根结点，再遍历右子树。
接下来，我们插入一个结点，具体做法如下：
如果插入的结点小于当前节点，就将其插入到当前节点的左子树中；如果插入的结点大于当前节点，就将其插入到当前节点的右子树中。然后，我们再次进行中序遍历输出树的结点，可以看到新插入的结点已经加入到了相应的位置。
最后，我们可以链一下算法的相关资料，进行参考和学习。

相关问题

给定一个二叉树（二叉链表存储），设计算法返回中序遍历的第一个结点。

### 回答1：
中序遍历的第一个结点是指二叉树中按照中序遍历顺序，第一个被访问到的结点。要设计算法返回中序遍历的第一个结点，可以采用递归或非递归方式实现。

递归方式：从根节点开始，先递归遍历左子树，如果左子树为空，则当前结点即为中序遍历的第一个结点；如果左子树不为空，则继续递归遍历左子树，直到找到左子树为空的结点。

非递归方式：采用栈来实现中序遍历，从根节点开始，将根节点及其左子树的所有结点依次入栈，直到左子树为空的结点。然后从栈中弹出一个结点，访问该结点，如果该结点有右子树，则将右子树及其左子树的所有结点依次入栈，直到左子树为空的结点。重复上述过程，直到栈为空。

无论采用递归还是非递归方式，返回的中序遍历的第一个结点都是二叉树中最左侧的结点。

### 回答2：
中序遍历的顺序为左子树根节点右子树，因此中序遍历的第一个节点是最左下方的节点，也就是二叉树中最左的叶子节点或者是最左侧的父节点。

设计算法如下：
1. 将当前结点置为根节点。
2. 如果左子树非空，则将左子树作为当前结点，并重复步骤2直到当前结点的左子树为空。
3. 如果当前结点没有父节点，则返回当前结点；否则，将当前结点的父节点作为当前结点，判断当前结点是否作为其父节点的右子节点，如果是，则重复步骤3；如果不是，则返回当前结点的父节点。

代码实现如下：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* firstInorderNode(TreeNode* root) {
    if (!root) { //二叉树为空
        return NULL;
    }
    while (root->left) { //当前结点有左子树
        root = root->left;
    }
    while (root->parent) { //当前结点有父节点
        if (root == root->parent->right) { //当前结点是其父节点的右子节点
            root = root->parent;
        } else { //当前结点是其父节点的左子节点
            return root->parent;
        }
    }
    return NULL; //当前节点为根节点为中序遍历的第一个节点，没有父节点，返回NULL
}

时间复杂度为O(h)，其中h为树的高度。空间复杂度为O(1)。

### 回答3：
二叉树的中序遍历是按照"左子树-根节点-右子树"的顺序遍历二叉树的一种方式，中序遍历的第一个结点即为二叉树中最左侧的叶子节点。

因此，设计算法返回中序遍历的第一个结点，可采用递归方式。首先判断当前节点是否存在左子树，如果存在，则递归遍历左子树。如果不存在左子树，则该节点即为中序遍历的第一个结点，返回该节点即可。

具体的实现过程如下：

1. 定义递归函数findFirstNode(Node node)。
2. 判断node是否为null，若是则返回null。
3. 判断node的左子树是否存在，若存在则递归遍历左子树。
4. 若左子树不存在，则返回该节点node。
5. 整个算法的返回值即为findFirstNode(root)，其中root为二叉树的根节点。

c语言完成用二叉链表作为存储结构，输入序列建立一棵二叉排序树，然后中序遍历这棵二叉树

好的，让我来简单介绍一下二叉排序树的概念和实现思路。

二叉排序树又称为二叉搜索树，是一种特殊的二叉树，它满足以下条件：

1. 对于任意结点，它的左子树中的所有结点的值都小于它的值；
2. 对于任意结点，它的右子树中的所有结点的值都大于它的值；
3. 左右子树都是二叉排序树。

根据这个定义，我们可以用二叉链表来实现一棵二叉排序树。具体实现思路如下：

1. 定义二叉树的结点类型，包括结点的值、左右子结点指针；
2. 定义一个函数，用于向二叉排序树中插入一个结点；
3. 读入一组序列，依次插入到二叉排序树中；
4. 中序遍历整棵二叉排序树，输出结点的值。

下面是具体的代码实现，你可以参考一下：

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

// 定义二叉树结点类型
typedef struct node {
    int value;
    struct node* left;
    struct node* right;
} Node;

// 向二叉排序树中插入一个结点
Node* insert(Node* root, int value) {
    if (root == NULL) {
        // 如果当前结点为空，就创建一个新的结点
        Node* node = (Node*)malloc(sizeof(Node));
        node->value = value;
        node->left = NULL;
        node->right = NULL;
        return node;
    } else if (value < root->value) {
        // 如果插入的值小于当前结点的值，就插入到左子树中
        root->left = insert(root->left, value);
    } else {
        // 如果插入的值大于等于当前结点的值，就插入到右子树中
        root->right = insert(root->right, value);
    }
    return root;
}

// 中序遍历二叉排序树
void inorder(Node* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->value);
    inorder(root->right);
}

int main() {
    // 读入一组序列，依次插入到二叉排序树中
    int n, value;
    scanf("%d", &n);
    Node* root = NULL;
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        root = insert(root, value);
    }

    // 中序遍历整棵二叉排序树，输出结点的值
    inorder(root);

    return 0;
}

这样就完成了二叉排序树的建立和中序遍历。当然，这只是一个简单的实现，如果你想进一步了解二叉排序树的相关知识，可以参考一些经典的算法教材。