AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-09-09 67
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为1的节点数量、二叉树高度、特定节点子树深度、判断两棵树是否相似、将叶子节点链接成双向链表、计算算术表达式的值、判断是否为完全二叉树以及求二叉树的最大宽度等。每道题目均提供了详细的算法思路及相应的C/C++代码实现，帮助读者理解和掌握二叉树的基本操作与应用。
二叉树习题
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 preEndIndex
    int 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
```c
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的节点个数

```c
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.判断二叉树是否为完全二叉树(二叉树的层序遍历)

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

二叉树的层次遍历：

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

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

注意几个判空，元素加入队列的时候要判空
首先就是要判断是否存在根节点，再加入队列。
其次是，在加入左右孩子结点时，要注意，别加入空指针。
```cpp
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);;

}

}

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


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


```c
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语言
算法
存储
C++
关键词：
C语言代码
C语言实战
C语言二叉树
C语言实战代码
C语言层序遍历
小徐在进步
目录
相关文章
XIAZHI
|
1月前
|
存储 安全 数据管理
C语言之考勤模拟系统平台（千行代码）
C语言之考勤模拟系统平台（千行代码）
XIAZHI
51 4
c的前世今生
|
21天前
|
存储 算法 程序员
C 语言递归算法：以简洁代码驾驭复杂逻辑
C语言递归算法简介：通过简洁的代码实现复杂的逻辑处理，递归函数自我调用解决分层问题，高效而优雅。适用于树形结构遍历、数学计算等领域。
c的前世今生
41 7
c的前世今生
|
28天前
|
存储 安全 物联网
C语言物联网开发之设备安全与代码可靠性隐患
物联网设备的C语言代码安全与可靠性至关重要。一是防范代码安全漏洞，包括缓冲区溢出和代码注入风险，通过使用安全函数和严格输入验证来预防。二是提高代码跨平台兼容性，利用`stdint.h`定义统一的数据类型，并通过硬件接口抽象与适配减少平台间的差异，确保程序稳定运行。
c的前世今生
42 9
土木林森
|
22天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
52 1
ephemerals__
|
1月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
131 8
阿客不是客
|
2月前
|
存储 搜索推荐 C语言
深入C语言指针，使代码更加灵活（二）
深入C语言指针，使代码更加灵活（二）
阿客不是客
38 2
阿客不是客
|
2月前
|
存储 程序员 编译器
深入C语言指针，使代码更加灵活（一）
深入C语言指针，使代码更加灵活（一）
阿客不是客
39 2
阿客不是客
|
2月前
|
C语言
深入C语言指针，使代码更加灵活（三）
深入C语言指针，使代码更加灵活（三）
阿客不是客
26 0
深入C语言指针，使代码更加灵活（三）
kgmh2cwvierzy
|
3月前
|
安全 C语言
在C语言中，正确使用运算符能提升代码的可读性和效率
在C语言中，运算符的使用需要注意优先级、结合性、自增自减的形式、逻辑运算的短路特性、位运算的类型、条件运算的可读性、类型转换以及使用括号来明确运算顺序。掌握这些注意事项可以帮助编写出更安全和高效的代码。
kgmh2cwvierzy
61 4
小徐在进步
|
3月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配，利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题，要求判断输入字符串中的括号是否正确匹配，并给出了完整的代码示例。此外，还探讨了栈在表达式求值中的应用，包括中缀、后缀和前缀表达式的转换与计算方法。最后，文章介绍了矩阵的压缩存储技术，涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略，提高存储效率。
小徐在进步
479 8