2023计算机考研初试在即，在最后阶段建议各位同学将知识点再系统复习一遍，以免有所遗漏！2022计算机考研数据结构第四单元知识点包含树、二叉树、树和森林、哈夫曼树和哈夫曼编码。高顿考研为大家整理了2022计算机考研数据结构第四单元知识点的详细内容，供大家参考复习！
树
树(有根树)是包括n个结点的有限非空集合。
特性：递归数据结构，层次结构
定义一：…定义二：…
相关术语：
双亲：若一个结点有子树，那么该结点称为子树根的双亲。
孩子：子树的根是该结点的孩子。
兄弟：有相同双亲的结点。
祖先：从根结点到某个结点路径上的所有结点都是该结点的祖先。
后裔：一个结点的所有子树上的任何结点都是该结点的后裔。
结点的度：一个结点拥有的子树数。
树的度：树中最大的结点的度。
树叶：度为零的结点。
分支结点：度不为零的结点。
结点的层次：从根开始定义起，根为第1层，其余结点的层次等于其双亲结点的层次加1。
树的高度：树中结点的最大层次。
森林：树的集合。
二叉树
二叉树是结点的有限集合，可以为空集，区分左右子树。
(1)性质：
二叉树的第i(i>1)层上至多有2i-1个结点。
高度为h的二叉树上至多有2^h–1个结点。
叶结点的个数总是比度为2的结点的个数多一个。
(2)几个概念：
满二叉树：高度为h的二叉树恰好有2^h–1个结点时称为满二叉树。
完全二叉树：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。(性质见书P71)
扩充二叉树：除叶子结点外，其余结点都必须有两个孩子。
(3)相关运算：
Root(x):若二叉树非空，则x有根的值，并返回true，否则返回false。
MakeTree(x,left,right):构造一棵二叉树：根的值为x，以left和right为左右子树。
BreakTree(x,left,right):拆分二叉树为三部分：x为根的值，left和right分别为原二叉树的左、右子树。
(4)二叉树的遍历
前序遍历、中序遍历、后序遍历、层次遍历(规则见书P75)
递归算法见P77
(5)二叉树的存储表示
顺序表示：完全二叉树中的结点可以按层次顺序，存储在一片连续的存储单元中。
链接表示：lChild和rChild为分别指向左、右孩子的指针，element是元素域。共有n-1个指针域非空，n+1个空指针域。
树和森林
(1)树和森林的存储表示(见书P82)
多重链表表示法
孩子兄弟链表示法
双亲表示法
三重链表表示法
(*)注意和二叉树的存储表示区分!
(2)树的遍历
前序遍历：访问根结点;从左往右前序遍历根的每一棵子树。
后序遍历：从左往右后序遍历根的每一棵子树;访问根结点。
层次遍历：从上往下，同一层从左往右，访问树中的每个结点。
(3)森林的遍历
加入一个虚结点，作为各棵树的根;遍历这棵树;删去虚结点。
先序遍历：访问第一棵树的根;按先序遍历第一棵树的根节点的子树组成的森林;按先序遍历除第一棵树外其余树组成的森林。
中序遍历、后序遍历以此类推。
(4)森林与二叉树的转换(见书P81)
哈夫曼树和哈夫曼编码
(1)路径长度：在二叉树中，从根到任意一个后裔结点的路径长度是指从根结点到该后裔结点的路径上所包括的边的数目。
二叉树的内路径长度：从根到其它所有分支结点的路径长度之和。
二叉树的外路径长度：从根到其它所有叶子结点的路径长度之和。
二叉树的加权路径长度：二叉树中所有叶子结点的加权路径长度之和。
(2)哈夫曼树和哈夫曼算法
最优二叉树：具有最小加权路径长度的二叉树。
哈夫曼算法：由哈夫曼给出、用于构造最优二叉树的算法。
a.用给定的一组权值{w1,w2,…,wn}，生成一个有n棵二叉树组成的集合F={T1，T2，…，Tn}，其中，每棵二叉树Ti只有一个结点，即权值为wi的根结点。
b.从F中选择两棵根结点权值最小的二叉树，作为新二叉树根的左、右子树，新二叉树根的权值是左、右子树根结点的权值之和。
c.从F中删除这两棵二叉树，另将新二叉树加入F中。
d.重复(2)和(3)，直到F中只包含一棵二叉树为止。
哈夫曼树：用哈夫曼算法构造的最优二叉树。
(3)哈夫曼编码
哈夫曼树的每个叶结点对应一个字符。在从哈夫曼树的每个结点到其左孩子的边上标上1。将从根到每个叶子的路径上的数码连接起来，就是该叶子所代表的字符的编码。
写评论
