【C语言督学训练营 第十四天】二叉树真题实战 ----- 层序建树、前中后序遍历、求树的WPL

news/2024/10/25 19:31:47/

文章目录

  • 前言
  • 树概念
  • 二叉树
  • 层序建树
  • 四种遍历二叉树的方式
    • 层次遍历
    • 前序遍历
    • 中序遍历
    • 后续遍历
  • 真题实战！

前言

今天进行总结的是考研408有关二叉树的基础知识，是王道C语言督学营的第十四天，随着课程的深入，代码实战的难度慢慢的上来了，如果觉着代码实战有困难，那么我推荐先在纸上画一画，然后再上代码，今天这节课主要进行了二叉树的层序建树，二叉树的前中后序遍历，以及层序遍历，最后针对一道2014年的考研真题进行了解析！
先预热一下：
在这里插入图片描述
在这里插入图片描述

树概念

树是n (n≥0）个节点的有限集。当n = O时，称为空树。
在任意一棵非空树中应满足:

  • 1)有且仅有一个特定的称为根的结点。
  • 2)当n >1时，其余节点可分为m (m > 0）个互不相交的有限集T1，T2,…", Tm，其中每个集合本身又是一棵树，并且称为根的子树。

树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点:

  • 1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
  • 2）树中所有结点可以有零个或多个后继。
    在这里插入图片描述

二叉树

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分,其次序不能任意颠倒。
与树相似，二叉树也以递归的形式定义。二叉树是n (n≥O)个结点的有限集合:

  • ①或者为空二叉树，即n= 0.
  • ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树又可分为满二叉树与完全二叉树，两者形如下图：
在这里插入图片描述
满二叉树与完全二叉树，因为其独有的特性，采用顺序存储结构存储极为方便。后面排序时会进行实战！
在这里插入图片描述
在这里插入图片描述
链式二叉树节点结构定义如下：
在这里插入图片描述
这里仅仅是对二叉树进行了简要的介绍，真正的知识要比这个多得多，后面在介绍数据结构的时候会详细介绍！记住下面图片的内容，然后开启我们今天的实战！
在这里插入图片描述

层序建树

层析建树我们需要借助一个辅助队列进行实现，我的思路是，使用队列记录数节点的输入顺序，然后根据节点的左子树右子树指针是否为空向其子树填值，当左子树右子树均有值的时候就向下一个节点填充，每次填充的内容是新入队的节点！直到将辅助队列遍历一遍，二叉树也就层序建树成功！
建树代码如下：
节点的定义：

//
// Created by 123 on 2023/2/20.
//#ifndef MYTEST_BITSTRUCT_H
#define MYTEST_BITSTRUCT_H
//基础元素类型
#define  ElementData int
#define ElementDataEnd -1
//二叉树的节点
struct BiTNode{ElementData data;struct BiTNode *leftNode;struct BiTNode *rightNode;
};
typedef struct BiTNode BiTNode;
//辅助队列（通过这个队列层次建树）
struct auxiliary{// 指向二叉树中的节点struct BiTNode* p;struct auxiliary *next;
};
typedef struct auxiliary tagQueue;
#endif //MYTEST_BITSTRUCT_H

代码中的前两个函数是为了初始化节点方便设计的；

BiTNode* newNode(ElementData e){BiTNode *pnew=(BiTNode*) malloc(sizeof (BiTNode));pnew->leftNode=NULL;pnew->rightNode=NULL;pnew->data=e;return pnew;
}
tagQueue* newTagNode(BiTNode* pnew){tagQueue *p=(tagQueue *) malloc(sizeof (tagQueue));p->next=NULL;p->p=pnew;return p;
}
BiTNode *Sequence_tree_building(){BiTNode *tree=NULL,*pnew=NULL;tagQueue *tail=NULL,*tagQ=NULL,*p;ElementData e;while(scanf("%d",&e)){if(e==ElementDataEnd){break;}//将信息写入新生成的节点pnew=newNode(e);p=newTagNode(pnew);// 写成NULL==tail是为了防止tail=NULL的情况发生;//改变指针之间的关系，将节点插入相应位置if(NULL==tree){//此分支创建二叉树，创建辅助队列tree=pnew;tail=p;tagQ=tail;continue;}else{//将新节点添加到队尾tail->next=p;tail=tail->next;}// 精妙之处，通过辅助队列构建二叉树if(tagQ->p->leftNode==NULL){tagQ->p->leftNode=pnew;}else if(tagQ->p->rightNode==NULL){// 此分支多一句是因为,这种建树方式是层序建树（这颗子树左右都有的话会向兄弟树根偏移，而辅助队列下一个就是本层的兄弟树根）tagQ->p->rightNode=pnew;tagQ=tagQ->next;}}return tree;
}

建树结果，可以看到树中每一层节点对应的data;
在这里插入图片描述

四种遍历二叉树的方式

遍历就是将树中的所有节点访问一遍。

层次遍历

借助辅助队列，其实树的层次遍历就是一次BFS的过程，其英文全称是Breadth First Search。又称广度优先搜索，宽度优先搜索。实现过程如下：

// ---------------层序遍历----------------BFS//
//这种实现思路使用的是一级指针，还可以通过二级指针实现//
//直接判断节点的两个子节点是否为空，不为空添加到队列//
void Layer_Consult(BiTNode* tree){tagQueue *head=(tagQueue*) malloc(sizeof (tagQueue)),*tail,*q;head->p=tree;head->next=NULL;tail=head;while (head!=NULL){printf("%d ",head->p->data);//入队if(head->p->leftNode!=NULL){tagQueue *p=(tagQueue*) malloc(sizeof (tagQueue));p->p=head->p->leftNode;p->next=NULL;tail->next=p;tail=p;}if(head->p->rightNode!=NULL){tagQueue *p=(tagQueue*) malloc(sizeof (tagQueue));p->p=head->p->rightNode;p->next=NULL;tail->next=p;tail=p;}q=head;head=head->next;free(q);q=NULL;}
}

以下三种遍历方式较为简单，就不给出思路解释了，实现方式均是递归（因为树本质就是递归实现，估计考研不会限制大家使用递归还是非递归方法遍历，递归常常可以将有关树的问题简化的非常简单）。

前序遍历

// ---------------先序遍历----------------//
void Pre_Consult(BiTNode* tree){if(tree==NULL){return;}printf("%d ",tree->data);Pre_Consult(tree->leftNode);Pre_Consult(tree->rightNode);
}

中序遍历

// ---------------中序遍历----------------//
void Middle_Consult(BiTNode* tree){if(tree==NULL){return;}Middle_Consult(tree->leftNode);printf("%d ",tree->data);Middle_Consult(tree->rightNode);
}

后续遍历

// ---------------后序遍历----------------//
void Last_Consult(BiTNode* tree){if(tree==NULL){return;}Last_Consult(tree->leftNode);Last_Consult(tree->rightNode);printf("%d ",tree->data);
}

以下图片为层序、前、中、后序遍历实战结果：
在这里插入图片描述

真题实战！

在这里插入图片描述
又到了真题实战环节，今天这个实战很简单，本质是探索叶子节点及树的深度（也就是遍历一遍即可）WPL只树的带权路径长度，也就是叶子节点权值*其深度，然后相加之和。

（1）使用递归算法，参数负责接受树根与深度，当树中节点左子树右子树均为空时返回其深度与权值的乘积，当传入的节点为空时返回0，然后用两个变量依次接收左子树右子树的返回值，函数最后将左子树右子树返回值相加再返回，函数递归完毕最终的返回值就是我们所求得总的WPL。
（2）给出二叉树节点数据类型定义：

struct BiTNode{ElementData data;struct BiTNode *leftNode;struct BiTNode *rightNode;
};

（3）代码实现，这里给出了三种方法，其中第一种是算法描述部分的方法，第二种是使用static变量，第三种是使用全局变量。三种方式实现结果如下：
在这里插入图片描述

//
// Created by Zhu Shichong on 2023/1/9.
//
#include <stdio.h>
#include <stdlib.h>
#include "BitStruct.h"
#define bool int
#define true 1
#define false 0
//封装函数初始化一个根节点
BiTNode* newNode(ElementData e){BiTNode *pnew=(BiTNode*) malloc(sizeof (BiTNode));pnew->leftNode=NULL;pnew->rightNode=NULL;pnew->data=e;return pnew;
}
tagQueue* newTagNode(BiTNode* pnew){tagQueue *p=(tagQueue *) malloc(sizeof (tagQueue));p->next=NULL;p->p=pnew;return p;
}// -------------------层序建树------------------------------//
BiTNode *Sequence_tree_building(){BiTNode *tree=NULL,*pnew=NULL;tagQueue *tail=NULL,*tagQ=NULL,*p;ElementData e;while(scanf("%d",&e)){if(e==ElementDataEnd){break;}//将信息写入新生成的节点pnew=newNode(e);p=newTagNode(pnew);// 写成NULL==tail是为了防止tail=NULL的情况发生;//改变指针之间的关系，将节点插入相应位置if(NULL==tree){//此分支创建二叉树，创建辅助队列tree=pnew;tail=p;tagQ=tail;continue;}else{//将新节点添加到队尾tail->next=p;tail=tail->next;}// 精妙之处，通过辅助队列构建二叉树if(tagQ->p->leftNode==NULL){tagQ->p->leftNode=pnew;}else if(tagQ->p->rightNode==NULL){// 此分支多一句是因为,这种建树方式是层序建树（这颗子树左右都有的话会向兄弟树根偏移，而辅助队列下一个就是本层的兄弟树根）tagQ->p->rightNode=pnew;tagQ=tagQ->next;}}return tree;
}//计算二叉树WPL（Wight Path Length）递归方式实现
int WPL(BiTNode* tree,int deep){if(NULL==tree){return 0;} else if(NULL==tree->leftNode&&NULL==tree->rightNode){return deep*tree->data;}int p= WPL(tree->leftNode,deep+1);int q= WPL(tree->rightNode,deep+1);return p+q;
}
//计算二叉树WPL（Wight Path Length）静态变量方式实现
//这种方式纯属遍历一遍二叉树！
int WPL_Static(BiTNode* tree,int deep){static wight=0;if(NULL==tree){return 0;}if(NULL==tree->leftNode&&NULL==tree->rightNode){wight+=deep*tree->data;}WPL_Static(tree->leftNode,deep+1);WPL_Static(tree->rightNode,deep+1);return wight;
}
//计算二叉树WPL（Wight Path Length）全局变量方式实现
//这种方式纯属遍历一遍二叉树！
int wightg=0;
void WPL_Global(BiTNode* tree,int deep){if(NULL==tree){return ;}if(NULL==tree->leftNode&&NULL==tree->rightNode){wightg+=deep*tree->data;}WPL_Global(tree->leftNode,deep+1);WPL_Global(tree->rightNode,deep+1);
}
int main() {BiTNode *tree=Sequence_tree_building();printf("Recur count WPL:%d\n", WPL(tree,0));printf("static count WPL:%d\n", WPL_Static(tree,0));WPL_Global(tree,0);printf("globle count WPL:%d\n", wightg);return 0;
}

http://www.ppmy.cn/news/567340.html

相关文章

提前出击：如何在故障降临之前解决设备问题？

提前出击：如何在故障降临之前解决设备问题？

在现代工业生产中&#xff0c;设备故障和停机时间对企业来说是极具挑战性和成本高昂的问题。为了解决这一问题&#xff0c;预测性维护作为一种先进的维护策略应运而生。本文将探讨预测性维护的概念以及如何通过它在设备故障之前解决问题。 预测性维护是一种基于设备运行数据和分…
阅读更多...
ISDN网络的基本结构，ISDN网络具有的能力

ISDN网络的基本结构，ISDN网络具有的能力

1.ISDN网络的基本结构 2.ISDN网络的具有的能力 ①分组交换能力 ②电路交换能力 ③无交换连接能力 ④公共信道信令能力
阅读更多...
什么是ISDN

什么是ISDN

什么是ISDN&#xff1f; ISDN或IntegratedServicesDigitalNetwork,是您本地电话公司的一项业务。一条ISDN线是支持声音和数据通信的一个简单的高速通讯的数字电话服务。普通的电话线的声音传输质量与数字的ISDN线相比的话&#xff0c;就好像您从密纹唱片听到的声音质量与CD的相…
阅读更多...
ISDN，俗称一线通！

ISDN，俗称一线通！

参考&#xff1a; https://blog.csdn.net/qq_20233867/article/details/73862719 ISDN线路接口可分为两种类型 第一代&#xff1a;N-ISDN&#xff0c;基本速率接口&#xff08;BRI&#xff0c;Basic Rate Interface&#xff09;&#xff0c;Narrow&#xff0c;窄带 第二代&am…
阅读更多...
isdn简介

isdn简介

isdn 中文名称&#xff1a;综合业务数字网 综合业务数字网&#xff08;Integrated Services Digital Network&#xff0c;ISDN&#xff09;是一个数字电话网络国际标准&#xff0c;是一种典型的电路交换网络系统。 综合业务数字网&#xff08;ISDN&#xff09;&#xff0c;俗称…
阅读更多...
ISDN网络浅述

ISDN网络浅述

前阵子有个公司&#xff08;本来是我们的EDI潜在客户&#xff0c;但后来被别人夺了过去&#xff09;打电话给我&#xff0c;问我们有没有经验实施基于ISDN的OFTP通信。我当时就质问他们你们不是已经有了service provider了么&#xff0c;不会问他们么&#xff0c;对方虚了。好吧…
阅读更多...
MSDN是什么东西？

MSDN是什么东西？

《Microsoft Developer Network》&#xff08;简称MSDN&#xff09;&#xff0c;是微软的一个期刊产品&#xff0c;专门介绍各种编程技巧。同时它也是独立于Microsoft Visual Studio制作的唯一帮助。目前大部分文章存放在MSDN的网站上&#xff0c;任何人可以免费参阅。 MSDN是微…
阅读更多...
ISDN与ADSL

ISDN与ADSL

ISDN与普通模拟电话线有什么不同&#xff1f; 模拟电话线只能传送模拟话音信号&#xff0c;只能提供单一的电话业务。而ISDN实现了用户线的数字化&#xff0c;不管是文字、图像还是声音&#xff0c;只要变成数字信号&#xff0c;都可以传输&#xff0c;因此&#xff0c;ISDN可…
阅读更多...
最新文章

Copyright @ 2022~2023