资源描述：
《数据结构第6章-树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树第六章树和二叉树第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4树和森林6.5树的应用第六章树和二叉树6.1树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作6.1树的有关概念1．树的概念树形结构是一种重要的非线性结构，讨论的是层次和分支关系。树是n个结点的有限集合，在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFEKLM6.1树的有关概念例：下面的图是一棵树T={A
2、,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其余结点可以划分为3个互不相交的集合：T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M}这些集合中的每一集合都本身又是一棵树，它们是A的子树。例如对于T11，B是根，其余结点可以划分为2个互不相交的集合：T11={E，K，L}，T12={F}，T11,T12是B的子树。JIACBDHGFEKLM6.1树的有关概念从逻辑结构看： 1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继； 4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结
3、构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。JIACBDHGFEKLM6.1树的有关概念2．树的应用 1）树可表示具有分枝结构关系的对象例1．家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J，K，L，M他们之间的关系可下图所示的树表示：例2．单位行政机构的组织关系JIACBDHGFEKLM6.1树的有关概念2）树是常用的数据组织形式有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的
4、。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C6.1树的有关概念3树的表示1）图示表示2）二元组表示 3）嵌套集合表示4）凹入表示法（类似书的目录） 5）广义表表示AEDHJIKLMDGCABEKLFCGDHMJI（A（B（E（K,L）,F））,C（G）,D（H（M）,I,J））6.1树的有关概念树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；祖先结点:从根到该结点的所经分支上的所有结点子孙结点：以某结
5、点为根的子树中任一结点都称为该结点的子孙JIACBDHGFEKLM6.1树的有关概念树的基本术语结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的深度：树中最大的结点层结点的度：结点子树的个数树的度：树中最大的结点度。叶子结点：也叫终端结点，是度为0的结点；分枝结点：度不为0的结点；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；森林；互不相交的树集合；森林和树之间的联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。JIACBDHGFEKLM6.1树的有关概念5树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：
6、1）initiate(T);T树的初始化，包括建树。2）root(T);求T树的根。3）parent(T,x):求T树中x结点的双亲结点。4）Child(T,x,i)：求T树中x结点的第i个孩子结点。5）right_sibling(T,x):求T树中x结点的右兄弟6）insert_Child(y,i,x):将根为x的子树置为y结点的第i个孩子7）del_child(x,i);删除x结点的第i个孩子8）traverse(T);遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。9）clear(T);置空T树6．2二叉树树是一种分枝结构的对象，在树的概念中，对每
7、一个结点孩子的个数没有限制，因此树的形态多种多样，本章我们主要讨论一种最简单的树——二叉树。第六章树和二叉树6.2二叉树一二叉树的概念二二叉树的性质三二叉树的存储结构6.2二叉树一二叉树的概念1二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树
