【数据结构C/C++】顺序与链式二叉树创建与前中后、层序遍历

2023-10-11 06:01
文章标签 二叉树 遍历 c++ 数据结构 创建 层序 顺序 链式 中后

本文主要是介绍【数据结构C/C++】顺序与链式二叉树创建与前中后、层序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 顺序存储结构二叉树
  • 链式存储结构二叉树
  • 刷题推荐
  • 408考研各数据结构C/C++代码（Continually updating）

顺序存储结构二叉树

顺序存储结构的二叉树的特点在于，其使用数组存放二叉树中的每一个节点。
我们设定根节点的数组索引下标为n（n>=1），那么有当前根节点的左子树节点在数组中的下标为2n，右子树在数组中的下标为2n+1。
上面是顺序存储结构二叉树的最最最重要的一个特性，我们后面的所有操作都基于这个理论。
相对于比较简单的对于链式存储结构的二叉树的遍历，以及计算最大二叉树深度，链式存储结构都会更加接单，而顺序存储结构则需要考虑到当前节点是否为空，并且当前索引是否超出了树当前最大的节点个数。

LeetCode计算二叉树最大深度
在这里插入图片描述

这里我不推荐你花大把时间去实现一个顺序存储结构的二叉树的层序遍历，因为我们知道，层序遍历一般的解法都是配合一个队列或者栈来实现的。
我在写Java的时候一般都会使用Deque也就是双端队列来实现，但是C语言并没有提供这样子的功能，你还得手动实现，比较费时，因此我不太推荐。
当然，有兴趣的可以去刷一下LeetCode链式存储结构的层序遍历，还是比较常见的。

先附上一张代码运行的图片。
在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>#define MaxSize 100typedef char TreeNodeType;//二叉树结构
typedef struct
{TreeNodeType data[MaxSize];int BiTreeNum;
} BinaryTree;// 声明队列数据结构
typedef struct
{int front, rear;int size;int capacity;int *array;
} Queue;void initTree(BinaryTree *T);
void createTree(BinaryTree *T, int n);
TreeNodeType rootTree(BinaryTree *T);
int countTree(BinaryTree *T);
int maxDepthOfTree(BinaryTree *T, int n);
void preOrderTraverse(BinaryTree *T, int n);
void inOrderTraverse(BinaryTree *T, int n);
void postOrderTraverse(BinaryTree *T, int n);
void levelOrderTraverse(BinaryTree *T); // 层序遍历
bool destoryTree(BinaryTree *T);
void traverseArray(BinaryTree *T); // 遍历数组// 队列相关函数
Queue *createQueue(int capacity);
bool isQueueEmpty(Queue *queue);
bool isQueueFull(Queue *queue);
void enqueue(Queue *queue, int item);
int dequeue(Queue *queue);int main()
{BinaryTree T;// 开始构造二叉树 其中使用1作为根节点下标// 而不是使用0，使用0的问题在于不好表示数据在数组中的位置// 我们知道二叉树满足 当前节点n的左子树和右子树的序列号应该为 2n和2n+1initTree(&T);printf("请输入根结点(输入#表示该结点为空):");createTree(&T, 1);traverseArray(&T);printf("当前二叉树的最大深度为：%d\n", maxDepthOfTree(&T, 1));printf("先序遍历：");preOrderTraverse(&T, 1);printf("\n");printf("中序遍历：");inOrderTraverse(&T, 1);printf("\n");printf("后序遍历：");postOrderTraverse(&T, 1);printf("\n");printf("层序遍历：");levelOrderTraverse(&T);printf("\n");return 0;
}void initTree(BinaryTree *T)
{int i;for (i = 0; i < MaxSize; ++i){T->data[i] = '\0';}T->BiTreeNum = 0;return;
}void createTree(BinaryTree *T, int n)
{char ch;// 刷新（清空）标准输入流（stdin）// 主打一个求稳fflush(stdin);// 输入当前节点信息 # 代表当前节点为空// 先构造过字数scanf(" %c", &ch);if (ch == '#'){ // 空直接返回return;}else{T->data[n] = ch;T->BiTreeNum++;printf("输入 %c 的左子树数据（输入#表示当前左子树为空: ", ch);// 这里有一个技巧createTree(T, 2 * n);printf("输入 %c 的右子树数据（输入#表示当前右边子树为空）: ", ch);createTree(T, (2 * n + 1));}
}// 计算二叉树的最大深度
// 从根节点到叶子节点的最长路径的长度
// 由于是顺序结构 因此这里从第一层也就是n=1开始向下遍历
// 然后不断的判断左子树和右子树的高度
// 最后取最大值
int maxDepthOfTree(BinaryTree *T, int n)
{if (n <= T->BiTreeNum && T->data[n] != '\0'){int leftDepth = maxDepthOfTree(T, 2 * n);int rightDepth = maxDepthOfTree(T, 2 * n + 1);return 1 + fmax(leftDepth, rightDepth);}else{return 0;}
}//先序遍历 根左右
void preOrderTraverse(BinaryTree *T, int n)
{if (T->data[n] == '\0')return;else{printf("%c ", T->data[n]);preOrderTraverse(T, 2 * n);preOrderTraverse(T, (2 * n + 1));}
}
//中序遍历 左根由7
void inOrderTraverse(BinaryTree *T, int n)
{if (T->data[n] == '\0')return;else{inOrderTraverse(T, 2 * n);printf("%c ", T->data[n]);inOrderTraverse(T, (2 * n + 1));}
}
//后序遍历  左右根
void postOrderTraverse(BinaryTree *T, int n)
{if (T->data[n] == '\0')return;else{postOrderTraverse(T, 2 * n);postOrderTraverse(T, (2 * n + 1));printf("%c ", T->data[n]);}
}
void traverseArray(BinaryTree *T){for(int i=1;i<=T->BiTreeNum;i++){printf("%c  ",T->data[i]);}printf("\n");
}// 层序遍历二叉树
void levelOrderTraverse(BinaryTree *T)
{if (T->BiTreeNum == 0){printf("二叉树为空\n");return;}//创建一个队列存放当前层Queue *queue = createQueue(T->BiTreeNum);int current = 1; // 从根节点开始//结束条件while (current <= T->BiTreeNum){printf("%c ", T->data[current]);//判断左子树是否存在 存在就放入队列if (2 * current <= T->BiTreeNum && T->data[2 * current] != '\0'){enqueue(queue, 2 * current);}//判断右子树是否存在 存在就放入队列if (2 * current + 1 <= T->BiTreeNum && T->data[2 * current + 1] != '\0'){enqueue(queue, 2 * current + 1);}//出队对头 if (!isQueueEmpty(queue)){current = dequeue(queue);}else{break;}}//使用完毕释放空间free(queue->array);free(queue);
}// 创建队列
Queue *createQueue(int capacity)
{Queue *queue = (Queue *)malloc(sizeof(Queue));if (!queue){perror("内存分配失败");exit(EXIT_FAILURE);}queue->front = 0;queue->rear = -1;queue->size = 0;queue->capacity = capacity;queue->array = (int *)malloc(capacity * sizeof(int));if (!queue->array){perror("内存分配失败");exit(EXIT_FAILURE);}return queue;
}// 检查队列是否为空
bool isQueueEmpty(Queue *queue)
{return (queue->size == 0);
}// 检查队列是否已满
bool isQueueFull(Queue *queue)
{return (queue->size == queue->capacity);
}// 入队列
void enqueue(Queue *queue, int item)
{if (isQueueFull(queue)){printf("队列已满\n");return;}queue->rear = (queue->rear + 1) % queue->capacity;queue->array[queue->rear] = item;queue->size++;
}// 出队列
int dequeue(Queue *queue)
{if (isQueueEmpty(queue)){printf("队列为空\n");return -1;}int item = queue->array[queue->front];queue->front = (queue->front + 1) % queue->capacity;queue->size--;return item;
}

链式存储结构二叉树

链式存储结构构造一个二叉树就比较简单，并且无论是遍历操作还是追求最大深度，都可以比较容易的求解。
其主要的重点在于结构体的定义，链式存储结构的精髓在于，左右指针域。

// 定义二叉树结点结构
typedef struct TreeNode
{int data;struct TreeNode *left; //左右指针struct TreeNode *right;
} TreeNode;

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>#define MaxSize 100
// 定义二叉树结点结构
typedef struct TreeNode
{int data;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 函数声明
TreeNode *createNode(int data);
TreeNode *insert(TreeNode *root, int data);
TreeNode *search(TreeNode *root, int data);
TreeNode *findMin(TreeNode *root);
TreeNode *deleteNode(TreeNode *root, int data);
void preorderTraversal(TreeNode *root);
void inorderTraversal(TreeNode *root);
void postorderTraversal(TreeNode *root);
int maxDepthOfTree(TreeNode *root);
void levelOrderTraversal(TreeNode *root);TreeNode *root = NULL;int main()
{int choice, data;printf("基于链式存储结构的二叉树操作：\n");while (1){printf("\n请选择操作：\n");printf("1. 插入\n");printf("2. 删除\n");printf("3. 查找\n");printf("4. 层序遍历\n");scanf("%d", &choice);switch (choice){case 1:printf("输入要插入的数据: ");scanf("%d", &data);root = insert(root, data);printf("前序遍历结果为：");preorderTraversal(root);printf("中序遍历结果为：");inorderTraversal(root);printf("后序遍历结果为：");postorderTraversal(root);printf("二叉树最大深度为：%d\n", maxDepthOfTree(root));break;case 2:printf("输入要删除的数据: ");scanf("%d", &data);root = deleteNode(root, data);printf("前序遍历结果为：");preorderTraversal(root);printf("中序遍历结果为：");inorderTraversal(root);printf("后序遍历结果为：");postorderTraversal(root);printf("二叉树最大深度为：%d\n", maxDepthOfTree(root));break;case 3:printf("输入要查找的数据: ");scanf("%d", &data);TreeNode *result = search(root, data);if (result != NULL){printf("找到了 %d\n", result->data);}else{printf("未找到 %d\n", data);}printf("前序遍历结果为：");preorderTraversal(root);printf("中序遍历结果为：");inorderTraversal(root);printf("后序遍历结果为：");postorderTraversal(root);printf("二叉树最大深度为：%d\n", maxDepthOfTree(root));break;case 4:printf("层序遍历结果为：");levelOrderTraversal(root);printf("\n");break;}}return 0;
}// 创建新的二叉树结点
TreeNode *createNode(int data)
{TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));if (newNode == NULL){perror("内存分配失败");exit(EXIT_FAILURE);}newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}// 插入结点
TreeNode *insert(TreeNode *root, int data)
{if (root == NULL){return createNode(data);}if (data < root->data){root->left = insert(root->left, data);}else if (data > root->data){root->right = insert(root->right, data);}return root;
}// 查找结点
TreeNode *search(TreeNode *root, int data)
{if (root == NULL || root->data == data){return root;}if (data < root->data){return search(root->left, data);}else{return search(root->right, data);}
}// 找到最小值结点
TreeNode *findMin(TreeNode *root)
{while (root->left != NULL){root = root->left;}return root;
}// 删除结点
TreeNode *deleteNode(TreeNode *root, int data)
{if (root == NULL){return root;}if (data < root->data){root->left = deleteNode(root->left, data);}else if (data > root->data){root->right = deleteNode(root->right, data);}else{// 结点有一个子结点或没有子结点if (root->left == NULL){TreeNode *temp = root->right;free(root);return temp;}else if (root->right == NULL){TreeNode *temp = root->left;free(root);return temp;}// 结点有两个子结点，找到中序遍历的后继结点（右子树中的最小值）TreeNode *temp = findMin(root->right);root->data = temp->data;root->right = deleteNode(root->right, temp->data);}return root;
}// 前序遍历
void preorderTraversal(TreeNode *root)
{if (root != NULL){printf("%d ", root->data);preorderTraversal(root->left);preorderTraversal(root->right);}
}// 中序遍历
void inorderTraversal(TreeNode *root)
{if (root != NULL){inorderTraversal(root->left);printf("%d ", root->data);inorderTraversal(root->right);}
}// 后序遍历
void postorderTraversal(TreeNode *root)
{if (root != NULL){postorderTraversal(root->left);postorderTraversal(root->right);printf("%d ", root->data);}
}// 计算二叉树的最大深度
int maxDepthOfTree(TreeNode *root)
{if (root == NULL){return 0;}else{int leftHeight = maxDepthOfTree(root->left);int rightHeight = maxDepthOfTree(root->right);return fmax(leftHeight, rightHeight) + 1;}
}// 层序遍历
void levelOrderTraversal(TreeNode *root)
{if (root == NULL){return;}// 创建一个队列用于层序遍历TreeNode *queue[MaxSize];int front = 0, rear = 0;queue[rear++] = root; // 根结点入队while (front < rear){TreeNode *current = queue[front++];printf("%d ", current->data);// 左子结点入队if (current->left != NULL){queue[rear++] = current->left;}// 右子结点入队if (current->right != NULL){queue[rear++] = current->right;}}
}

刷题推荐

LeetCode树类型题目
树类型的题目其实是我刷的最多的，因为其实只要找到规律了，做起来就最快，直接往递归这一条路上去考虑即可。
在这里插入图片描述

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。

这篇关于【数据结构C/C++】顺序与链式二叉树创建与前中后、层序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/186059。

相关文章

解决IDEA使用springBoot创建项目,lombok标注实体类后编译无报错,但是运行时报错问题

解决IDEA使用springBoot创建项目,lombok标注实体类后编译无报错,但是运行时报错问题

《解决IDEA使用springBoot创建项目,lombok标注实体类后编译无报错,但是运行时报错问题》文章详细描述了在使用lombok的@Data注解标注实体类时遇到编译无误但运行时报错的问题,分析... 目录问题分析问题解决方案步骤一步骤二步骤三总结问题使用lombok注解@Data标注实体类，编译时
阅读更多...
C++中使用vector存储并遍历数据的基本步骤

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库（STL）提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,：本文主要介绍C... 目录（1）容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌（基于哈希表）：‌容器适配器‌：（
阅读更多...
MySQL分表自动化创建的实现方案

MySQL分表自动化创建的实现方案

《MySQL分表自动化创建的实现方案》在数据库应用场景中,随着数据量的不断增长,单表存储数据可能会面临性能瓶颈,例如查询、插入、更新等操作的效率会逐渐降低,分表是一种有效的优化策略,它将数据分散存储在... 目录一、项目目的二、实现过程（一）mysql 事件调度器结合存储过程方式1. 开启事件调度器2. 创
阅读更多...
mysql外键创建不成功/失效如何处理

mysql外键创建不成功/失效如何处理

《mysql外键创建不成功/失效如何处理》文章介绍了在MySQL5.5.40版本中,创建带有外键约束的`stu`和`grade`表时遇到的问题,发现`grade`表的`id`字段没有随着`studen... 当前mysql版本：SELECT VERSION();结果为：5.5.40。在复习mysql外键约
阅读更多...
Window Server创建2台服务器的故障转移群集的图文教程

Window Server创建2台服务器的故障转移群集的图文教程

《WindowServer创建2台服务器的故障转移群集的图文教程》本文主要介绍了在WindowsServer系统上创建一个包含两台成员服务器的故障转移群集,文中通过图文示例介绍的非常详细,对大家的... 目录一、 准备条件二、在ServerB安装故障转移群集三、在ServerC安装故障转移群集，操作与Ser
阅读更多...
Window Server2016 AD域的创建的方法步骤

Window Server2016 AD域的创建的方法步骤

《WindowServer2016AD域的创建的方法步骤》本文主要介绍了WindowServer2016AD域的创建的方法步骤,文中通过图文介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、准备条件二、在ServerA服务器中常见AD域管理器：三、创建AD域，域地址为“test.ly”
阅读更多...
C++中实现调试日志输出

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳：精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC
阅读更多...
Python在固定文件夹批量创建固定后缀的文件(方法详解)

Python在固定文件夹批量创建固定后缀的文件(方法详解)

《Python在固定文件夹批量创建固定后缀的文件(方法详解)》文章讲述了如何使用Python批量创建后缀为.md的文件夹,生成100个,代码中需要修改的路径、前缀和后缀名,并提供了注意事项和代码示例,... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果5.
阅读更多...
使用IntelliJ IDEA创建简单的Java Web项目完整步骤

使用IntelliJ IDEA创建简单的Java Web项目完整步骤

《使用IntelliJIDEA创建简单的JavaWeb项目完整步骤》：本文主要介绍如何使用IntelliJIDEA创建一个简单的JavaWeb项目,实现登录、注册和查看用户列表功能,使用Se... 目录前置准备项目功能实现步骤1. 创建项目2. 配置 Tomcat3. 项目文件结构4. 创建数据库和表5.
阅读更多...
使用SpringBoot创建一个RESTful API的详细步骤

使用SpringBoot创建一个RESTful API的详细步骤

《使用SpringBoot创建一个RESTfulAPI的详细步骤》使用Java的SpringBoot创建RESTfulAPI可以满足多种开发场景,它提供了快速开发、易于配置、可扩展、可维护的优点,尤... 目录一、创建 Spring Boot 项目二、创建控制器类（Controller Class）三、运行
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2