`

每周一道数据结构(三)树、二叉树、最优二叉树

阅读更多
原帖地址:http://www.cnblogs.com/coder2012/archive/2013/06/05/3102868.html




 


  树形结构是一类非常重要的非线性结构,它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象,因此在计算机领域里有着广泛应用,如操作系统中的文件管理、编译程序中的语法结构和数据库系统信息组织形式等。



 


树的相关定义




  1. 节点的度:一个节点含有的子树的个数称为该节点的度;

  2. 树的度:一棵树中,最大的节点的度称为树的度;

  3. 叶节点终端节点:度为零的节点;

  4. 非终端节点分支节点:度不为零的节点;

  5. 双亲节点父节点:若一个结点含有子节点,则这个节点称为其子节点的父节点;

  6. 孩子节点子节点:一个节点含有的子树的根节点称为该节点的子节点;

  7. 兄弟节点:具有相同父节点的节点互称为兄弟节点;

  8. 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

  9. 树的高度深度:树中节点的最大层次;

  10. 堂兄弟节点:双亲在同一层的节点互为堂兄弟;

  11. 节点的祖先:从根到该节点所经分支上的所有节点;

  12. 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。

  13. 森林:由m(m>=0)棵互不相交的树的集合称为森林;


 


二叉树




  二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。


  二叉树(BinaryTree)是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树右子树的二叉树组成。


  完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树。


1.二叉树的遍历


   所谓遍历二叉树,就是遵从某种次序,访问二叉树中的所有结点,使得每个结点仅被访问一次。


  二叉树的遍历包括三种:



  • DLR称为前根遍历(前序遍历)

    •   访问结点的操作发生在遍历其左右子树之前



  • LDR称为中根遍历(中序遍历)

    •   访问结点的操作发生在遍历其左右子树之中(间)



  • LRD称为后根遍历(后序遍历)


    •   访问结点的操作发生在遍历其左右子树之后



递归实现:



void preorder(NODE *p)
{
if(p!=NULL)
{printf(“
%d ”,p->data);
preorder(p
->lchild);
preorder (p
->rchild);}
}

void InOrder(BinTree T)
{
if(T) { // 如果二叉树非空
InOrder(T->lchild);
printf(
"%c",T->data); // 访问结点
InOrder(T->rchild);
}
}
// InOrder

void posorder(NODE *p)
{
if(p!=NULL)
{
posorder(p
->lchild);
posorder (p
->rchild);
printf(“
%d ”,p->data);
}


非递归实现:



/*算法思想:

利用队列基本操作
1.初始化:根结点入队列
2.while(队列非空)
{
a.队首元素出队列
b.原队首元素对应的左、右孩子(非空)入队列
}
*/

void traverse(NODE *T)
{
NODE
*q[100];
int head,tail, i;
q[
0]=T;head=0;tail=1;
while(head<tail)
{
p
=q[head++];
printf(“
%c”,T->data);
if(p->lchild!=NULL)
q[tail
++]=p->lchild;
if(p->rchild!=NULL)
q[tail
++]=p->rchild;
}
}


 


2.二叉树的构造


  基于先序遍历的构造,即以二叉树的先序序列为输入构造。



void CreateBinTree (BinTree *T)
{
char ch;
if((ch=getchar())=='')
*T=NULL; //读人空格,将相应指针置空
else{ //读人非空格
*T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
(*T)->data=ch;
CreateBinTree(
&(*T)->lchild); //构造左子树
CreateBinTree(&(*T)->rchild); //构造右子树
}
}


 


最优二叉树




    在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树哈夫曼树


  假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:


  1.  将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);

  2.  在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

  3. 从森林中删除选取的两棵树,并将新树加入森林;

  4. 重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。



  具体代码:



#include "stdio.h"
#include
"stdlib.h"
#define m 100

struct ptree //定义二叉树结点类型
{
int w; //定义结点权值
struct ptree *lchild; //定义左子结点指针
struct ptree *rchild; //定义右子结点指针
};

struct pforest //定义链表结点类型
{
struct pforest *link;
struct ptree *root;
};

int WPL=0; //初始化WTL为0
struct ptree *hafm();
void travel();
struct pforest *inforest(struct pforest *f,struct ptree *t);

void travel(struct ptree *head,int n)
{
//为验证harfm算法的正确性进行的遍历
struct ptree *p;
p
=head;
if(p!=NULL)
{
if((p->lchild)==NULL && (p->rchild)==NULL) //如果是叶子结点
{
printf(
"%d ",p->w);
printf(
"the hops of the node is: %d/n",n);
WPL
=WPL+n*(p->w); //计算权值
}//if
travel(p->lchild,n+1);
travel(p
->rchild,n+1);
}
//if
}//travel

struct ptree *hafm(int n, int w[m])
{
struct pforest *p1,*p2,*f;
struct ptree *ti,*t,*t1,*t2;
int i;
f
=(pforest *)malloc(sizeof(pforest));
f
->link=NULL;
for(i=1;i<=n;i++) //产生n棵只有根结点的二叉树
{
ti
=(ptree*)malloc(sizeof(ptree));//开辟新的结点空间
ti->w=w[i]; //给结点赋权值
ti->lchild=NULL;
ti
->rchild=NULL;
f
=inforest(f, ti);
//按权值从小到大的顺序将结点从上到下地挂在一颗树上
}//for
while(((f->link)->link)!=NULL)//至少有二棵二叉树
{
p1
=f->link;
p2
=p1->link;
f
->link=p2->link; //取出前两棵树
t1=p1->root;
t2
=p2->root;
free(p1);
//释放p1
free(p2); //释放p2
t=(ptree *)malloc(sizeof(ptree));//开辟新的结点空间
t->w = (t1->w)+(t2->w); //权相加
t->lchild=t1;
t
->rchild=t2; //产生新二叉树
f=inforest(f,t); //每次构造一颗二叉树的时候,都要从新排列一下
}
//while
p1=f->link;
t
=p1->root;
free(f);
return(t); //返回t
}

pforest
*inforest(struct pforest *f,struct ptree *t)
{
//按权值从小到大的顺序将结点从上到下地挂在一颗树上
struct pforest *p, *q, *r;
struct ptree *ti;
r
=(pforest *)malloc(sizeof(pforest)); //开辟新的结点空间
r->root=t;
q
=f;
p
=f->link;
while (p!=NULL) //寻找插入位置
{
ti
=p->root;
if(t->w > ti->w) //如果t的权值大于ti的权值
{
q
=p;
p
=p->link; //p向后寻找
}//if
else
p
=NULL; //强迫退出循环
}//while
r->link=q->link;
q
->link=r; //r接在q的后面
return(f); //返回f
}

void InPut(int &n,int w[m])
{
printf(
"please input the sum of node/n"); //提示输入结点数
scanf("%d",&n); //输入结点数
printf ("please input weight of every node/n"); //提示输入每个结点的权值
for(int i=1;i<=n;i++)
scanf(
"%d",&w[i]); //输入每个结点权值
}

int main( )
{
struct ptree *head;
int n,w[m];
InPut(n,w);
head
=hafm(n,w);
travel(head,
0);
printf(
"The length of the best path is WPL=%d", WPL);//输出最佳路径权值之和
return 1;
}


  

本文链接

分享到:
评论

相关推荐

    数据结构课件zju01

    此外,还提供了一些参考书目,如魏宝刚、陈越、王申康编著的《数据结构与算法分析(C语言版)》,Sartaj Sahni的《Data Structures, Algorithms, and Applications in C++》,以及严蔚敏等编著的《数据结构》和...

    April-2021-LeetCode-Challenge

    4. **树结构**:二叉树是常见的一种数据结构,包括二叉搜索树、完全二叉树、满二叉树、平衡树(AVL树、红黑树)等。树相关的题目可能涉及遍历(前序、中序、后序)、查找、插入和删除节点等操作。 5. **图算法**:...

    Leetcode-每周-中

    5. **树与图**:在数据结构中,树和图是两种重要的非线性结构。题目可能要求你实现二叉树的遍历、查找最近的节点,或者解决最短路径问题。 6. **堆与队列**:堆常用于实现优先队列,而队列则用于处理先进先出的问题...

    leetcode答案-leetcode:leetCode题型解析与解答

    4. 树:二叉树、平衡树、堆等数据结构的实现与操作。 5. 哈希表:利用哈希表快速查找、去重等。 6. 动态规划:解决最优化问题,寻找最优解的过程。 7. 回溯法:用于解决组合问题,如八皇后、迷宫寻路等。 8. 分治法...

    基于Simulink的风火水储联合调频系统中储能SOC对ACE影响的技术分析

    内容概要:本文详细探讨了在Simulink环境中构建的风火水储联合调频系统中,储能系统的荷电状态(SOC)对区域控制偏差(ACE)的影响。文中通过具体案例和MATLAB代码展示了储能系统在不同SOC水平下的表现及其对系统稳定性的作用。同时,文章比较了储能单独调频与风火水储联合调频的效果,强调了储能系统在应对风电波动性和提高系统响应速度方面的重要作用。此外,作者提出了针对SOC变化率的参数整定方法以及多电源协同工作的优化策略,旨在减少ACE波动并确保系统稳定运行。 适合人群:从事电力系统调频研究的专业人士,尤其是熟悉Simulink仿真工具的研究人员和技术人员。 使用场景及目标:适用于希望深入了解储能系统在电力系统调频中作用的研究者和技术人员,目标是通过合理的SOC管理和多电源协同工作,优化调频效果,提高系统稳定性。 其他说明:文章提供了详细的MATLAB代码片段,帮助读者更好地理解和应用所讨论的概念。同时,文中提到的实际案例和仿真结果为理论分析提供了有力支持。

    欧姆龙PLC NJ中大型程序案例:结构化与面向对象编程的深度融合及应用

    内容概要:本文深入探讨了欧姆龙PLC NJ系列中大型程序中结构化编程与面向对象编程的结合及其应用。首先介绍了结构化编程作为程序框架的基础,通过功能块(FB)实现清晰的程序结构和流程控制。接着阐述了面向对象编程的理念,将现实世界的对象映射到程序中,利用类的概念实现模块化和可扩展性。两者结合提高了程序的容错率,增强了程序的稳定性和可维护性。文中通过多个实际案例展示了如何在工业自动化领域中应用这两种编程方法,如电机控制、设备类的创建、异常处理机制、接口实现多态性、配方管理和报警处理等。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是那些希望提升PLC编程技能的人群。 使用场景及目标:适用于需要优化PLC程序结构、提高程序可靠性和可维护性的场合。目标是帮助工程师掌握结构化编程和面向对象编程的技巧,从而写出更加高效、稳定的PLC程序。 其他说明:文章强调了在实际项目中灵活运用两种编程方法的重要性,并提醒读者注意实时性要求高的动作控制应采用结构化编程,而工艺逻辑和HMI交互则更适合面向对象编程。

    matlab与聚类分析

    matlab与聚类分析。根据我国历年职工人数(单位:万人),使用有序样品的fisher法聚类。

    卡尔曼滤波生成航迹测量程序

    卡尔曼滤波生成航迹测量程序

    基于格子玻尔兹曼方法(LBM)的多孔电极浸润特性研究及其Python实现

    内容概要:本文详细介绍了利用格子玻尔兹曼方法(LBM)对多孔电极浸润特性的模拟研究。首先阐述了LBM的基本原理,包括碰撞和迁移两个关键步骤,并提供了相应的Python伪代码。接着讨论了如何处理多孔介质中的固体边界,特别是通过随机算法生成孔隙结构以及结合CT扫描数据进行三维重构的方法。文中还探讨了表面张力、接触角等因素对浸润过程的影响,并给出了具体的数学表达式。此外,文章提到了并行计算的应用,如使用CUDA加速大规模网格计算,以提高模拟效率。最后,作者分享了一些实用技巧,如通过调整松弛时间和润湿性参数来优化模拟效果,并强调了LBM在处理复杂几何结构方面的优势。 适合人群:从事电池研发、材料科学领域的研究人员和技术人员,尤其是关注多孔电极浸润性和电解液扩散机制的人群。 使用场景及目标:适用于希望深入了解多孔电极内部流体动力学行为的研究者,旨在帮助他们更好地理解和预测电极材料的浸润特性,从而改进电池设计和性能。 其他说明:尽管LBM在处理多孔介质方面表现出色,但在某些极端条件下仍需引入额外的修正项。同时,参数的选择和边界条件的设定对最终结果有着重要影响,因此需要谨慎对待。

    基于FPGA和W5500的TCP网络通信:Zynq扩展口开发测试平台(使用Vivado 2019.2纯Verilog实现)

    内容概要:本文详细介绍了在Zynq扩展口上使用FPGA和W5500实现TCP网络通信的过程。作者通过一系列实验和技术手段,解决了多个实际问题,最终实现了稳定的数据传输。主要内容包括:硬件搭建(SPI接口配置)、数据回环处理、压力测试及优化、多路复用扩展以及上位机测试脚本的编写。文中提供了大量Verilog代码片段,展示了如何通过状态机控制SPI通信、优化数据缓存管理、处理中断等问题。 适合人群:对FPGA开发和网络通信感兴趣的工程师,尤其是有一定Verilog编程基础的研发人员。 使用场景及目标:适用于需要在嵌入式系统中实现高效、稳定的TCP通信的应用场景。目标是帮助读者掌握FPGA与W5500结合进行网络通信的具体实现方法和技术细节。 其他说明:文章不仅提供了详细的代码实现,还分享了许多实践经验,如硬件连接注意事项、信号完整性问题的解决方案等。此外,作者还提到了未来的工作方向,如UDP组播和QoS优先级控制的实现。

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    基于FDTD仿真的可调谐石墨烯超材料吸收体设计与实现

    内容概要:本文详细介绍了利用有限差分时域法(FDTD)进行可调谐石墨烯超材料吸收体的设计与仿真。文中解释了石墨烯超材料的基本结构(三层“三明治”结构)、关键参数(如化学势、周期、厚度等)及其对吸收性能的影响。同时展示了如何通过调整石墨烯的化学势来实现吸收峰的位置和强度的变化,以及如何优化结构参数以获得最佳的吸收效果。此外,还提供了具体的代码示例,帮助读者理解和重现相关实验结果。 适合人群:从事纳米光子学、超材料研究的专业人士,尤其是对石墨烯基超材料感兴趣的科研工作者和技术开发者。 使用场景及目标:适用于希望深入了解石墨烯超材料的工作原理及其潜在应用场景的研究人员;旨在探索新型可调谐光学器件的设计思路和发展方向。 其他说明:文中不仅分享了理论知识,还包括了许多实践经验,如避免常见错误、提高仿真相关效率的小技巧等。对于想要将研究成果应用于实际产品的团队来说,这些细节非常有价值。

    随机生成2字到10字的中文词组

    随机生成2字,3字,4字,5字,6字,7字,8字,9字,10字的中文词组20个

    【汽车电子电气架构】智能座舱域控平台设计:基于双片龍鷹一号SoC芯片的高性能硬件架构与多模态交互系统构建

    内容概要:本文详细探讨了智能座舱域控设计的发展历程和技术趋势。首先介绍了智能座舱从被动式交互到主动式交互的技术演变,包括硬件和交互方式的进步。随后,文章重点讨论了智能座舱功能发展趋势,涵盖车载显示技术的多屏化、大屏化和高端化,以及SoC芯片的多核异构架构和算力融合,强调了其在智能座舱中的核心作用。此外,还阐述了电子电气架构从分布式向集成化的转型,分析了其面临的挑战和未来趋势。最后,基于当前智能座舱的发展需求,提出了一种基于双片龍鷹一号芯片的新域控平台设计方案,详细描述了其硬件设计实现方案,旨在提供高性能、高可靠性的智能座舱解决方案。 适合人群:汽车电子工程师、智能座舱研发人员及相关领域的技术人员。 使用场景及目标:①帮助读者理解智能座舱的技术发展历程及其未来发展方向;②为智能座舱域控平台的设计和开发提供参考和技术支持;③探讨电子电气架构的转型对汽车行业的影响及应对策略。 其他说明:文章结合实际案例和技术数据,深入浅出地解释了智能座舱的各项技术细节,不仅提供了理论指导,还具有较强的实践意义。通过对智能座舱域控平台的全面剖析,有助于推动智能座舱技术的创新发展,提升用户体验。

    多智能体协同编队控制:无人机编队背后的Python实现与关键技术解析

    内容概要:本文详细介绍了多智能体协同编队控制的技术原理及其应用实例。首先通过生动形象的例子解释了编队控制的核心概念,如一致性算法、虚拟结构法和Leader-Follower模式。接着深入探讨了如何用Python实现基础的一致性控制,以及如何通过调整参数(如Kp、Ka)来优化编队效果。文中还讨论了实际工程中常见的问题,如通信延迟、避障策略和动态拓扑变化,并给出了相应的解决方案。最后,强调了参数调试的重要性,并分享了一些实用技巧,如预测补偿、力场融合算法和分布式控制策略。 适合人群:对多智能体系统、无人机编队控制感兴趣的科研人员、工程师和技术爱好者。 使用场景及目标:适用于希望深入了解多智能体协同编队控制理论并能够将其应用于实际项目的研究人员和开发者。目标是帮助读者掌握编队控制的关键技术和实现方法,提高系统的稳定性和可靠性。 其他说明:文章不仅提供了详细的理论讲解,还附有具体的代码示例,便于读者理解和实践。同时,作者结合自身经验分享了许多宝贵的调试技巧和注意事项,有助于读者在实际应用中少走弯路。

    评估管线钢环焊缝质量及其对氢脆的敏感性.pptx

    评估管线钢环焊缝质量及其对氢脆的敏感性.pptx

    C盘清理bat脚本自动清理C盘垃圾文件

    C盘清理bat脚本自动清理C盘垃圾文件

    GBT21266-2007 辣椒及辣椒制品中辣椒素类物质测定及辣度表示方法

    GBT21266-2007 辣椒及辣椒制品中辣椒素类物质测定及辣度表示方法

    弹跳球 XNA 游戏项目 演示如何使用 C# 在 Visual Studio XNA 中构建类似 arkanoiddx-ball 的游戏

    弹跳球 XNA 游戏项目。演示如何使用 C# 在 Visual Studio XNA 中构建类似 arkanoiddx-ball 的游戏。

    【人形机器人领域】宇树科技人形机器人:技术实力、市场炒作与应用前景分析

    内容概要:文章全面解析了宇树科技人形机器人的发展现状、技术实力、市场炒作现象及其应用前景和面临的挑战。宇树科技成立于2016年,凭借春晚舞台的惊艳亮相和社交媒体的热议迅速走红,其人形机器人具备先进的运动控制算法、传感器技术和仿生结构设计。然而,市场炒作现象如高价租赁、二手市场炒作和虚假宣传等影响了市场秩序。尽管存在炒作,人形机器人在工业、服务和家庭领域仍具广阔前景,但也面临技术升级、成本控制、安全性和政策监管等挑战。 适合人群:对机器人技术、人工智能以及科技发展趋势感兴趣的读者,包括科技爱好者、投资者和相关行业的从业者。 使用场景及目标:①帮助读者了解宇树科技人形机器人的技术特点和发展历程;②揭示市场炒作现象及其影响;③探讨人形机器人的应用前景和面临的挑战。 其他说明:文章强调了宇树科技人形机器人在技术上的突破和市场上的表现,同时也提醒读者关注市场炒作现象带来的风险,呼吁各方共同努力推动人形机器人产业健康发展。

Global site tag (gtag.js) - Google Analytics