树与二叉树

概览图

本章节重点

掌握树、二叉树的相关概念定义；

掌握二叉树的递归遍历方式，了解非递归遍历方式。

掌握哈夫曼树及哈夫曼编码；

了解树的存储结构；

了解树与森林的转换。

树的相关概念

树是由n个有限结点组成的具有层次关系的集合。n=0 时称为空树。

任意一个非空树都应该满足：

1）有且仅有一个特定的结点，称为根；

2）当 n>1 时，其余结点可分为 m ( m ≥ 0 )个互不相交的有限集合 T1, T2,...,Tm，这些子集合本身也是树，称为根节点的子树。

树的定义是具有递归特性的，是一种递归的数据结构。

同时也是一种分层的结构。

树适合于表示具有