资源描述：
《数据结构课件第4 章树 12.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第四章 树和二叉树第四章树和二叉树4.1树的基本概念4.2二叉树4.3二叉树存储结构与遍历4.4线索二叉树4.5树和森林4.6哈夫曼树及应用4.1树的基本概念1.树的定义2.树的实例与表示树的有关术语树的基本操作1．树的定义树是n个结点的有限集合T，当n=0时，称为空树；当n>0时，T满足如下条件：在任一棵非空树中： （1）有且仅有一个称为根的结点。 （2）其余结点可分为M个互不相交的子集合，而且这些子集合中的每一个本身又是一棵树，也称为根的子树。JIACBDHGFEKLM例：T={A,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其余结点可以划分为
2、3个互不相交的子集合：T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M}T1、T2、T3中的每一集合本身又是一棵树，它们是A的子树。例如对T1，B是根，其余结点可以划分为2个互不相交的子集合：T11={E，K，L}，T12={F}，T11,T12是B的子树。JIACBDHGFEKLM2．树的实例 树可表示具有分枝结构关系的对象例1．家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可用树表示：例2．单位行政机构的组织关系JIACBDHGFEKLM计算机中树是常用的数据组织形式尽管有些应用中数
3、据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式来组织的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11文件12C盘2、树的表示1）图示表示2）二元组表示3）嵌套集合表示4）凹入表示法5）广义表表示树的二元组表示（D，S）D={A，B，C，D，E，F，G，H，I，J} S={R} R={〈A,B>,,,,,,,,}树的图示表示JIACBDHGFE嵌
4、套集合表示:AEDHJIKLMFGC（A（B（E（K,L）,F））,(C（G）),(D（H（M）,I,J））)B广义表表示:2、树的表示1）图示表示2）二元组表示3）嵌套集合表示教材P120图6-2A4）凹入表示法（类似书目录）教材P120图6-2C5）广义表表示教材P120图6-2B3、树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子，B、C是A的孩子；双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点：同一双亲的孩子结点，H、I、J互为兄弟；堂兄结点：同一层上结点，B、C、D互为堂兄弟；祖先
5、结点:从根到该结点的路经分支上的所有结点，结点K的祖先是A、B、E子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙，结点D的子孙是H、I、J、MJIACBDHGFEKLM3、树的基本术语结点的层次：根结点的层次定义为1；根的孩子为第二层，依此类推； 树的深度：树中所有结点的层次的最大值 结点的度：结点子树的个数 树的度：树中结点度的最大值。 叶子结点：度为0的结点； 分枝结点：度不为0的结点；JIACBDHGFEKLM有序树：在树T中，如果各子树Ti之间有先后次序，称为有序树。子树有序的树，如：家族树；无序树：子树无序的树；森林；m（m≥0）棵互不相交
6、的树的集合；森林和树之间的联系：一棵非空树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。4、树的基本操作（P119）树的应用很广，树的基本操作：1）CreateTree(T):建树。2）root(T);求T树的根。3）traverse(T);遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。4）Child(T,x,i)：求T树中x结点的第i个孩子结点。5）rightsibling(T,x):求T树中x结点的右兄弟6）parent(T,x):求T树中x结点的双亲结点。7）delchild(T,x,i);删除x结点的第i个
7、孩子8）insertChild(T,y,i,x):将根为x的子树置为y结点的第i个孩子9）clear(T);置空T树,initTree(T):T树的初始化，4．2二叉树一二叉树的概念二二叉树的性质。一二叉树的概念1二叉树的定义二叉树：或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。AFGEDCB一二叉树的概念二叉树说明1）二叉树中每个结点最多有两个子树；既：二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;(a)、(b)是不同的二叉树，(a)的左子树有四个
8、结点，(b)的左子树有两个结点(a)(
