数据结构与算法 教学课件 作者 王曙燕 chapter6 树和二叉树.ppt

《数据结构与算法 教学课件 作者 王曙燕 chapter6 树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、16.2树的概念第6章树和二叉树6.3二叉树6.4二叉树的遍历6.5线索二叉树6.6树和森林6.1应用实例6.7哈夫曼树及其应用6.8实例分析与实现6.9算法总结2第6章树和二叉树实例一：数据压缩问题在信息传输、数据压缩问题中，我们总是希望找到一种编码能将待处理数据压缩得尽可能的短。6.1应用实例实例二：表达式的树形表示任意一个表达式，均可以用树形结构来表示，由于大部分的算术运算符有两个操作数，所以可用二叉树来表示一个算术表达式，表达式树中并无括号，但其结构却有效地表达了其运算符间的运算次序。另外，利用二叉树的遍历等操作，还可得到表达式的三种不同的表示形式：前缀表达式、中缀表达式、后缀表达式

2、，并可以实现表达式的求值运算。3实例三：等价类划分问题等价关系是现实世界中广泛存在的一种关系，许多应用问题可归结为按给定的等价关系将集合划分为等价类的问题。问题可描述为：若R是集合S上的一个等价关系，则由R可得到集合S的唯一划分，即可以按R将S划分为若干个不相交的子集S1，S2，…，这些子集的并集等于S，子集Si称为S的R等价类。第6章树和二叉树6.1应用实例实例四：N皇后问题N皇后问题要求在一个NN格的棋盘上放置N个皇后，使其互不攻击。按规则，互不攻击的约束条件为：任意两个皇后不能处于同一行、同一列或同一对角线上，现要求给出满足约束条件的所有棋盘布局。46.2树的概念定义：数据关系R：若

3、D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。第6章树和二叉树数据对象D：D是具有相同特性的数据元素的集合。5例如：第6章树和二叉树ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2根6.2树的概念6表示方法：第6章树和二叉树①树型表示bacghdefij6.2树的概念7表示方法：第6章树和二叉树②文氏图表示ijdfghabce6.2树的概念8表示方法：第6章树和二叉

4、树③凹入表示abdeijfcgh6.2树的概念9表示方法：第6章树和二叉树④嵌套括号表示a(b(d,e(i,j),c(g,h)))6.2树的概念10有向树：第6章树和二叉树有确定的根；树根和子树根之间为有向关系。有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。6.2树的概念11树型结构和线性结构的结构特点第6章树和二叉树第一个数据元素(无前驱)根结点(无前驱)最后一个元素(无后继)。多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)线性结构树型结构其它数据元素(一个前驱、多个后继)6.2树的概念12第6章树和二叉树基本术语①结点：数据元素+若干指向子树的分支②

5、结点的度:分支的个数③树的度:树中所有结点的度的最大值④叶子结点:度为零的结点⑤分支结点:度大于零的结点⑥(从根到结点的)路径：由从根到该结点所经分支和结点构成。ABCDEFGHIJMKL6.2树的概念13数据结构第6章树和二叉树基本术语⑦孩子结点：一个结点的直接后继⑧双亲结点:一个结点的直接前驱⑨兄弟结点:同一双亲结点的孩子结点之间互称~。⑩堂兄弟、祖先结点、子孙结点结点的层次:假设根结点的层次为1，依次累加。树的深度：树中叶子结点所在的最大层次ABCDEFGHIJMKL森林：是m（m≥0）棵互不相交的树的集合6.2树的概念14第6章树和二叉树基本操作①InitTree(Tree);②De

6、storyTree(Tree);③CreatTree(Tree);④TreeEmpty(Tree);⑤Root(Tree);⑥Parent(Tree,x);⑦FirstChild(Tree,x);⑧NextSibling(Tree,x);⑨InsertChild(Tree,p,Child);⑩DeleteChild(Tree,p,i);6.2树的概念15第6章树和二叉树定义：满足以上两个条件的树型结构为二叉树。①每个结点的度都不大于2；②每个结点的孩子结点次序不能任意颠倒。二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。ABEFKLDHJM根结点左子树

7、右子树6.2树的概念166.3二叉树第6章树和二叉树形态：空二叉树只有根结点的二叉树只有右子树的二叉树左、右子树均非空的二叉树只有左子树的二叉树5种176.3二叉树第6章树和二叉树基本操作：①Initiate(bt);②Destory(bt);③Creat(bt);④Empty(bt);⑤Root(bt);⑥Parent(bt,x);⑦LeftChild(bt,x);⑧RithtChild(bt,x);⑨Tr