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

1. 输入字符序列，建立二叉树的二叉链表的函数实现：

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

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

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

2. 实现二叉树的中序递归遍历算法的函数实现：

void inorderTraversal(Tree root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%c ", root->data);
        inorderTraversal(root->right);
    }
}

3. 实现二叉树的中序非递归遍历算法的函数实现：

#include <stdbool.h>
#include <stddef.h>

#define MAX_SIZE 100

typedef struct Stack {
    Tree data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, Tree t) {
    if (!isFull(s)) {
        s->data[++s->top] = t;
    }
}

Tree pop(Stack *s) {
    if (!isEmpty(s)) {
        return s->data[s->top--];
    }
    return NULL;
}

void inorderTraversalWithoutRecursion(Tree root) {
    Stack s;
    initStack(&s);
    Tree p = root;
    while (p != NULL || !isEmpty(&s)) {
        while (p != NULL) {
            push(&s, p);
            p = p->left;
        }
        if (!isEmpty(&s)) {
            p = pop(&s);
            printf("%c ", p->data);
            p = p->right;
        }
    }
}

4. 借助队列实现二叉树的层次遍历算法的函数实现：

#include <stdbool.h>
#include <stddef.h>

#define MAX_SIZE 100

typedef struct Queue {
    Tree data[MAX_SIZE];
    int front, rear;
} Queue;

void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

bool isEmpty(Queue *q) {
    return q->front == q->rear;
}

bool isFull(Queue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

void enqueue(Queue *q, Tree t) {
    if (!isFull(q)) {
        q->data[q->rear] = t;
        q->rear = (q->rear + 1) % MAX_SIZE;
    }
}

Tree dequeue(Queue *q) {
    if (!isEmpty(q)) {
        Tree t = q->data[q->front];
        q->front = (q->front + 1) % MAX_SIZE;
        return t;
    }
    return NULL;
}

void levelOrderTraversal(Tree root) {
    Queue q;
    initQueue(&q);
    if (root != NULL) {
        enqueue(&q, root);
    }
    while (!isEmpty(&q)) {
        Tree t = dequeue(&q);
        printf("%c ", t->data);
        if (t->left != NULL) {
            enqueue(&q, t->left);
        }
        if (t->right != NULL) {
            enqueue(&q, t->right);
        }
    }
}

5. 求二叉树的高度的函数实现：

int treeHeight(Tree root) {
    if (root == NULL) {
        return 0;
    } else {
        int leftHeight = treeHeight(root->left);
        int rightHeight = treeHeight(root->right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
}

6. 求二叉树的结点个数的函数实现：

int countNodes(Tree root) {
    if (root == NULL) {
        return 0;
    } else {
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
}

7. 求二叉树的叶子个数的函数实现：

int countLeaves(Tree root) {
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL) {
        return 1;
    } else {
        return countLeaves(root->left) + countLeaves(root->right);
    }
}

8. 交换二叉树每个结点的左子树和右子树的函数实现：

void swapChild(Tree root) {
    if (root != NULL) {
        Tree tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        swapChild(root->left);
        swapChild(root->right);
    }
}

9. 一个简单的菜单程序的实现：

int main() {
    Tree root = createTree();
    int choice = 0;
    do {
        printf("\n1. 中序递归遍历\n");
        printf("2. 中序非递归遍历\n");
        printf("3. 层次遍历\n");
        printf("4. 求高度\n");
        printf("5. 求结点个数\n");
        printf("6. 求叶子个数\n");
        printf("7. 交换子树\n");
        printf("0. 退出\n");
        printf("请选择操作：");
        scanf("%d", &choice);
        switch (choice) {
            case 1:
                inorderTraversal(root);
                break;
            case 2:
                inorderTraversalWithoutRecursion(root);
                break;
            case 3:
                levelOrderTraversal(root);
                break;
            case 4:
                printf("二叉树的高度为：%d\n", treeHeight(root));
                break;
            case 5:
                printf("二叉树的结点个数为：%d\n", countNodes(root));
                break;
            case 6:
                printf("二叉树的叶子个数为：%d\n", countLeaves(root));
                break;
            case 7:
                swapChild(root);
                break;
            case 0:
                break;
            default:
                printf("输入错误，请重新选择！\n");
                break;
        }
    } while (choice != 0);
    return 0;
}