东北大学——考研初试——计算机842——树非编程题

树的术语

• 父节点与子节点
• 父节点、子节点与兄弟节点
• 结点度与树度
• 深度与高度（层次）
• 有序树与无序树：子树的左右顺序是否影响结构？
• 路径及其长度：由顶点组成的序列；由边的数量表示。

树的性质

理解胜记忆

• 树的总度数 + 1 = 树的总结点数

  • 拓展：n0 * 0 + n1 * 1 + … + ni * i + 1 = n0 + n1 + … + ni

• 阶数为m的树，在第i层上的最大节点数量：m^{(i-1)}

• 高度为h的m元树的最大节点数量：1\,+\,m\,+\,m^2\,+\,\dots\,+\,m^{(h-1)}

• 具有n个顶点的m元树的最小深度满足不等式：1\,+\,m\,+\,\dots\,+ \,m^{(d-2)} < n \leqslant 1\,+\,m\,+ \,\dots \,+ \,m^{(d-1)}

特殊二叉树

• 满二叉树

  • 完全二叉树
    • 对于序号为i的结点而言
      • 其左子节点编号为2i
      • 右子节点编号为2i+1
      • 其父节点编号为⌊i/2⌋
    • 除了最后一层外的所有层次均满填，并且最后一层中的结点从左至右排布

• 二叉排序树（BST）是一种基于节点值大小关系进行组织的二叉搜索树。

• 在计算机科学领域中被称为AVL树。

• 定义上所述的平衡因子等于左子树的高度减去右子树的高度；

• 其取值仅限于-1、0或1。

先中后序遍历的问题

写出先（中 左 右）、中（左 中 右）、后（左 右 中）来辅助分析。

基于两种遍历序列构建二叉树（重点内容）。具体步骤如下：首先通过先序或后序遍历确定父节点位置；其次借助中序遍历及父节点信息区分左右子树结构。

深度优先广度优先的问题

• 深度优先是一种先序遍历的方法；其特点是可以通过递归来实现（需注意压栈顺序）。
• 广度优先是一种层次遍历的方法；通常使用队列结构来实现。
• 时间复杂度相同：均为每个顶点恰好被访问一次的时间复杂度为O(n)。
• 空间复杂度因树的深度而异，在深度优先搜索中主要取决于树的高度；而在广度优先搜索中，则主要取决于树的宽度。

二叉树树的线索化（常考点）

首先对二叉树进行遍历并为其分配序号；
接着通过编号连接各节点；
随后检查是否存在根节点：
如果有根节点，则根节点的左子指针和尾节点的右子指针均指向根节点；
若无根节点，则根节点的左子指针和尾节点的右子指针均指向null。

树、森林、二叉树遍历的对应关系

理解胜记忆

树	森林	二叉树
树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

孩子兄弟法二叉树转化树、森林（常考点）

1. 左子树的右子孙们排布整齐。
   2. 右子孙们通过连线连接到双亲结点。
   3. 移除右子孙们的联系关系。

##平衡二叉树
从最低的不平衡因子开始

• 平衡二叉树的构建过程如下：

1. 向树中插入一个节点
2. 计算当前二叉树的平衡因子并确定所需的旋转类型
3. 执行一次平衡旋转以恢复树的平衡状态
4. 循环执行上述步骤直至所有节点被成功插入

对节点x进行一次顺时针方向的转动操作，则意味着其右子树中的一个特定节点（即该节点的最左边后代）将被切断连接关系，并将其重新连接到节点x的新位置上——具体来说是接到节点x原有位置左侧的空间中；与此同时，则将被切断的部分转移至节点x原有位置右侧的空间中以完成整个变换过程

平衡因子	旋转类型	操作
平衡因子	旋转类型	操作
x点左子树的左子树	LL平衡旋转	x右旋转
x点右子树的右子树	RR平衡旋转	x左旋转
x点左子树的右子树	LR平衡旋转	x的左孩子左旋转，再x右旋转
x点右子树的左子树	RL平衡旋转	x的右孩子右旋转，再x左旋转

• 增加结点

  • 加到叶子，再平衡

• 删除结点

  • 不断替换，直到删除叶子结点，删除，再平衡

##哈夫曼树和哈夫曼编码（常考点）

• 哈夫曼树的性质
  • 带权路径长度最小
  • 只有度为0和度为k的结点

哈夫曼树的构造：

1. 计算每个字符在文本中出现的概率；
2. 按概率从小到大排列所有字符；
3. 将概率最低的两个字符合并为一个新的节点，并将它们的概率之和作为新节点的概率值；反复上述步骤直到生成一颗单一父节点的树

• 哈夫曼编码

  1. 为左子树分配二进制位0、右子树分配二进制位1。
  2. 沿着从根节点到每个叶子节点的路径记录其对应的信息。
  • 带权路径长度
    1. 叶结点的权值 * 叶结点的路径长度
    2. 把所有叶结点的值求和

零碎的点

• 中序遍历与层序遍历序列相同，画树

  • 只要右子树

• n个叶结点的非满完全二叉树，树高

  • logn下取整 + 2，我推不出来，画图找规律

t为基于中序遍历的线索二叉树结构，在t中的某个非根节点x拥有一个左子节点的情况下，则x节点的直接前驱节点即为其左子节点路径上的最后一个右子节点。
核心原理：在该结构中，在t中的某个非根节点x拥有一个左子节点的情况下，则x位于中间位置，并被其左子节点的最右后代所包围。

• 森林内节点的数量为n，在其转换生成的一棵二叉树中（该二叉树）具有空右指针域的节点数目为n+1。

• 原理：在该转换过程中共有n个节点能够直接对应于原始森林中的相应节点（即原有n个独立的根节点），此外还新增了一个根节点用于构建整个二叉树结构。

• 从一棵二叉排序树中删除两个元素时，请问其删除顺序是否会影响最终的树结构？此现象发生在2001年版本的系统中。

• 不受影响的原因在于：若所删去的两个元素均为叶子节点，则不会对树结构产生任何影响；而对于那些非叶子节点而言，在执行删减操作时会先将其转化为叶子节点后再进行处理。