c语言生成一个完全二叉树,并分别按照前序遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序输出显示二叉树各结点的信息。
时间: 2024-11-21 10:30:49 浏览: 24
C语言二叉树的三种遍历方式的实现及原理
5星 · 资源好评率100%
在C语言中,我们可以使用递归的方式来生成一个完全二叉树并对其进行遍历。这里我将提供一个简单的例子,首先我们需要创建一个结构体表示二叉树节点:
```c
#include <stdio.h>
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左子节点指针
struct TreeNode* right; // 右子节点指针
} TreeNode;
```
生成完全二叉树的函数可以这样实现:
```c
TreeNode* createCompleteTree(int n) {
if (n <= 0) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1; // 根节点通常是第一个元素
int i = 2, level = 2;
while (i <= n) {
if (level % 2 == 1) { // 非空层,从左到右插入
while (root->left != NULL && i > 0) {
root = root->left;
i--;
}
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = i++;
} else { // 空层,从右到左插入
while (root->right != NULL && i > 0) {
root = root->right;
i--;
}
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = i++;
}
level++;
}
return root;
}
```
接下来,我们编写三个遍历函数:
1. 前序遍历(根-左-右):
```c
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
```
2. 中序遍历(左-根-右):
```c
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->val);
inOrderTraversal(root->right);
}
}
```
3. 后序遍历(左-右-根):
```c
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->val);
}
}
```
最后,你可以这样使用这些函数:
```c
int main() {
int n = 5; // 指定完全二叉树的节点数
TreeNode* tree = createCompleteTree(n);
printf("Preorder traversal: ");
preOrderTraversal(tree); // 输出前序遍历结果
printf("\nInorder traversal: ");
inOrderTraversal(tree); // 输出中序遍历结果
printf("\nPostorder traversal: ");
postOrderTraversal(tree); // 输出后序遍历结果
freeRecursive(tree); // 自定义的释放内存函数
return 0;
}
// 自定义释放内存的辅助函数
void freeRecursive(TreeNode* node) {
if (node == NULL) return;
freeRecursive(node->left);
freeRecursive(node->right);
free(node);
}
```
阅读全文