根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。 二叉树的基本功能 ① 二叉树的建立; ② 前序遍历二叉树; ③ 中序遍历二叉树; ④ 后序遍历二叉树; ⑤ 按层序遍历二叉树 ⑥ 求二叉树的深度; ⑦
时间: 2023-09-14 22:07:43 浏览: 122
根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。
5星 · 资源好评率100%
二叉树的链式存储结构可以使用一个结构体来表示二叉树的节点,每个节点包含一个数据域和两个指针域指向左子树和右子树。建立二叉树时,可以采用递归的方法,先建立左子树,再建立右子树。
下面是使用 C 语言实现二叉树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 建立二叉树
void createTree(TreeNode **root) {
int val;
scanf("%d", &val);
if (val == -1) { // 输入 -1 表示该节点为空
*root = NULL;
} else {
*root = (TreeNode *) malloc(sizeof(TreeNode));
(*root)->data = val;
createTree(&((*root)->left));
createTree(&((*root)->right));
}
}
// 前序遍历二叉树
void preOrder(TreeNode *root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
// 中序遍历二叉树
void inOrder(TreeNode *root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
// 后序遍历二叉树
void postOrder(TreeNode *root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
// 按层序遍历二叉树
void levelOrder(TreeNode *root) {
if (root == NULL) return;
TreeNode *queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode *node = queue[front++];
printf("%d ", node->data);
if (node->left != NULL) queue[rear++] = node->left;
if (node->right != NULL) queue[rear++] = node->right;
}
}
// 求二叉树的深度
int depth(TreeNode *root) {
if (root == NULL) return 0;
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() {
TreeNode *root = NULL;
printf("请输入二叉树的节点,-1表示该节点为空:\n");
createTree(&root);
printf("前序遍历结果:");
preOrder(root);
printf("\n中序遍历结果:");
inOrder(root);
printf("\n后序遍历结果:");
postOrder(root);
printf("\n按层序遍历结果:");
levelOrder(root);
printf("\n二叉树的深度:%d\n", depth(root));
return 0;
}
```
以上代码实现了二叉树的建立、前序遍历、中序遍历、后序遍历、按层序遍历和求深度功能。
阅读全文