学习目标

在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机构以及城市交通、通信等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。

所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树形结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系，如前面提到的族谱、城市交通等。在本章将重点讨论树形结构中最简单、应用十分广泛的二叉树结构。

知识要点

（1）树和二叉树的定义及相关概念，二叉树的链式存储、二叉树三种顺序遍历算法及遍历算法的应用。

（2）中序线索二叉树的算法及其简单应用。

（3）哈夫曼树的概念、哈夫曼树的构造和编码算法。