姓名：
系别： 专业： 学号： 读 书 笔 记
论题： 姓名： 班级： 学号：
期 末 论
文
论树与二叉树
摘要：
树形结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可以用数来形象表示。数在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一。
关键词：二叉树，遍历，存储结构，森林
目录：
1. 树的定义和基本术语
2. 二叉树
3. 树和森林
4. 赫夫曼树及其应用
一、 树的定义和基本术语
树的定义：
树是n(n?0)个结点的有限集合T。若n=0，空树；若n>0，则：
有且仅有一个根(Root)结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为 m(m?0)个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，称为根的子树(SubTree)。 例如：
A B E F K L
其中，A是根；其余结点分成三个互不相交的子集： T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树。
C D J G H I M
基本术语：
结点：一个数据元素及指向其子树的分支。
结点的度：结点拥有的子树个数。 叶结点：度为零的结点。 孩子：结点子树的根。 兄弟：同一结点的孩子。
祖先：根到该结点路径上的所有结点。 子孙：某结点为根的子树上的任意结点。
结点层次：从根开始，根为第一层，根孩子为第二层，以此类推。 树的深度(高度)：树中结点的最大层次数。 有序树：树中结点的子树由左向右有序。 森林：m(m ? 0)棵互不相交的树。
二、 二叉树
定义：二叉树是n(n?0)个结点的有限集合，或空树(n=0)；或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成。
特点：每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)；二叉树结点的子树有左右之分。