第六章 树和二叉树
6.1树（tree）的概念
在日常生活中，可以见到很多情形可以归结为树结构。如：家族谱系、行政管理机构、DOS和Windows磁盘文件管理系统等。
我们讨论的树和自然界的树在生长方向上正好相反，它是倒长的树，即根朝上，枝干和叶子朝下。 例1：某家族谱系的一部分
景奇宏恩新民意海新主意河意江宏福新华意民新诚意凌宏亮新胜意山意水
例2：国家行政管理机构的一部分
国务院河北省北京市天津市内蒙古区廊坊市石家庄市海淀区西城区昌平县
例3：DOS和Windows磁盘文件的一部分
C:\\ TC20 VC6.0 数据结构课件 数据结构讲稿 第一章 第二章 ……
MyTc程序 Tc1 Tc2 ……
MyVc程序
Vc1 Vc2 ……
树是一种层次结构，属于非线性结构。我们学过的线性表可以灵活组织数据，但它受到线性结构的限制，表达层次结构不太方便。 6.1.1树的定义
·树T是n（n≥0）个结点的有限集合。它满足： (1)仅有一个特定的结点，称为根（root）结点; (2)其余结点分为m(m≥0)个互不相交的非空有限集合
T,T,……,T,其中每个集合自身又是一棵树，称为
1,2m根的子树（subtree）。
·为了表述方便，把没有结点的树称为空树。 ·树的定义具有递归性：即一棵树是由根及若干棵子树构成的，而子树又是由根及若干棵子树构成的，……。
表达树的方法通常有4种：树形、凹入、集合和广义表
(1) 树形表示法
A B E C F G D H (2) 凹入表示法
A B C E F D G H
(3) 集合嵌套表示法
A EC○F ○GD○H ○B
