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

简介: 这段代码和文本介绍了一系列二叉树相关的问题及其解决方案。其中包括根据前序和中序序列构建二叉树、通过层次遍历序列和中序序列创建二叉树、计算二叉树节点数量、叶子节点数量、度为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;
}
相关文章
|
12天前
|
安全 C语言
在C语言中,正确使用运算符能提升代码的可读性和效率
在C语言中,运算符的使用需要注意优先级、结合性、自增自减的形式、逻辑运算的短路特性、位运算的类型、条件运算的可读性、类型转换以及使用括号来明确运算顺序。掌握这些注意事项可以帮助编写出更安全和高效的代码。
25 4
|
27天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
29天前
|
存储 算法 C语言
C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解
这份二叉排序树习题集涵盖了二叉搜索树(BST)的基本操作,包括构建、查找、删除等核心功能。通过多个具体示例,如构建BST、查找节点所在层数、删除特定节点及查找小于某个关键字的所有节点等,帮助读者深入理解二叉排序树的工作原理与应用技巧。此外,还介绍了如何将一棵二叉树分解为两棵满足特定条件的BST,以及删除所有关键字小于指定值的节点等高级操作。每个题目均配有详细解释与代码实现,便于学习与实践。
|
29天前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
29天前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。
|
29天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
26天前
|
存储 Serverless C语言
【C语言基础考研向】11 gets函数与puts函数及str系列字符串操作函数
本文介绍了C语言中的`gets`和`puts`函数,`gets`用于从标准输入读取字符串直至换行符,并自动添加字符串结束标志`\0`。`puts`则用于向标准输出打印字符串并自动换行。此外,文章还详细讲解了`str`系列字符串操作函数,包括统计字符串长度的`strlen`、复制字符串的`strcpy`、比较字符串的`strcmp`以及拼接字符串的`strcat`。通过示例代码展示了这些函数的具体应用及注意事项。
|
29天前
|
存储 C语言
C语言程序设计核心详解 第十章:位运算和c语言文件操作详解_文件操作函数
本文详细介绍了C语言中的位运算和文件操作。位运算包括按位与、或、异或、取反、左移和右移等六种运算符及其复合赋值运算符,每种运算符的功能和应用场景都有具体说明。文件操作部分则涵盖了文件的概念、分类、文件类型指针、文件的打开与关闭、读写操作及当前读写位置的调整等内容,提供了丰富的示例帮助理解。通过对本文的学习,读者可以全面掌握C语言中的位运算和文件处理技术。
|
29天前
|
存储 C语言
C语言程序设计核心详解 第七章 函数和预编译命令
本章介绍C语言中的函数定义与使用,以及预编译命令。主要内容包括函数的定义格式、调用方式和示例分析。C程序结构分为`main()`单框架或多子函数框架。函数不能嵌套定义但可互相调用。变量具有类型、作用范围和存储类别三种属性,其中作用范围分为局部和全局。预编译命令包括文件包含和宏定义,宏定义分为无参和带参两种形式。此外,还介绍了变量的存储类别及其特点。通过实例详细解析了函数调用过程及宏定义的应用。
|
1月前
|
Linux C语言
C语言 多进程编程(三)信号处理方式和自定义处理函数
本文详细介绍了Linux系统中进程间通信的关键机制——信号。首先解释了信号作为一种异步通知机制的特点及其主要来源,接着列举了常见的信号类型及其定义。文章进一步探讨了信号的处理流程和Linux中处理信号的方式,包括忽略信号、捕捉信号以及执行默认操作。此外,通过具体示例演示了如何创建子进程并通过信号进行控制。最后,讲解了如何通过`signal`函数自定义信号处理函数,并提供了完整的示例代码,展示了父子进程之间通过信号进行通信的过程。