数据结构课件：树的概念及存储.pptx

树的概念及存储

本讲要点哪些问题可以抽象成树这类逻辑结构树的定义树的基本术语树的存储结构

1.问题及抽象导学案例1：查找U盘中文件的存储路径假设一个U盘中有3个文件夹，每个文件夹中又有若干文件。请设计一种文件信息存储方法，当输入某个文件名称后，显示该文件在U盘中的存储路径，若U盘中无该文件，则显示“文件未找到”。

1.问题及抽象导学案例2问题：对表达式树表示的算术表达式求值已知算术表达式6+(7-3)/2对应的表达式树如图所示，请求出该表达式的值。

1.问题及抽象抽象根顶级域名netcomorggovcnuk……二级域名huawei……baidubj……eduwww……mapnjnupku……nju三级域名mail……www四级域名

2.树的定义树：n（n≥0）个结点的有限集合。若n＝0，称为空树。任意一棵非空树，满足以下条件：1）有且仅有一个特定的称为根的结点。2）当n＞1时，除根结点之外的其余结点可划分为m（m0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，称为根结点的子树。Ti为根结点的第i棵子树。树的定义是递归的。

3.树的基本术语孩子、双亲、兄弟结点：

某结点的子树的根结点称为该结点的孩子结点，该结点则称为其孩子结点的双亲结点。具有同一个双亲结点的孩子结点互称兄弟结点。子孙结点和祖先结点：

某结点的所有子树中的结点称为该结点的子孙结点。从根结点到达某结点的路径上经过的所有结点（除自身外），被称为该结点的祖先结点。结点的度和树的度：

某结点所拥有的子树个数称为该结点的度，树中所有结点度的最大值称为该树的度。

3.树的基本术语叶子结点和分支结点：

路径和路径长度：

结点的层次和树的高度：

结点的层次从根结点开始算，规定根结点的层次是1，其余结点的层次数等于其双亲结点的层次数加1。

树中所有结点的最大层次数称为该树的高度。有序树和无序树

除特殊说明外，在数据结构中讨论的树都是有序树。

3.树的基本术语森林：

m（m≥0）棵互不相交的树的集合称为森林。

当m=1时，森林就退化成了一棵树；

当m=0时，则表示一个空森林。

4.树的存储结构实现树的存储结构，关键是什么?如何表示各结点的数据信息如何表示树中结点之间的逻辑关系

4.树的存储结构（1）双亲表示法在存储结点数据信息的同时附加存储该结点的双亲关系。顺序存储结构优点？缺点？

4.树的存储结构（2）多叉链表表示法每个结点包含一个数据域和若干指针域，其中数据域用于存储结点的数据信息，指针域存储结点间的逻辑关系。链式存储结构缺陷？实用吗？

4.树的存储结构（3）孩子链表表示法用一个线性表存储树中结点的数据信息，称为结点表；为每个结点建立一个孩子链表，其中只存储孩子结点在结点表中的下标。链式存储结构顺序存储结构+缺陷？实用吗？

4.树的存储结构（4）孩子兄弟表示法链表中每个结点除了存储结点信息的数据域外，还有两个指针域，分别指向该结点的第一个孩子结点和右兄弟结点。链式存储结构优点？实用吗？孩子兄弟表示法既简化了结构，又与另一种树形结构——二叉树的链式存储类似。孩子兄弟表示法是树的一种较为普遍的存储结构。

本讲要点哪些问题可以抽象成树这类逻辑结构树的定义树的基本术语树的存储结构