计算机的竞争度逐年加大，报考学生越来越多，对于打算报考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，指向其左指向前驱，右指向后继(方便前，中，后遍历)
树转二叉树：二叉树左子树为树的子节点，右子树为兄弟，单个树即只有左侧，同样森林可以是左右子树的二叉树
同理二叉树转回森林和树：类似
树
层次：根为第一层，最大层为树的高度，深度为根到该节点的路径长度;高度为叶节点到该节点最大路径
二叉树性质：
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，指向其左指向前驱，右指向后继(方便前，中，后遍历)
树转二叉树：二叉树左子树为树的子节点，右子树为兄弟，单个树即只有左侧，同样森林可以是左右子树的二叉树
同理二叉树转回森林和树：类似
收藏