《清华大学》PPT课件

《《清华大学》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第14章二叉树及其应用1清华大学黄维通设计制作本章主要内容树的概念关于树的一些术语及特性二叉树的特点与数学性质二叉树的基本操作及其实现二叉树的应用2清华大学黄维通设计制作树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。14.1树的概念3清华大学黄维通设计制作4清华大学黄维通设计制作结点的度：一个结点的子结点的个数称为该结点的度。一棵

2、树的度是指该树中结点的最大度数。终端结点：树中度为零的结点称为终端结点，树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。14.2关于树的一些术语及特性5清华大学黄维通设计制作路径：如果存在树中的一个结点序列K1,K2,..,Kj，使得结点Ki是结点Ki+1的父结点(1≤i≤j)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。结点高度：树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。6清华大学黄维通设计制作层：从树根

3、到任一结点n有惟一的一条路径，这条路径的长度称为结点n的深度或层数。有序树：树的定义在某些结点之间确定了父子关系（可延拓为祖先子孙关系）。但是树中兄弟结点之间就没有祖先子孙关系。若在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树7清华大学黄维通设计制作14.3二叉树的特点与数学性质二叉树的定义二叉树是一种特殊的树型结构，其每个节点最多只有两个子树二叉树是结点的有限集合，该集合或是空集，或是一个根特点：每一个结点至多有两个后继结点，且有左右之分，不能任意交换，这些结点分别称为左

4、子树，右子树。8清华大学黄维通设计制作14.3.1二叉树的特点9清华大学黄维通设计制作(a)只有左子树(b)只有右子树10清华大学黄维通设计制作14.3.2两种特殊形态的二叉树满二叉树一棵高度为n≥0且有2n+1-1个结点的二叉树称为满二叉树11清华大学黄维通设计制作近似满二叉树若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为近似满二叉树(有时也称为完全二叉树)。12清华大学黄维通设计制作非近似满二叉树在近似满二叉树中，若某个结点没有左儿子，则它一定

5、没有右儿子，即该结点是一个叶结点13清华大学黄维通设计制作14.3.3二叉树的数学性质高度为n≥0的二叉树至少有n+1个结点高度不超过n(≥0)的二叉树至多有2n+1-1个结点含有n≥1个结点的二叉树的高度至多为n-1，至少为lg(n)14清华大学黄维通设计制作14.4二叉树的基本操作及其实现15清华大学黄维通设计制作二叉树的常用操作如下：InitTree(&T)：构造一棵空二叉树；DestroyTree(&T)：销毁一棵二叉树；Parent(T,e)：返回二叉树T中e结点的父结点，若不存在则返回“空”；L

6、eftChild(T,e)：返回二叉树T中e结点的左儿子结点，若不存在则返回“空”；RightChild(T,e)：返回二叉树T中e结点的右儿子结点，若不存在则返回“空”；Value(T,e)：返回二叉树T中e结点的值；Root(T)：返回二叉树T的根结点。14.4.1二叉树的基本操作16清华大学黄维通设计制作1二叉树的顺序存储结构#defineMAXLENGTH255#defineTYPEintstructTTree{intnTreeSize;TYPEnode[MAXLENGTH];};typedefst

7、ructTTreeTree;14.4.2二叉树基本操作的实现17清华大学黄维通设计制作顺序存储结构实现ADT二叉树的操作:voidInitTree(Tree*T)//构造空树{inti;T->nTreeSize=0;for(i=0;inode[i]=0;}voidDestroyTree(Tree*T)//销毁树{inti;T->nTreeSize=0;for(i=0;inode[i]=0;}18清华大学黄维通设计制作TYPEParent

8、(TreeT,inte)//返回父结点{if(e>0)returnT.node[(e-1)/2];elsereturn0;}TYPELeftChild(TreeT,inte)//返回二叉树T中e结点的左儿子结点{if(e*2+1