用C语言1.编写函数,输入字符序列,建立二叉树的二叉链表 2.编写函数,实现二叉树的中序递归遍历算法。 3.编写函数,实现二叉树的中序非递归遍历算法 4.编写函数,借助队列实现二叉树的层次遍历算法 5.编写函数,求二叉树的高度 6.编写函数,求二叉树的结点个数 7.编写函数,求二叉树的叶子个数 8.编写函数,交换二叉树每个结点的左子树和右子树 9.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法

1. 输入字符序列，建立二叉树的二叉链表的 C 语言代码如下：

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

TreeNode* buildTree(char* s, int* idx) {
    if (s[*idx] == '\0' || s[*idx] == '#') {
        (*idx)++;
        return NULL;
    }
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = s[*idx];
    (*idx)++;
    node->left = buildTree(s, idx);
    node->right = buildTree(s, idx);
    return node;
}

2. 实现二叉树的中序递归遍历算法的 C 语言代码如下：

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%c ", root->val);
    inorderTraversal(root->right);
}

3. 实现二叉树的中序非递归遍历算法的 C 语言代码如下：

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[1000];
    int top = -1;
    TreeNode* cur = root;
    while (cur != NULL || top != -1) {
        while (cur != NULL) {
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top--];
        printf("%c ", cur->val);
        cur = cur->right;
    }
}

4. 借助队列实现二叉树的层次遍历算法的 C 语言代码如下：

void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* cur = queue[front++];
        printf("%c ", cur->val);
        if (cur->left) {
            queue[rear++] = cur->left;
        }
        if (cur->right) {
            queue[rear++] = cur->right;
        }
    }
}

5. 求二叉树的高度的 C 语言代码如下：

int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

6. 求二叉树的结点个数的 C 语言代码如下：

int getNodeCount(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return getNodeCount(root->left) + getNodeCount(root->right) + 1;
}

7. 求二叉树的叶子个数的 C 语言代码如下：

int getLeafCount(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return getLeafCount(root->left) + getLeafCount(root->right);
}

8. 交换二叉树每个结点的左子树和右子树的 C 语言代码如下：

void swap(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    swap(root->left);
    swap(root->right);
}

9. 编写一个主函数，调试上述算法的 C 语言代码如下：

int main() {
    char s[] = "ABD##E##CF###";
    int idx = 0;
    TreeNode* root = buildTree(s, &idx);
    while (1) {
        printf("\n请输入一个数字(1-9)选择要测试的算法，0退出：");
        int choice;
        scanf("%d", &choice);
        if (choice == 0) {
            break;
        }
        switch (choice) {
            case 1:
                root = buildTree(s, &idx);
                break;
            case 2:
                inorderTraversal(root);
                printf("\n");
                break;
            case 3:
                inorderTraversal(root);
                printf("\n");
                break;
            case 4:
                levelOrderTraversal(root);
                printf("\n");
                break;
            case 5:
                printf("%d\n", getHeight(root));
                break;
            case 6:
                printf("%d\n", getNodeCount(root));
                break;
            case 7:
                printf("%d\n", getLeafCount(root));
                break;
            case 8:
                swap(root);
                break;
            default:
                break;
        }
    }
    return 0;
}