首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2022研计算机数据结构复习提纲：树

2021-04-30 07:41:00来源：网络

　　 2022研计算机数据结构复习提纲：树

　　数据结构也是计算机研常的科，部分院校会试到这一专业课，本文新东方在线计算机研小编整理分享“2022研计算机数据结构复习提纲：树”相关内容，一起来看看吧。

　　层次：根为第一层，最大层为树的高度，深度为根到该节点的路径长度;高度为叶节点到该节点最大路径

　　二叉树性质：

　　1，二叉树第i层上的结点数最多为2i-1(i≥1)。

　　2，深度为k的二叉树至多有2^k-1个结点(k≥1)

　　3，在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1

　　4，具有n个结点的完全二叉树的深度为：log2[n](向下)+1或log2[n+1](向上)

　　二叉树存储形式：

　　1，顺序存储：第i个结点的孩子是2i,2i+1(完全二叉树适用，如果该树不是完全二叉树，需要添加空节点构成完全二叉树)

　　2，二叉链表结构：左右指针，中间数据|left|data|right|

　　二叉树遍历：

　　遍历是树进行其他运算的基础，前+中，中+后，层次+中(因为前后可以推出根结点，而中可以推左右)使用递归思想来推树的结构能够快些

　　如：前+中

　　前：GDAFEMHZ中：ADEFGHMZ

　　步骤：根据前知道root是G，根据中知道左子树是ADEF,右子树是HMZ

　　分析leftTree,由前知道root是D，soleftTreeis:A,andrightTreeis:EF

　　分析leftTreeA,结束，分析rightTree,From前知道root是F，From中知leftTreeisE

　　分析rigthTreeHMZ,From前知rootisM,From中知leftTreeisH,andrightTreeisZ

　　遍历结束，树的层次遍历为GDMAFHZE

　　如：中+后

　　中：ADEFGHMZ后：AEFDHZMG

　　步骤：From后，知道root是G，From中知leftTreeisADEF,rightTreeisHMZ;

　　分析leftTree:From后知rootisD,From中leftTreeisA,rightTreeisEF;

　　分析rightTreeEF;From后知：rootisF,From中leftTreeisE;

　　分析rightTreeHMZ;From后知rootisM，From中leftTreeisH，rightTreeisZ;

　　遍历结束，层次遍历为：GDMAFHZE

　　线索二叉树：左右标签为0，表示左右指针指向左右孩子节点，若为1，指向其左指向前驱，右指向后继(方便前，中，后遍历)

　　树转二叉树：二叉树左子树为树的子节点，右子树为兄弟，单个树即只有左侧，同样森林可以是左右子树的二叉树

　　同理二叉树转回森林和树：类似

　　以上是小编为大家整理分享的“2022研计算机数据结构复习提纲：树”相关内容，希望对大家有帮助。祝大家上理想的院校!更多计算机专业备信息，敬请关注新东方在线考研网!


本文关键字: 2022考研 计算机复习

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10