计算机考试内容中的数据结构占试卷分值45分,建议考生在这门课程上多花点功夫去备考。以下是新东方在线整理的知识点,一定要认真看,。
2019考研计算机数据结构知识点:树和二叉树
第四章 树和二叉树
1、几个重要的概念:树、森林、子树、根、终端结点(叶子)、非终端结点、双亲、孩子、兄弟、堂兄弟、度、深度、有序树、无序树、二叉树、k 叉树、完全二叉树、满二叉树、线索二叉树;
2、二叉树的 5 种基本形态;
3、二叉树的 5 个重要性质:
(1)在二叉树的第 i 层上至多有 2i-1 个结点(i≥1);
(2)深度为 k 的二叉树至多有 2k-1 个结点,(k≥1)
(3)对任何一棵二叉树 T,如果其终端结点(叶子)数为 n0,度为 2 的结点数为 n2,则 n0=n2+1;
(4)具有 n 个结点的完全二叉树的深度为 log2 n1;
(5)如果对一棵有 n 个结点的完全二叉树(其深度为 log2 n1)的结点按性层序编号(从第1层到第log2 n1层,每层从左到右),则对任一结点 i(1≤i≤n)
4、二叉树的存储结构:
(1)了解顺序存储结构,只做了解;
(2)链式存储结构,重要,需要掌握,后面的算法都是基于此结构;
5、二叉树的遍历:
(1)能对任意一棵二叉树进行手动前序、中序、后序遍历;
(2)能将由前序+中序、后序+中序给出的序列还原成一棵二叉树;
(3)能将一个数学表达式用中序方法将其用二叉树画出来,并能写出其前缀(波兰式)、中缀、后缀(逆波兰式)表达出来;