13518219792
文章目录
前言
一、二叉树是什么？
二、二叉树的创建（以顺序表的形式）
1.先创建数组（为了顺序表做准备）
2.输入数值
3.输出数值
4.创建空二叉树并在二叉树中输入数值
5.判断是否为空二叉树
6.返回二叉树的深度
7.先序遍历输出二叉树
8.中序遍历输出二叉树
9.后序遍历输出二叉树
10.层序遍历输出二叉树
11.总结：（全部代码实现）
三、二叉树的基本操作（链表版本）
1.链表节点结构体
2.先序创建二叉树
1）中序后序创建二叉树
3.先序遍历二叉树
1）递归操作
2）非递归操作
4.中序遍历二叉树
1）递归操作
2）非递归操作
5.后序遍历二叉树
1）递归操作
2）非递归操作
6.求第k层节点的个数
7.求二叉树的深度
8.二叉树的叶子节点的个数
9.二叉树的总节点的个数
10.递归查找指定元素x的节点
11.全部代码：
总结
本文主要内容：
1.对于二叉树的基本操作，创建 、遍历 、前序、中序、后序输出等
2.关于二叉树的自己的体会
提示：以下是本篇文章正文内容，下面案例可供参考
二叉树是数据结构中的一种，可以通过顺序表或者链表的形式实现，接下来让我们一起来看看如何通过顺序表或者链表的形式来实现二叉树
二叉树图：
代码如下（示例）：
#define MAX_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_SIZE];
TElemType Nil = '#'; 我们规定当元素数值为 ‘#’ 的时候表示该节点为NULL代码如下（示例）：
void input(TElemType* x) {
scanf("%c", &x);
} 简单明了的传参 TElemType也就是char类型的变量 xvoid visit(TElemType x) {
printf("%c", x);
}void InitBiTree(SqBiTree T) {
//构造空二叉树
for (int i = 0; i< MAX_SIZE; i++) {
T[i] = Nil;//初始值为空 #表示为空
}
}
void CreateBiTree(SqBiTree T) {
int i = 1;//按照层次次序输入二叉树中结点的值
scanf("%s", T + 1);
while (T[i]!='\0')
{
i++;
}
T[i] = '#';
}int BiTreeEmpty(SqBiTree T) {
//初始条件：二叉树T存在。操作结果为：若T为空二叉树，则返回true 否则false
if (T[1] == Nil) {
return 1;//空
}
else {
return 0;
}
}//返回二叉树的深度
int BiTreeDepth(SqBiTree T) {
int i = MAX_SIZE - 1;
while (T[i] == '#') {
i--;
}
//现在得到的i是存储元素的最后一位
int j = i;
int dep = 0;
while (j >= 1) {
dep++;
j = j / 2;//根据的是树的深度为 【log2n】+1
}
return dep;
}这里的先序遍历是通过二叉树的一个性质来输出的，二叉树的性质之一：把完全二叉树的节点按照顺序写好对应坐标之后，i 节点的左右孩子的坐标位置分别为 2 * i 和 2 * i + 1；
void PreTraverse(SqBiTree T, int e) {
if (T[e] != '#') {
visit(T[e]);
PreTraverse(T, 2 * e);
PreTraverse(T, 2 * e + 1);//遍历输出结点 左子树 右子树
}
} 这个函数就涉及到二叉树的一个性质 通过2*e和2*e+1来进行遍历
void PreOrderTraverse(SqBiTree T) {
//先序遍历
if (!BiTreeEmpty(T)) {
//非空就调用PreTraverse
PreTraverse(T, 1);//从第一个元素就开始
}
printf("\n");
}
void InTraverse(SqBiTree T, int e) {
//中序遍历使用
if (T[e] != '#') {
InTraverse(T, 2 * e);
visit(T[e]);
InTraverse(T, 2 * e + 1);//中序遍历，先左后中再右
}
}
void InOrderTreaverse(SqBiTree T) {
if (!BiTreeEmpty(T)) {
InTraverse(T, 1);
}
printf("\n");
}//后序遍历
void PostTreaverse(SqBiTree T, int e) {
if (T[e] != '#') {
PostTreaverse(T, e * 2);
PostTreaverse(T, e * 2 + 1);
visit(T[e]);
}
}
void PostOrderTraverse(SqBiTree T) {
if (!BiTreeEmpty(T)){
PostTreaverse(T, 1);
}
printf("\n");
}//层序遍历二叉树
void LevelOrderTraverse(SqBiTree T) {
int dep = BiTreeDepth(T);
int tree_max = pow(dep, 2) - 1;//得到当前深度下完全二叉树应该有多少结点
for (int i = 1; i< tree_max; i++) {
if (T[i] == '#') {
continue;
}//不用输出‘#’ 而且获得的深度来看，不需要for很多没有价值的 下标 牛逼
visit(T[i]);
}
}#define _CRT_SECURE_NO_WARNINGS
#include#include#include#include//使用顺序结构完成二叉树的基本操作
//编写前序、中序、后序以及层次顺序遍历二叉树的算法，并计算二叉树的深度、所有的结点数
#define MAX_SIZE 100
typedef char TElemType;
typedef TElemType SqBiTree[MAX_SIZE];
TElemType Nil = '#';
void input(TElemType* x) {
scanf("%c", &x);
}
void visit(TElemType x) {
printf("%c", x);
}
void InitBiTree(SqBiTree T) {
//构造空二叉树
for (int i = 0; i< MAX_SIZE; i++) {
T[i] = Nil;//初始值为空 #表示为空
}
}
void CreateBiTree(SqBiTree T) {
int i = 1;//按照层次次序输入二叉树中结点的值
scanf("%s", T + 1);
while (T[i]!='\0')
{
i++;
}
T[i] = '#';
}
int BiTreeEmpty(SqBiTree T) {
//初始条件：二叉树T存在。操作结果为：若T为空二叉树，则返回true 否则false
if (T[1] == Nil) {
return 1;//空
}
else {
return 0;
}
}
//返回二叉树的深度
int BiTreeDepth(SqBiTree T) {
int i = MAX_SIZE - 1;
while (T[i] == '#') {
i--;
}
//现在得到的i是存储元素的最后一位
int j = i;
int dep = 0;
while (j >= 1) {
dep++;
j = j / 2;//根据的是树的深度为 【log2n】+1
}
return dep;
}
void PreTraverse(SqBiTree T, int e) {
if (T[e] != '#') {
visit(T[e]);
PreTraverse(T, 2 * e);
PreTraverse(T, 2 * e + 1);//遍历输出结点 左子树 右子树
}
}
void PreOrderTraverse(SqBiTree T) {
//先序遍历
if (!BiTreeEmpty(T)) {
//非空就调用PreTraverse
PreTraverse(T, 1);//从第一个元素就开始
}
printf("\n");
}
void InTraverse(SqBiTree T, int e) {
//中序遍历使用
if (T[e] != '#') {
InTraverse(T, 2 * e);
visit(T[e]);
InTraverse(T, 2 * e + 1);//中序遍历，先左后中再右
}
}
void InOrderTreaverse(SqBiTree T) {
if (!BiTreeEmpty(T)) {
InTraverse(T, 1);
}
printf("\n");
}
//后序遍历
void PostTreaverse(SqBiTree T, int e) {
if (T[e] != '#') {
PostTreaverse(T, e * 2);
PostTreaverse(T, e * 2 + 1);
visit(T[e]);
}
}
void PostOrderTraverse(SqBiTree T) {
if (!BiTreeEmpty(T)){
PostTreaverse(T, 1);
}
printf("\n");
}
//层序遍历二叉树
void LevelOrderTraverse(SqBiTree T) {
int dep = BiTreeDepth(T);
int tree_max = pow(dep, 2) - 1;//得到当前深度下完全二叉树应该有多少结点
for (int i = 1; i< tree_max; i++) {
if (T[i] == '#') {
continue;
}//不用输出‘#’ 而且获得的深度来看，不需要for很多没有价值的 下标 牛逼
visit(T[i]);
}
}
int main()
{
TElemType e;
SqBiTree Bt;
InitBiTree(Bt);
CreateBiTree(Bt);
printf("先序遍历结果为：");
PreOrderTraverse(Bt);
printf("中序遍历结果为：");
InOrderTreaverse(Bt);
printf("后序遍历结果为：");
PostOrderTraverse(Bt);
LevelOrderTraverse(Bt);
return 0;
} //使用链表的 形式来实现二叉树的基本操作
#define MaxSize 20
typedef struct TreeNode {
int data;//数据域
struct TreeNode* lchild;
struct TreeNode* rchild;//指向左右孩子结点
}BiNode,*BiTree;//先序创建二叉树
BiTree CreateTree() {
int data;
scanf("%d", &data); //这样每一次输入都会进行传值操作 直到输入的数值小于0然后开始右结点 使用递归的方法进行创建二叉树
BiTree root;
if (data<= 0) {
return NULL;
}
else {
root = (BiTree)malloc(sizeof(BiNode));
root->data = data;
root->lchild = CreateTree();
root->rchild = CreateTree();//先序传参 制造先序二叉树
}
return root;
}中序、后序创建二叉树的代码实现就是更改先序创建二叉树中的 root->data = data; 位置
更改递归的先后就可以，到这个地方大家应该就明白如何操作了（我看了一圈的csdn也没有多少人去说明这个事情，这是我在群里问了其他人的回复：更换递归和root->data = data；的位置）
3.先序遍历二叉树 1）递归操作所有的二叉树的遍历，不管先序、中序、后序，都可以通过递归的形式是实现。这个是最简单，最好理解的方式。在不强调不能使用递归的前提下，建议优先使用递归。
先序、中序、后序，只是跟上文那个什么序进行遍历创建二叉树一个道理，更改递归的位置即可~
//先序遍历
//1.递归操作 实现先序遍历
void PreTreeTraverse(BiTree root) {
if (root) {
//只要根节点不是空
printf("%d", root->data);
PreTreeTraverse(root->lchild);
PreTreeTraverse(root->rchild);
}
}非递归操作中，先序、中序、后序操作都有不同，所以这个比较难理解和记忆，但是有一个共同点是，都需要使用辅助栈的形式（定义一个类似于栈的 BiTree数组）！！！
这个写法大概思路是创建辅助栈，然后创建新节点，然后判断是否根节点为NULL（NULL的话不需要 遍历直接返回），设置栈数组的变量top 提前赋值为-1（任意都可以 按照个人习惯来），然后是top++（top现在为0）将root赋值给stack[0] 然后进入while循环（判断依据是栈中有没有元素 top>-1），因为是先序所以直接输出root节点数据，然后使用 if 语句判断是否有左右孩子（先判断右孩子的原因是，使得最后一个放进去的是左孩子节点，这样出栈的时候，是左孩子先出）
//2.非递归操作
//引入辅助栈
void PreOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root != NULL) {
//表示非空树
top++;
stack[top] = root;//将root放在stack数组中
//栈不空的时候循环
while (top >-1) { //这个写法牛逼的地方在于 首先是先输出根结点的数值然后出栈top--然后判断是否有右孩子，放进栈里面 然后
//出栈并访问结点 //这个时候如果有孩子的话 top>-1 还能进入while循环 然后输出左孩子（有的话）然后出栈 在判断这个孩子有没有左右孩子，一旦是没有了，你们前面压栈的右孩子就可以输出了
//输出右孩子之后，出栈 然后进行判断右孩子是由有左右孩子 模拟递归操纵s
p = stack[top];
top--;
printf("%d", p->data);
//右孩子入栈
if (p->rchild != NULL) {
top++;
stack[top] = p->rchild;
}
//左孩子入栈
if (p->lchild != NULL) {
top++;
stack[top] = p->rchild;
}
}
}
}
这个时候就能发现，有一定的规律在递归操作上
//有了先序遍历操作就可以写出来中序和后序遍历操作
//2.中序遍历
//1）递归操作
void InTreeTreaver(BiTree root) {
if (root) {
//判断根节点是否为空
InTreeTreaver(root->lchild);
printf("%d", root->data);
InTreeTreaver(root->rchild);
}
}//2)非递归
void InTreeTreaver2(BiTree root) {
//创建临时栈
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root) {
p = root;
while (top >-1 || p != NULL) {
//扫描所有的左孩子进栈 其实在左孩子进栈的过程中就只剩下右孩子
while (p != NULL) {
top++;
stack[top] = p;
p = p->lchild;
}
//扫描完成之后开始出栈
if (top >-1) {
p = stack[top];
printf("%d", p->data);
top--;
//扫描右孩子
p = p->rchild;
}
}
}
}//3.后序遍历
void PostTreeTraverse(BiTree root) {
if (root) {
PostTreeTraverse(root->lchild);
PostTreeTraverse(root->rchild);
printf("%d", root->data);
}
}//2)非递归
//后序遍历二叉树:非递归实现
void PostOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
int sign;
if (root != NULL) {
do {
//root节点入栈
while (root != NULL) {
top++;
stack[top] = root;
root = root->lchild;
}
//p指向栈顶前一个已访问节点
p = NULL;
//置root为已访问
sign = 1;
while (top != -1 && sign) {
//取出栈顶节点
root = stack[top];
//右孩子不存在或右孩子已访问则访问root
if (root->rchild == p) {
printf("%d ", root->data);
top--;
//p指向被访问的节点
p = root;
}
else {
//root指向右孩子节点
root = root->rchild;
//置未访问标记
sign = 0;
}
}
} while (top != -1);
}
}/遇到叶子节点 正好 因为你想要的是第k层 所以就k-1递归 然后等你到第k层的时候也就是k=1的时候 自然就返回1 了
你输入的第k层，在递归k-1次之后到达第k层，自然就返回1了 ，然后就得到对应第k层的数值了
int LevelNodeNum(BiTree root,int k) {
//进行判断是否为空 或者k数值不对
if (root == NULL || k< 1) {
return 0;
}
if (k == 1) {
return 1;//遇到叶子节点 正好 因为你想要的是第k层 所以就k-1递归 然后等你到第k层的时候也就是k=1的时候 自然就返回1 了
}
else {
return LevelNodeNum(root->lchild, k - 1) + LevelNodeNum(root->rchild,k - 1);
}
}//求二叉树的大深度
//使用递归的方式来实现
int maxTreeDeapth(BiTree root) {
if (root) {
int maxLeft = maxTreeDeapth(root->lchild);
int maxRight = maxTreeDeapth(root->rchild);
if (maxLeft >maxRight) {
return maxLeft + 1;
}
else {
return maxRight + 1;
}
}
return 0;
}//求二叉树叶子节点个数
int LeafNodeNum(BiTree root) {
//这一步是为了判断是否为空树 空树自然叶子节点为0
if (root == NULL) {
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) {
return 1;//叶子节点的特点 没有孩子 所以用递归 可以得到叶子节点的个数
}
else {
return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);
}
}求二叉树的叶子节点的个数和求总结点的个数，不同的是在使用递归的时候，如果是为了求叶子节点只需要在这个节点没有左右孩子的时候 return 1 在递归的时候不会+1
但是在求总结点个数的时候，使用递归的时候都会+1，这个+1表示的是加上这个节点了，其他方面没有不同
//二叉树的总节点个数
//使用递归的方法实现
int CountNode(BiTree root) {
if (root) {
if (root->lchild == NULL && root->rchild == NULL) {
return 1;//遇到叶子节点返回1
}
else {
return CountNode(root->lchild) + CountNode(root->rchild)+1;
//每一次正常运行都会加一并表示节点，直到遇到叶子节点返回数值1
}
}
}先进行左孩子递归一直找，找不到的时候就会使用右孩子递归了，如果再找不到就返回NULL，表示没有这个元素为x的节点
//查找元素为x的节点
//采用递归的方法
BiTree SearchNode(BiTree root, int x) {
if (root) {//这个是判断是否为NULL空树 第二是为了判断左右孩子是否为NULL
if (root->data == x) {
return root;//如果数据对了就返回相应节点
}
else {
BiTree p;//创建新节点位置
p = SearchNode(root->lchild, x);//使用遍历 先左孩子进行比较
if (!p) {//左孩子比较完成之后在进行右孩子递归比较 只要有有孩子就可以一直比较
p = SearchNode(root->rchild, x);
}
return p;
}
}
return NULL;
}#define _CRT_SECURE_NO_WARNINGS
#include#include#include#include//使用链表的 形式来实现二叉树的基本操作
#define MaxSize 20
typedef struct TreeNode {
int data;//数据域
struct TreeNode* lchild;
struct TreeNode* rchild;//指向左右孩子结点
}BiNode,*BiTree;
//我们规定，节点值必须为大于0的数值 ，如果是0表示奇数继续往下创建子节点的操作
//二叉树的操作通常使用递归的方法，二叉树的操作可以分为两类，一类是需要改变二叉树的结构，比如二叉树的创建，结点的删除等等
//这类操作，传入的二叉树的 结点参数为二叉树指针的地址，这种参数的传入，便于更改二叉树结构体的指针
//我们使用递归的方法创建左右子树
//第一种创建二叉树，使用一级指针
//先序创建二叉树
BiTree CreateTree() {
int data;
scanf("%d", &data); //这样每一次输入都会进行传值操作 直到输入的数值小于0然后开始右结点 使用递归的方法进行创建二叉树
BiTree root;
if (data<= 0) {
return NULL;
}
else {
root = (BiTree)malloc(sizeof(BiNode));
root->data = data;
root->lchild = CreateTree();
root->rchild = CreateTree();//先序传参 制造先序二叉树
}
return root;
}
//先序遍历
//1.递归操作 实现先序遍历
void PreTreeTraverse(BiTree root) {
if (root) {
//只要根节点不是空
printf("%d", root->data);
PreTreeTraverse(root->lchild);
PreTreeTraverse(root->rchild);
}
}
//2.非递归操作
//引入辅助栈
void PreOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root != NULL) {
//表示非空树
top++;
stack[top] = root;//将root放在stack数组中
//栈不空的时候循环
while (top >-1) { //这个写法牛逼的地方在于 首先是先输出根结点的数值然后出栈top--然后判断是否有右孩子，放进栈里面 然后
//出栈并访问结点 //这个时候如果有孩子的话 top>-1 还能进入while循环 然后输出左孩子（有的话）然后出栈 在判断这个孩子有没有左右孩子，一旦是没有了，你们前面压栈的右孩子就可以输出了
//输出右孩子之后，出栈 然后进行判断右孩子是由有左右孩子 模拟递归操纵s
p = stack[top];
top--;
printf("%d", p->data);
//右孩子入栈
if (p->rchild != NULL) {
top++;
stack[top] = p->rchild;
}
//左孩子入栈
if (p->lchild != NULL) {
top++;
stack[top] = p->rchild;
}
}
}
}
//有了先序遍历操作就可以写出来中序和后序遍历操作
//2.中序遍历
//1）递归操作
void InTreeTreaver(BiTree root) {
if (root) {
//判断根节点是否为空
InTreeTreaver(root->lchild);
printf("%d", root->data);
InTreeTreaver(root->rchild);
}
}
//2)非递归
void InTreeTreaver2(BiTree root) {
//创建临时栈
BiTree stack[MaxSize];
BiTree p;
int top = -1;
if (root) {
p = root;
while (top >-1 || p != NULL) {
//扫描所有的左孩子进栈 其实在左孩子进栈的过程中就只剩下右孩子
while (p != NULL) {
top++;
stack[top] = p;
p = p->lchild;
}
//扫描完成之后开始出栈
if (top >-1) {
p = stack[top];
printf("%d", p->data);
top--;
//扫描右孩子
p = p->rchild;
}
}
}
}
//3.后序遍历
void PostTreeTraverse(BiTree root) {
if (root) {
PostTreeTraverse(root->lchild);
PostTreeTraverse(root->rchild);
printf("%d", root->data);
}
}
//2)非递归
//后序遍历二叉树:非递归实现
void PostOrderTraverseNonRec(BiTree root) {
BiTree stack[MaxSize];
BiTree p;
int top = -1;
int sign;
if (root != NULL) {
do {
//root节点入栈
while (root != NULL) {
top++;
stack[top] = root;
root = root->lchild;
}
//p指向栈顶前一个已访问节点
p = NULL;
//置root为已访问
sign = 1;
while (top != -1 && sign) {
//取出栈顶节点
root = stack[top];
//右孩子不存在或右孩子已访问则访问root
if (root->rchild == p) {
printf("%d ", root->data);
top--;
//p指向被访问的节点
p = root;
}
else {
//root指向右孩子节点
root = root->rchild;
//置未访问标记
sign = 0;
}
}
} while (top != -1);
}
}
//求二叉树的大深度
//使用递归的方式来实现
int maxTreeDeapth(BiTree root) {
if (root) {
int maxLeft = maxTreeDeapth(root->lchild);
int maxRight = maxTreeDeapth(root->rchild);
if (maxLeft >maxRight) {
return maxLeft + 1;
}
else {
return maxRight + 1;
}
}
return 0;
}
//求二叉树叶子节点个数
int LeafNodeNum(BiTree root) {
//这一步是为了判断是否为空树 空树自然叶子节点为0
if (root == NULL) {
return 0;
}
if (root->lchild == NULL && root->rchild == NULL) {
return 1;//叶子节点的特点 没有孩子 所以用递归 可以得到叶子节点的个数
}
else {
return LeafNodeNum(root->lchild) + LeafNodeNum(root->rchild);
}
}
////// 求k层节点个数
/// /// 1. 对于二叉树的学习，我已经使用过了顺序表的形式和链表的形式，感觉上，第一次在二叉树上发现了递归的神奇用处，之前使用的递归的时候都是一些很小的问题的解决，这一次在二叉树的遍历上面，无论是如何实现的二叉树，在进行先序、中序、后序等遍历的时候，使用递归的方法是最为简单，也是最好理解的。
2.虽然在学过Java之后觉得C为基础的数据结构真的好麻烦，Java会有相应的框架，一时畏难心理就有了，但是在最近的学习来看，数据结构是一门很有意思的课程，在这个地方，感受到数据结构的魅力，希望大家不要畏难，感受敲完代码理解代码的那一刻的快乐，大家加油！！！
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
