首页
最新活动
服务器租用
香港服务器租用
台湾服务器租用
美国服务器租用
日本服务器租用
新加坡服务器租用
高防服务器
香港高防服务器
台湾高防服务器
美国高防服务器
裸金属
香港裸金属服务器
台湾裸金属服务器
美国裸金属服务器
日本裸金属服务器
新加坡裸金属服务器
云服务器
香港云服务器
台湾云服务器
美国云服务器
日本云服务器
CDN
CDN节点
CDN带宽
CDN防御
CDN定制
行业新闻
官方公告
香港服务器资讯
帮助文档
wp博客
zb博客
服务器资讯
联系我们
关于我们
机房介绍
机房托管
登入
注册
帮助文档
专业提供香港服务器、香港云服务器、香港高防服务器租用、香港云主机、台湾服务器、美国服务器、美国云服务器vps租用、韩国高防服务器租用、新加坡服务器、日本服务器租用 一站式全球网络解决方案提供商!专业运营维护IDC数据中心,提供高质量的服务器托管,服务器机房租用,服务器机柜租用,IDC机房机柜租用等服务,稳定、安全、高性能的云端计算服务,实时满足您的多样性业务需求。 香港大带宽稳定可靠,高级工程师提供基于服务器硬件、操作系统、网络、应用环境、安全的免费技术支持。
联系客服
服务器资讯
/
香港服务器租用
/
香港VPS租用
/
香港云服务器
/
美国服务器租用
/
台湾服务器租用
/
日本服务器租用
/
官方公告
/
帮助文档
【数据结构】树和二叉树的概念及结构
发布时间:2024-03-02 20:28:45 分类:帮助文档
【数据结构】树和二叉树的概念及结构 1.树概念及结构 1.1树的概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点,称为根结点,根节点没有前驱结点。除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继。因此,树是递归定义的。 注意:树形结构中,子树之间不能有交集,否则就不是树形结构 1.2 树的相关概念 节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6 叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点 非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点 兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点 树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推; 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙 森林:由m(m>0)棵互不相交的树的集合称为森林; 1.3 树的表示 树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。 树的孩子兄弟表示法(Child-sibling representation)也被称为左孩子右兄弟表示法,它是一种用于表示树结构的方法。在这种表示法中,每个节点包含两个指针:一个指向其第一个子节点,另一个指向它的下一个兄弟节点。 typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 }; 1.4 树在实际中的运用(表示文件系统的目录树结构) 2.二叉树概念及结构 2.1概念 一棵二叉树是结点的一个有限集合,该集合: 1. 或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成 从上图可以看出: 1. 二叉树不存在度大于2的结点 2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树 注意:对于任意的二叉树都是由以下几种情况复合而成的: 2.2 特殊的二叉树 1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。 2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.3 二叉树的性质 1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( ) A 不存在这样的二叉树 B 200 C 198 D 199 解析:叶子节点是度为0的节点,根据上面的性质3: 所以叶子节点=199+1=200; 答案:B 2.在具有 2n 个结点的完全二叉树中,叶子结点个数为( ) A n B n+1 C n-1 D n/2 解析: 答案:B 3.一棵完全二叉树的节点数位为531个,那么这棵树的高度为( ) A 11 B 10 C 8 D 12 解析: 答案:B 4.一个具有767个节点的完全二叉树,其叶子节点个数为() A 383 B 384 C 385 D 386 解析: 答案:B 2.4 二叉树的存储结构 二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。 1. 顺序存储 顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数,在逻辑上是一颗二叉树。 2. 链式存储 二叉树的链式存储结构是指:用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,到高阶数据结构如红黑树等会用到三叉链。
上一篇
vps企业站
下一篇
356香港主机
相关文章
【服务器】安卓手机使用Termux搭建web服务
使用vscode远程服务器,让代码在vscode关闭后也在服务器后台运行
Ubuntu开启NTP时间同步
网上租的服务器怎么样
500m和1000mbps宽带速度怎么样
idc备案网站内容怎么填
windows 配置永久路由
SQL server 实现不同服务器之间的数据同步(作业实现)
宝塔硬盘不够用怎么办
香港云服务器租用推荐
服务器租用资讯
·广东云服务有限公司怎么样
·广东云服务器怎么样
·广东锐讯网络有限公司怎么样
·广东佛山的蜗牛怎么那么大
·广东单位电话主机号怎么填写
·管家婆 花生壳怎么用
·官网域名过期要怎么办
·官网邮箱一般怎么命名
·官网网站被篡改怎么办
服务器租用推荐
·美国服务器租用
·台湾服务器租用
·香港云服务器租用
·香港裸金属服务器
·香港高防服务器租用
·香港服务器租用特价
7*24H在线售后
高可用资源,安全稳定
1v1专属客服对接
无忧退款试用保障
德讯电讯股份有限公司
电话:00886-982-263-666
台湾总部:台北市中山区建国北路一段29号3楼
香港分公司:九龙弥敦道625号雅兰商业二期906室
服务器租用
香港服务器
日本服务器
台湾服务器
美国服务器
高防服务器购买
香港高防服务器出租
台湾高防服务器租赁
美国高防服务器DDos
云服务器
香港云服务器
台湾云服务器
美国云服务器
日本云服务器
行业新闻
香港服务器租用
服务器资讯
香港云服务器
台湾服务器租用
zblog博客
香港VPS
关于我们
机房介绍
联系我们
Copyright © 1997-2024 www.hkstack.com All rights reserved.