使用C语言实现一下功能.建立二叉树的二叉链表存储结构。2.实现二叉树的先序、中序和后序三种遍历操作(验证性内容)。3. 实现二叉树的先序、中序和后序遍历的非递归操作(选则完成其中一种遍历)。
时间: 2024-05-08 21:21:56 浏览: 115
实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
// 创建二叉树
Node *createBinaryTree() {
int data;
scanf("%d", &data);
if (data == 0) {
return NULL;
}
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->left = createBinaryTree();
node->right = createBinaryTree();
return node;
}
// 先序遍历(递归)
void preOrderTraversal(Node *node) {
if (node == NULL) {
return;
}
printf("%d ", node->data);
preOrderTraversal(node->left);
preOrderTraversal(node->right);
}
// 中序遍历(递归)
void inOrderTraversal(Node *node) {
if (node == NULL) {
return;
}
inOrderTraversal(node->left);
printf("%d ", node->data);
inOrderTraversal(node->right);
}
// 后序遍历(递归)
void postOrderTraversal(Node *node) {
if (node == NULL) {
return;
}
postOrderTraversal(node->left);
postOrderTraversal(node->right);
printf("%d ", node->data);
}
// 先序遍历(非递归)
void preOrderTraversalNonRecursive(Node *node) {
if (node == NULL) {
return;
}
Node *stack[100];
int top = 0;
stack[top++] = node;
while (top > 0) {
Node *current = stack[--top];
printf("%d ", current->data);
if (current->right != NULL) {
stack[top++] = current->right;
}
if (current->left != NULL) {
stack[top++] = current->left;
}
}
}
int main() {
printf("请输入二叉树的节点,以 0 结束:\n");
Node *root = createBinaryTree();
printf("先序遍历(递归)结果:");
preOrderTraversal(root);
printf("\n中序遍历(递归)结果:");
inOrderTraversal(root);
printf("\n后序遍历(递归)结果:");
postOrderTraversal(root);
printf("\n先序遍历(非递归)结果:");
preOrderTraversalNonRecursive(root);
return 0;
}
```
示例输入:
```
请输入二叉树的节点,以 0 结束:
1 2 0 0 3 4 0 0 5 0 0
```
示例输出:
```
先序遍历(递归)结果:1 2 3 4 5
中序遍历(递归)结果:2 1 4 3 5
后序遍历(递归)结果:2 4 5 3 1
先序遍历(非递归)结果:1 2 3 4 5
```
阅读全文