该问题要求设计程序,利用二叉链表结构,建立一棵二叉树。并能递归实现二叉树的先序遍历、中序遍历和后序遍历三种遍历算法,能用队列实现二叉树的层次遍历算法,并按层次输出(标出层号),并能统计树叶数,结点数,层高等信息。
时间: 2023-10-05 19:11:24 浏览: 77
好的,我明白了。这个问题要求你建立一个二叉树,并能够实现四种遍历算法和统计一些信息。首先,我们需要定义一个二叉树节点的结构体:
```
typedef struct TreeNode {
int data; // 节点数据
struct TreeNode *left; // 左子树指针
struct TreeNode *right; // 右子树指针
} TreeNode;
```
接着,我们可以用递归方式实现先序、中序和后序遍历:
```
// 先序遍历
void preorderTraversal(TreeNode *root) {
if (root == NULL) return;
printf("%d ", root->data); // 访问根节点
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
// 中序遍历
void inorderTraversal(TreeNode *root) {
if (root == NULL) return;
inorderTraversal(root->left); // 遍历左子树
printf("%d ", root->data); // 访问根节点
inorderTraversal(root->right); // 遍历右子树
}
// 后序遍历
void postorderTraversal(TreeNode *root) {
if (root == NULL) return;
postorderTraversal(root->left); // 遍历左子树
postorderTraversal(root->right); // 遍历右子树
printf("%d ", root->data); // 访问根节点
}
```
接下来,我们可以用队列实现层次遍历:
```
// 层次遍历
void levelTraversal(TreeNode *root) {
if (root == NULL) return;
Queue *queue = createQueue(); // 创建一个队列
enqueue(queue, root); // 根节点入队
int level = 0; // 当前层号初始化为0
while (!isEmpty(queue)) {
int size = getSize(queue); // 当前队列大小即为当前层节点数
printf("Level %d: ", level);
for (int i = 0; i < size; i++) {
TreeNode *node = dequeue(queue); // 队首节点出队
printf("%d ", node->data); // 访问队首节点
if (node->left != NULL) enqueue(queue, node->left); // 左子节点入队
if (node->right != NULL) enqueue(queue, node->right); // 右子节点入队
}
printf("\n");
level++; // 层号加1
}
}
```
最后,我们可以统计树叶数、结点数和层高:
```
// 统计树叶数
int countLeaves(TreeNode *root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1; // 叶节点
return countLeaves(root->left) + countLeaves(root->right);
}
// 统计结点数
int countNodes(TreeNode *root) {
if (root == NULL) return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
// 统计层高
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; // 返回更高的子树高度加1
}
```
这样,你就可以用这些函数来建立二叉树、遍历二叉树和统计信息了。
阅读全文