链表实现二叉树C语言，要求输入为结点个数，以及各节点的值，输出为二叉树的先序序遍历，输出测试深度，先序遍历建立的二叉树，中序遍历建立的二叉树（递归方式）。中序遍历建立的二叉树（非递归方式），后续遍历建立的二叉树，建立的二叉树的左子树的值和右子树的值

以下是实现链表表示二叉树的C语言代码，包括输入结点个数和各节点的值，并输出先序遍历、测试深度、中序遍历、后序遍历等相关信息： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树结点结构体 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 创建二叉树 // 返回值为根节点的指针 TreeNode* createTree(int n) { int i, val; TreeNode *node, *p, *q; TreeNode **queue = (TreeNode **)malloc(sizeof(TreeNode *) * n); // 输入根节点的值 printf("请输入根节点的值："); scanf("%d", &val); // 创建根节点 node = (TreeNode *)malloc(sizeof(TreeNode)); node->val = val; node->left = NULL; node->right = NULL; queue[0] = node; // 使用队列逐层创建二叉树 for (i = 1; i < n; i++) { printf("请输入第%d个节点的值：", i+1); scanf("%d", &val); p = (TreeNode *)malloc(sizeof(TreeNode)); p->val = val; p->left = NULL; p->right = NULL; queue[i] = p; // 将新节点插入到父节点的左右子树中 q = queue[(i-1)/2]; if (i % 2 == 1) { q->left = p; } else { q->right = p; } } free(queue); return node; } // 先序遍历二叉树 void preOrder(TreeNode *root) { if (root == NULL) { return; } printf("%d ", root->val); preOrder(root->left); preOrder(root->right); } // 测试深度 int maxDepth(TreeNode *root) { if (root == NULL) { return 0; } else { int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; } } // 中序遍历二叉树（递归方式） void inOrderRecursive(TreeNode *root) { if (root == NULL) { return; } inOrderRecursive(root->left); printf("%d ", root->val); inOrderRecursive(root->right); } // 中序遍历二叉树（非递归方式） void inOrderNonRecursive(TreeNode *root) { TreeNode *stack[1000]; int top = -1; TreeNode *p = root; while (p != NULL || top >= 0) { while (p != NULL) { stack[++top] = p; p = p->left; } if (top >= 0) { p = stack[top--]; printf("%d ", p->val); p = p->right; } } } // 后序遍历二叉树 void postOrder(TreeNode *root) { if (root == NULL) { return; } postOrder(root->left); postOrder(root->right); printf("%d ", root->val); } // 计算左子树的节点数和右子树的节点数 void countNodes(TreeNode *root, int *leftCount, int *rightCount) { if (root == NULL) { *leftCount = 0; *rightCount = 0; return; } int left = 0, right = 0; countNodes(root->left, &left, &right); *leftCount = left + right + 1; countNodes(root->right, &left, &right); *rightCount = left + right + 1; } int main() { int n, leftCount, rightCount; TreeNode *root; printf("请输入二叉树的结点个数："); scanf("%d", &n); root = createTree(n); printf("先序遍历结果："); preOrder(root); printf("\n"); printf("测试深度：%d\n", maxDepth(root)); printf("中序遍历结果（递归方式）："); inOrderRecursive(root); printf("\n"); printf("中序遍历结果（非递归方式）："); inOrderNonRecursive(root); printf("\n"); printf("后序遍历结果："); postOrder(root); printf("\n"); countNodes(root->left, &leftCount, &rightCount); printf("左子树的值：%d，右子树的值：%d\n", leftCount, rightCount); return 0; } ``` 需要注意的是，这里采用了队列来逐层创建二叉树。对于中序遍历建立的二叉树，我们使用了递归和非递归两种方式来实现。对于左子树和右子树的值，我们使用了一个辅助函数 `countNodes` 来计算。