首页 > 知识点讲解
       树的存储结构及遍历操作
知识路径: > 计算机科学基础 > 常用数据结构 > 树 > 树和二叉树 > 
被考次数:9次     被考频率:中频率     总体答错率:38%     知识难度系数:     
相关知识点:11个      
        1)树的存储结构
        树是非线性的结构,存储树时,须把树中节点之间存在的关系反映在树的存储结构中。树有很多存储结构,这里仅介绍最常用的两种。
        (1)树的标准存储结构。
        树的标准存储结构由节点的数据和指向子节点的指针数组组成;对于度为M的树,其指针数组中的元素个数为M
        (2)树的带逆存储结构。
        由于树的带逆存储结构需要一个从子节点指向父节点的指针,因而该结构在标准存储结构的基础上,需要在树的节点中增加一个指向其双亲节点位置的指针。
        2)树的遍历
        树的遍历是树的基本操作之一,也是最重要的操作之一。树的遍历含义是指:按照某种要求依次访问树中的每个节点,每个节点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
        (1)树的前序遍历。
        首先访问根节点,然后从左到右前序遍历根节点的各棵子树。树的前序遍历递归算法如下:
        
        若利用栈来记录当前未访问完的子树的根节点指针,则前序遍历的非递归算法如下:
        
        (2)树的后序遍历。
        树的后序遍历的基本思想是:先依次遍历每棵子树,然后访问根节点,与后序遍历二叉树相同。树的后序遍历递归算法如下:
        
        (3)树的中序遍历。
        树的中序遍历的基本思想是:先左子树,遍历根节点,然后依次遍历其他各棵子树,类似二叉树的中序遍历。树的中序遍历递归算法如下:
        
 
本知识点历年真题:
隶属试卷 题号/题型 题干 难度系数/错误率
   2020年下半年
   程序员
   上午试卷 综合知识
第38题
选择题
下图所示为一个二叉排序树(二叉査找树),其先序遍历序列为( )。

43%
   2019年下半年
   程序员
   上午试卷 综合知识
第41题
选择题
若某二叉树的先序遍历序列是ABDCE,中序遍历序列是BDACE,则该二叉树为(41)。

48%
>>  更多  本知识点历年真题
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有