在程序开始时用先序/中序/后序遍历的顺序建立二叉链表的递归算法

好的，这是一个经典的二叉树遍历问题。建立二叉链表的递归算法如下：

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void createBiTree(BiTree &T) {
    int ch;
    cin >> ch;
    if (ch == -1) {
        T = NULL;
    } else {
        T = new BiTNode;
        T->data = ch;
        createBiTree(T->lchild);
        createBiTree(T->rchild);
    }
}

在这里，我们使用了先序遍历的方式来建立二叉树。输入 `-1` 表示该节点为空，否则将输入的值赋给该节点，并递归地建立左子树和右子树。

如果你需要用中序或后序遍历的方式来建立二叉树，可以稍微修改一下递归的顺序即可。

相关问题

编写一道这样的程序1．要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的操作。其中先序遍历和后序遍历采用递归算法，中序遍历采用非递归算法。 2．输入数据：树中每个结点的数据类型设定为字符型。

好的，下面是程序实现：

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

typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 先序遍历
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

// 中序遍历
void inOrderTraversal(TreeNode* root) {
    TreeNode* stack[100];
    int top = -1;
    TreeNode* p = root;
    while (p != NULL || top != -1) {
        while (p != NULL) {
            stack[++top] = p;
            p = p->left;
        }
        if (top != -1) {
            p = stack[top--];
            printf("%c ", p->data);
            p = p->right;
        }
    }
}

// 后序遍历
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%c ", root->data);
}

// 创建二叉树
TreeNode* createTree() {
    char c;
    scanf("%c", &c);
    if (c == '#') {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = c;
    root->left = createTree();
    root->right = createTree();
    return root;
}

int main() {
    printf("请输入二叉树的先序遍历序列(其中'#'表示空节点)：\n");
    TreeNode* root = createTree();

    printf("先序遍历结果为：");
    preOrderTraversal(root);
    printf("\n");

    printf("中序遍历结果为：");
    inOrderTraversal(root);
    printf("\n");

    printf("后序遍历结果为：");
    postOrderTraversal(root);
    printf("\n");

    return 0;
}

程序说明：

1. `TreeNode` 结构体表示二叉树的节点，包含数据域 `data` 和左右子树指针 `left` 和 `right`。
2. 先序遍历、中序遍历和后序遍历分别用了不同的算法实现。其中，中序遍历采用了非递归算法，使用栈来辅助实现。
3. `createTree()` 函数递归地创建二叉树，输入先序遍历序列即可。
4. 在 `main()` 函数中调用各个遍历函数，输出遍历结果。

注意事项：

1. 在创建二叉树时，输入先序遍历序列时要注意写法，输入格式类似于 `AB#C##D##`，其中 `#` 表示空节点。
2. 输入完先序遍历序列后，要记得使用 `getchar()` 消耗掉输入流中的回车符。

用c语言实现：1. 建立自己的头文件BT.H，内容包括二叉链表的结构描述、二叉树的建立、二叉树的先序、中序与后序遍历算法。 2. 建立二叉树,并通过调用函数, 输出先序遍历、中序遍历与后序遍历的结果。

在C语言中，为了实现二叉树的操作，我们首先需要在`BT.h`头文件中定义相关的数据结构以及重要的函数声明：

// BT.h
#ifndef BT_H
#define BT_H

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

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

// 创建一个新的二叉树节点
TreeNode* createNode(int value);

// 二叉树的建立，这里采用递归的方式插入节点
TreeNode* buildTree(int arr[], int start, int end);

// 二叉树的遍历函数声明
void preOrder(TreeNode* root);
void inOrder(TreeNode* root);
void postOrder(TreeNode* root);

#endif // BT_H

接下来，我们在`BT.c`文件中实现上述函数：

// BT.c
#include "BT.h"

// 创建新的节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        return NULL;
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 二叉树构建函数
TreeNode* buildTree(int arr[], int start, int end) {
    if (start > end)
        return NULL;

    int mid = (start + end) / 2;
    TreeNode* root = createNode(arr[mid]);
    root->left = buildTree(arr, start, mid - 1);
    root->right = buildTree(arr, mid + 1, end);
    return root;
}

// 先序遍历
void preOrder(TreeNode* root) {
    if (root == NULL)
        return;
    printf("%d ", root->data); // 输出节点值
    preOrder(root->left);
    preOrder(root->right);
}

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

// 后序遍历
void postOrder(TreeNode* root) {
    if (root == NULL)
        return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->data); // 输出节点值
}

最后，在`main.c`中测试这些函数：

#include "BT.h"

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    TreeNode* root = buildTree(arr, 0, n - 1);
    if (root == NULL) {
        printf("Failed to build tree\n");
        return 1;
    }

    printf("Preorder traversal: ");
    preOrder(root);
    printf("\n");

    printf("Inorder traversal: ");
    inOrder(root);
    printf("\n");

    printf("Postorder traversal: ");
    postOrder(root);
    printf("\n");

    free(root);
    return 0;
}

这个程序创建了一个二叉搜索树并实现了三种遍历方式。运行`main.c`将输出相应的遍历结果。