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。

相关文章

如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
Java调用DeepSeek API的最佳实践及详细代码示例

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》：本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.
阅读更多...
Spring AI集成DeepSeek的详细步骤

Spring AI集成DeepSeek的详细步骤

《SpringAI集成DeepSeek的详细步骤》DeepSeek作为一款卓越的国产AI模型,越来越多的公司考虑在自己的应用中集成,对于Java应用来说,我们可以借助SpringAI集成DeepSe... 目录DeepSeek 介绍Spring AI 是什么？1、环境准备2、构建项目2.1、pom依赖2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Python如何实现PDF隐私信息检测

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今，数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...
使用Python快速实现链接转word文档

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import
阅读更多...
前端原生js实现拖拽排课效果实例

前端原生js实现拖拽排课效果实例

《前端原生js实现拖拽排课效果实例》：本文主要介绍如何实现一个简单的课程表拖拽功能,通过HTML、CSS和JavaScript的配合,我们实现了课程项的拖拽、放置和显示功能,文中通过实例代码介绍的... 目录1. 效果展示2. 效果分析2.1 关键点2.2 实现方法3. 代码实现3.1 html部分3.2
阅读更多...
Goland debug失效详细解决步骤(合集)

Goland debug失效详细解决步骤(合集)

《Golanddebug失效详细解决步骤(合集)》今天用Goland开发时,打断点,以debug方式运行,发现程序并没有断住,程序跳过了断点,直接运行结束,网上搜寻了大量文章,最后得以解决,特此在这... 目录Bug：Goland debug失效详细解决步骤【合集】情况一：Go或Goland架构不对情况二：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2