数据结构 第6章.ppt

《数据结构 第6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章树和二叉树6.1树的概念与定义6.2二叉树6.3二叉树的遍历与线索化6.4树、森林和二叉树的关系6.5哈夫曼树及其应用本章重点和难点:掌握树的基本概念；掌握二叉树的基本概念和性质；掌握二叉树的存储结构；掌握二叉树的遍历方法；了解二叉树线索化方法及其线索化二叉树相关的运算；掌握Haffman树及其应用；掌握掌握树的存储结构；掌握树、森林和二叉树相互转化方法。6.1树的概念与定义树是n（n≥0）个结点的有限集合T。当n=0时，称为空树；当n>0时，该集合满足如下条件：(1)其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。(2)其余n-1个结点

2、可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。图6.1树的图示方法·结点：包含一个数据元素及若干指向其它结点的分支信息。·结点的度：一个结点的子树个数称为此结点的度。·叶结点：度为0的结点，即无后继的结点，也称为终端结点。·分支结点：度不为0的结点，也称为非终端结点。·孩子结点：一个结点的直接后继称为该结点的孩子结点。在图6.1中，B、C是A的孩子。·双亲结点：一个结点的直接前驱称为该结点的双亲结点。在图6.1中，A是B、C的双亲。·兄弟结点：同一双亲结

3、点的孩子结点之间互称兄弟结点。在图6.1中，结点H、I、J互为兄弟结点。·祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图6.1中，结点K的祖先是A、B、E。·子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。在图6.1中，结点D的子孙是H、I、J、M。·树的度：树中所有结点的度的最大值。·结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。·树的高度（深度）：树中所有结点的层次的最大值。·有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。·森林：m（m≥0）棵互不相交的树的集合。将一棵非空树的

4、根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子结点：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F的祖先：A，B结点M的祖先：A，D，HADTTree数据对象D：一个集合，该集合中的所有元素具有相同的特性。数据关系R：若D为空集，则为空树。若D中仅含有一个数据元素，则R为空集，否则R={H}，H是如下的二元关系：(1)在D中存在

5、唯一的称为根的数据元素root，它在关系H下没有前驱。(2)除root以外，D中每个结点在关系H下都有且仅有一个前驱。基本操作：(1)InitTree（Tree）：将Tree初始化为一棵空树。(2)DestoryTree（Tree）：销毁树Tree。(3)CreateTree（Tree）：创建树Tree。(4)TreeEmpty（Tree）：若Tree为空，则返回TRUE，否则返回FALSE。(5)Root（Tree）：返回树Tree的根。(6)Parent（Tree，x）：树Tree存在，x是Tree中的某个结点。若x为非根结点，则返回它的双亲，否则返回“空”。(7)

6、FirstChild（Tree，x）：树Tree存在，x是Tree中的某个结点。若x为非叶子结点，则返回它的第一个孩子结点，否则返回“空”。(8)NextSibling（Tree，x）：树Tree存在，x是Tree中的某个结点。若x不是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则返回“空”。(9)InsertChild（Tree，p，Child）：树Tree存在，p指向Tree中某个结点，非空树Child与Tree不相交。将Child插入Tree中，做p所指向结点的子树。(10)DeleteChild（Tree，p，i）：树Tree存在，p指向Tree中某个结点，1

7、≤i≤d，d为p所指向结点的度。删除Tree中p所指向结点的第i棵子树。(11)TraverseTree（Tree，Visit（））：树Tree存在，Visit（）是对结点进行访问的函数。按照某种次序对树Tree的每个结点调用Visit（）函数访问一次且最多一次。若Visit（）失败，则操作失败。6.2二叉树6.2.1二叉树的定义与基本操作定义：我们把满足以下两个条件的树形结构叫做二叉树（BinaryTree）：（1）每个结点的度都不大于2