C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现

2024-09-07 03:28
文章标签 语言 实战 代码 二叉树 遍历 实现 深度 层序 构造 详细

本文主要是介绍C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树习题
1.通过前序序列和中序序列构造二叉树
2.通过层次遍历序列和中序序列创建一棵二叉树
3.求一棵二叉树的结点个数
4.求一棵二叉树的叶子节点数
5.求一棵二叉树中度为1的节点个数
6.求二叉树的高度
7.求一棵二叉树中值为x的节点作为根节点的子树深度
8.判断两棵树是否相似，相似返回1，不相似返回0
9.设计算法利用叶子结点中的空指针域将所有叶子结点链接成一个带头结的双链表
10.假设一个仅包含二元运算的算术表达式以二叉链表形式存放在二叉树T,设计算法求解算术表达式
11.判断二叉树是否为完全二叉树(二叉树的层序遍历)
12.求一棵二叉树的最大宽度

文章目录

  • 1.通过前序序列和中序序列构造二叉树
  • 2.通过层次遍历序列和中序序列创建一棵二叉树
  • 3.求一棵二叉树的结点个数
  • 4.求一棵二叉树的叶子节点数
  • 5.求一棵二叉树中度为1的节点个数
  • 6.求二叉树的高度
  • 7.求一棵二叉树中值为x的节点作为根节点的子树深度
  • 8.判断两棵树是否相似，相似返回1，不相似返回0
  • 9.设计算法利用叶子结点中的空指针域将所有叶子结点链接成一个带头结的双链表
  • 10.假设一个仅包含二元运算的算术表达式以二叉链表形式存放在二叉树T,设计算法求解算术表达式
  • 11.判断二叉树是否为完全二叉树(二叉树的层序遍历)
  • 12.求一棵二叉树的最大宽度

1.通过前序序列和中序序列构造二叉树

创建树的过程，就是明确子树的创建过程，明确子树的创建过程，就是明确根节点的创建过程

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;void preOrder(BiTree T)   //二叉树的前序遍历，传入一个二叉树
{if(T!=NULL)  //子树根节点不为空{printf("%c ",T->data);preOrder(T->lchild);preOrder(T->rchild);}
}BiTNode * creatBitree(ElemType preOrderList[],int preStartIndex,int preEndIndex,ElemType inOrderList[],int inStartIndex,int inEndIndex)
{//确定递归结束条件，先序序列循环一遍if(preStartIndex>preEndIndex){return NULL;}//创建一个根节点BiTNode *T=(BiTNode *)malloc(sizeof(BiTNode));T->data=preOrderList[preStartIndex];  //先序序列开始位置为根节点//找当前根节点在中序序列的位置，确定当前根节点的左右子树int rIndex=0;     //当前在中序遍历中找到的根节点的索引for(rIndex=inStartIndex;rIndex<=inEndIndex;rIndex++ ){if(inOrderList[rIndex]==T->data)break;}//此时要在中序序列中，确定左右子树//当前左子树，应该是instratIndex到rIndex-1//当前右子树，应该是rIndex+1到inEndIndex//此时的先序序列的左子树，preStartIndex+1到preStartIndex+length//先序序列的右子树，preStartIndex+length+1 preEndIndexint length=rIndex-inStartIndex;T->lchild=creatBitree(preOrderList, preStartIndex+1, preStartIndex+length, inOrderList, inStartIndex, rIndex-1);T->rchild= creatBitree(preOrderList, preStartIndex+length+1, preEndIndex, inOrderList, rIndex+1, inEndIndex);return T;  //把根节点返回回去
}int main() {char preOrderList[]={'A','B','D','E','C','F','G'};int preOrderListLength=7;char inOrderList[]={'D','B','E','A','F','C','G'};int inOrderListLength=7;BiTree T= creatBitree(preOrderList, 0, preOrderListLength-1, inOrderList, 0, inOrderListLength-1);preOrder(T);printf("\n");}

2.通过层次遍历序列和中序序列创建一棵二叉树

#include <stdio.h>
#include <stdlib.h>typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;void preOrder(BiTree T)   //二叉树的前序遍历，传入一个二叉树
{if(T!=NULL)  //子树根节点不为空{printf("%c ",T->data);preOrder(T->lchild);preOrder(T->rchild);}
}BiTNode * secend_creatBitree(char leverOrderList[],int LevelstartIndex,int LevelendIndex,char inOrderList[],int inStartIndex,int inEndIndex)
{if(LevelstartIndex>LevelendIndex) return NULL;// 创建根节点BiTNode *T=(BiTNode *)malloc(sizeof(BiTNode));T->data=leverOrderList[LevelstartIndex];int rIndex=inStartIndex;for(;rIndex<inEndIndex;rIndex++){if(T->data==inOrderList[rIndex])break;}//在层次遍历中，找到左子树和右子树，因为层次遍历中，寻找的过程是跳跃的，所以需要重新赋值左子树序列和右子树序列//外层循环是层次遍历的序列，因为层次遍历的顺序是不改变的，只是中间会有右子树的结点，会跳跃//内层循环是中序遍历的序列，依次和层次序列比较，声明新的数组存放当前新的左子树的层次遍历序列char lftLevelOrderList[100];int lftLevelOrderListlength=0;for(int j=LevelstartIndex+1;j<=LevelendIndex;j++){for(int i=inStartIndex;i<=rIndex-1;i++){if(leverOrderList[j]==inOrderList[i]){lftLevelOrderList[lftLevelOrderListlength++]=leverOrderList[j];}}}//同理右子树也是这么找的char rgtLevelOrderList[100];int rgtLevelOrderListlength=0;for(int j=LevelstartIndex+1;j<=LevelendIndex;j++){for(int i=rIndex+1;i<=inEndIndex;i++){if(leverOrderList[j]==inOrderList[i]){rgtLevelOrderList[rgtLevelOrderListlength++]=leverOrderList[j];}}}T->lchild=secend_creatBitree(lftLevelOrderList, 0, lftLevelOrderListlength-1, inOrderList, inStartIndex, rIndex-1);T->rchild=secend_creatBitree(rgtLevelOrderList, 0, rgtLevelOrderListlength-1, inOrderList,rIndex+1, inEndIndex);return T;
}int main() {char preOrderList[]={'A','B','D','E','C','F','G'};int preOrderListLength=7;char inOrderList[]={'D','B','E','A','F','C','G'};int inOrderListLength=7;char leverOrderList[]={'A','B','C','D','E','F','G'};int levelOrderListlength=7;BiTree T= secend_creatBitree(leverOrderList, 0, levelOrderListlength-1, inOrderList, 0, inOrderListLength-1);preOrder(T);printf("\n");}

3.求一棵二叉树的结点个数

思路如下:本质就是二叉树的遍历，每次访问到根的时候，用全局变量记录长度+1

int treelength=0;  //treelength是一个全局变量
void tree_length(BiTree T)
{if(T==NULL) return;treelength++;tree_length(T->lchild);tree_length(T->rchild);
}

4.求一棵二叉树的叶子节点数

思路:使用先序遍历访问二叉树的每一个结点，如果访问的结点为叶子结点，则二叉树叶子结点总数加1

int leafnodenum=0;  //这是全局变量
void leafnode_num(BiTree T)
{if(T==NULL) return;if(T->lchild==NULL&&T->rchild==NULL)leafnodenum++;leafnode_num(T->lchild);leafnode_num(T->rchild);
}

5.求一棵二叉树中度为1的节点个数

在这里插入图片描述 
int singlenodenum=0;void getSinglenodenum(BiTree T)
{if(T==NULL) return;if(T->lchild==NULL||T->rchild==NULL){if(T->lchild!=NULL||T->rchild!=NULL) singlenodenum++;}getSinglenodenum(T->lchild);getSinglenodenum(T->rchild);
}

6.求二叉树的高度

大总结：
关于二叉树的高度与二叉树的深度：

明确什么是高度什么是深度？

明确二叉树的高度用什么遍历，二叉树的深度用什么遍历？
二叉树的高度用后序遍历，子结点把它的高度返回给它的父节点。
二叉树的深度用前序遍历

二叉树的最大深度其实就是二叉树根节点的高度

求二叉树高度的模版

伪代码:
左 int leftheight=getheight(node->left);
右 int rightheight=getheight(node->right);
根 return 1+max(leftheight+rightheight);伪代码精简版(不推荐，因为没有后序的过程)
return 1+max(getheight(node->left),getheight(node->right))

实际代码如下:

int getheight(BiTree T)
{if(T==NULL) return 0;int leftheight=getheight(T->lchild);int rightheight=getheight(T->rchild);int hegiht=0;if(leftheight>=rightheight)hegiht=leftheight;else hegiht=rightheight;return hegiht+1;
}

利用三目运算符精简如下:

int getheight(BiTree T)
{if(T==NULL) return 0;int leftheight=getheight(T->lchild);int rightheight=getheight(T->rchild);return leftheight>rightheight?leftheight+1:rightheight+1;
}

7.求一棵二叉树中值为x的节点作为根节点的子树深度

思路如下：
找到二叉树中值为x的节点，若值不存在，则返回0，如存在，用计算二叉树的高度模板，找节点的深度。
数据检验：输入B，看是否=2

int getheight(BiTree T)
{if(T==NULL) return 0;int leftheight=getheight(T->lchild);int rightheight=getheight(T->rchild);return leftheight>rightheight?leftheight+1:rightheight+1;
}BiTNode * seek_node(BiTNode*T, char x)
{if(T==NULL) return NULL;if(T->data==x) return T;BiTNode *temp=seek_node(T->lchild, x);if(temp!=NULL) return temp;return seek_node(T->rchild, x);}主函数：if(seek_node(T, 'B')!=NULL){printf("子树深度为：%d",getheight(seek_node(T, 'B'))) ;}else{printf("没有该结点");}

复盘总结:

seek_node寻找二叉树中，值为x的结点
框架是二叉树的前序遍历，根节点那块用来判断
当判断为一棵子树的左子树后，要判断是否返回左子树的结果，因为左子树和右子树的结果要选择一个返回给他们的父亲，故需要判断左子树结果是否满足，满足就返回左子树，此时就不遍历他兄弟，也就是右子树，若不满足，也不需要判断左子树是否满足了，直接返回右子树即可。

深度思考：
1.目标节点是左子树的最左结点，他的返回过程是什么样的？
找到最左结点，返回它，此时一直传到根节点的左子树判断，存在不为空，返回它，函数结束

2.目标结点是左子树的最右结点，他的返回过程是什么样的？
每一层都会返回return T reutrn T

8.判断两棵树是否相似，相似返回1，不相似返回0

基本思路：

树的问题=根节点的解+左右子树的解
出口：考虑判断空树
根节点的解:
若两棵树都是空树，则他们相似，return 1
若一棵树是空树另一棵不是空树，则他们不相似，return 0
左右子树的解：
根节点的解判断完毕，判断左右子树的解
判断左子树是否相似，isSimilar(r->lchild); 相似得到1，不相似得到0
判断右子树是否相似，isSimilar(r->rchild); 相似得到1，不相似得到0
左右子树都相似才算相似,才是完整解
root1->lchild, root2->lchild) && isSimilar(root1->rchild, root2->rchild
return 左右子树的解

// 判断两棵二叉树是否相似
int isSimilar(BiTNode *root1, BiTNode *root2) {// 如果两棵树的节点都是空的，则它们相似if (root1 == NULL && root2 == NULL) {return 1;}// 如果一个节点为空，另一个节点不为空，则它们不相似if (root1 == NULL || root2 == NULL) {return 0;}// 递归判断左子树和右子树是否相似return isSimilar(root1->lchild, root2->lchild) && isSimilar(root1->rchild, root2->rchild);
}

9.设计算法利用叶子结点中的空指针域将所有叶子结点链接成一个带头结的双链表

注意：双链表一定要使用尾插

void preOrderTraverse(BiTNode *&tail,BiTree T)
{if(T==NULL) return;//判断根节点if(T->lchild==NULL&&T->rchild==NULL){T->lchild=tail;tail->rchild=T;tail=T;}else{preOrderTraverse(tail, T->lchild);preOrderTraverse(tail, T->rchild);}}主函数+测试// 定义一个链表表头和尾指针BiTNode *head=(BiTNode *)malloc(sizeof(BiTNode));head->lchild=NULL;head->rchild=NULL;BiTNode *tail=head;BiTNode *p=head;preOrderTraverse(tail, T);while(p->rchild!=NULL){printf("%c ",p->rchild->data);p=p->rchild;}printf("\n");

在这里插入图片描述

注意点:这个else，最开始写代码的过程中，我没有写else，实际上不能不写，如果不写，会出线传入NULL，NULL==NULL是无法被判断的

10.假设一个仅包含二元运算的算术表达式以二叉链表形式存放在二叉树T,设计算法求解算术表达式

在这里插入图片描述

层序遍历：* + 3 1 2
中序遍历: 1 + 2 * 3
构造数据

int operatorFunc(char oprt,int left,int right)
{switch (oprt) {case '+':return left+right;break;case '-':return left-right;break;case '*':return left*right;break;case '/':return left/right;break;default:return 0;}
}int getResult(BiTree T)
{//表达式求值，是唯一一个后序遍历if(T==NULL) return 0;if(T->lchild==NULL&&T->rchild==NULL) //如果节点是叶子节点 ，返回它的值{return T->data-'0';}else   //如果不是叶子节点，是操作符，操作它的左右子树{return operatorFunc(T->data, getResult(T->lchild), getResult(T->rchild));}
}

11.判断二叉树是否为完全二叉树(二叉树的层序遍历)

思路：二叉树的层序遍历模版来解决该问题，因为用层序遍历我们不难发现当二叉树层序遍历到空结点后完全二叉树后面都应该为空结点。

二叉树的层次遍历：

注意变量是树的结点，是地址，是存放地址的指针变量。

二叉树的层序遍历主要代码思路：
首先要创建一个队列，将头结点放入队列中。
然后开始循环，若队列为空，则结束遍历。
队列不为空，先拿出队头元素，用中间变量把它存储起来，输出中间变量的值，删除这个队头元素，将中间变量所指向的左右孩子加入进队列，直到循环结束。

注意几个判空，元素加入队列的时候要判空
首先就是要判断是否存在根节点，再加入队列。
其次是，在加入左右孩子结点时，要注意，别加入空指针。

typedef struct BiTNode
{ElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;typedef struct Queue
{BiTNode** Plist;  //该指针用于指向存储二叉树中每个结点地址的数组，该数组中的每个元素是一个地址int front;   //队头int rear; //队尾
}Queue;
//队列的建立
void initailQueue(Queue &Q)
{Q.Plist=(BiTNode**)malloc(sizeof(Queue)*100);Q.front=0;Q.rear=0;
}
//入队,循环队列
void enQueue(Queue &Q,BiTNode *e)
{Q.Plist[Q.rear]=e;Q.rear=(Q.rear+1)%100;
}
//出队
void deQueue(Queue &Q,BiTNode** e)
{*e=Q.Plist[Q.front];Q.front=(Q.front+1)%100;
}
//队列判空
int isemptyQueue(Queue Q)
{if(Q.front==Q.rear)return  1;else return 0;}
//当前队列的长度 头尾指针做差即可//二叉树的层序遍历开始
void levelOrderTraverse(BiTree T)
{Queue Q;initailQueue(Q);if(T!=NULL){enQueue(Q, T);}while(!isemptyQueue(Q)) //如果队列非空{//取出头结点front(),再pop()掉BiTNode *p=NULL;deQueue(Q,&p) ;   //注意这里的传入参数，是p指针的地址printf("%c ",p->data);  //这里开始输出层序遍历if(p->lchild!=NULL) enQueue(Q, p->lchild);          //子树不为空的时候加入子树if(p->lchild!=NULL) enQueue(Q, p->rchild);;}
}

问题的继续思考?

在该问题中，我们直接在循环中输出的二叉树，我们也可以声明一个动态数组，来储存每一次的结果，最后拿到主函数中，进行遍历输出。

判断二叉树是否为完全二叉树？
核心代码思路：
假如我们要加入队列的左右孩子结点，其中有空的，就弹出当前循环，以后再有结点加入队列，就不是完全二叉树。
在这里插入图片描述

给出一个非完全二叉树的例子：

在这里插入图片描述

int is_complete_bitree(BiTree T)
{//第一步，寻找第一个空树结点，用层序遍历Queue Q;initailQueue(Q);if(T!=NULL) enQueue(Q, T);while (!isemptyQueue(Q)) {BiTNode *p=NULL;deQueue(Q, &p);if(p->lchild!=NULL){enQueue(Q, p->lchild);}else{break;}if(p->rchild!=NULL){enQueue(Q, p->rchild);}else{break;}}  //找到了第一棵空子树while (!isemptyQueue(Q)) {BiTNode *p=NULL;deQueue(Q, &p);if(p->lchild!=NULL){return 0;}if(p->rchild!=NULL){return 0;}}    //若队列中，存在还有孩子的，就return 0//队列已为空return 1;
}

12.求一棵二叉树的最大宽度

二叉树的最大宽度，关键在于记录二叉树的是否同层的问题
该问题，是解决结点处理不同层结点问题的模版

原理图如下：
在这里插入图片描述

代码如下:

//二叉树的最大宽度
int max_bitree_width(BiTree T)
{Queue Q;initailQueue(Q);if(T!=NULL) enQueue(Q, T);int width_max=0;while(!isemptyQueue(Q)){int size=(Q.rear - Q.front + 100) % 100;   // size就是当前层的元素数if(size>width_max) width_max=size;for(int i=1;i<=size;i++){BiTNode *p=NULL;deQueue(Q, &p);if(p->lchild!=NULL) enQueue(Q,p->lchild);if(p->rchild!=NULL) enQueue(Q,p->rchild);}}return width_max;
}

这篇关于C语言手撕实战代码_二叉树_构造二叉树_层序遍历二叉树_二叉树深度的超详细代码实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
活用c4d官方开发文档查询代码

活用c4d官方开发文档查询代码

当你问AI助手比如豆包，如何用python禁止掉xpresso标签时候，它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2