计算机#2022考研究生计算机数据结构复习提纲#树

类目：三人行考研网>计算机>正文

时间：2020-12-0918:50:54

数据结构也是计算机考研常考的科目 ，部分院校会考试到这一专业课，本文三人行计算机考研小编整理分享“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，指向其左指向前驱
，右指向后继（方便前，中 ，后遍历）

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

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