总结

树与二叉树是数据结构里概念密度最高的一章:性质、遍历、线索化、哈夫曼树,每一项都可能单独出题。术语对照表把满二叉树、完全二叉树、四种遍历、线索二叉树的说法对齐到英文,核心要点给出必须记牢的 n0=n2+1n_0 = n_2 + 1 与每层结点数上界,其余概念建议配合本章的遍历演示一起复习。

术语对照表

中文术语英文术语说明
树Treen 个结点的有限集
二叉树Binary Tree每个结点至多两个孩子的有序树
叶子结点Leaf度为 0 的结点
深度Depth结点的最大层次数
满二叉树Full Binary Tree每层结点数达最大值
完全二叉树Complete Binary Tree最后一层结点集中左侧
前序遍历Preorder根左右
中序遍历Inorder左根右
后序遍历Postorder左右根
层序遍历Level-order按层次遍历
线索二叉树Threaded Binary Tree用空指针存前驱后继
哈夫曼树Huffman Tree带权路径长度最小的二叉树

核心要点

  • 二叉树性质:n0=n2+1n_0 = n_2 + 1;第 i 层至多 2i−12^{i-1} 个结点
  • 前序+中序 或 后序+中序 可唯一确定二叉树;前序+后序不能
  • 三种遍历递归代码只改变 visit 的位置,时间复杂度均为 O(n)O(n)
  • 层序遍历借助队列实现
  • 哈夫曼编码是最优前缀编码,用于数据压缩

发现内容有问题?

告诉我们哪里需要改进。