数据结构ppt教学课件-第六章树和二叉树

《数据结构ppt教学课件-第六章树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树引言：树型结构是一类重要的非线性结构。树型结构是结点之间有分支，且具有层次关系的结构，非常类似于自然界中的树。树结构在客观世界大量存在。例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用：在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；Windows操作系统中对磁盘文件的管理。……教师学生其他人员2007级2008级2009级2010级……南信大数理院计算机院语院……叶子根子树第六章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.

2、5哈夫曼树及应用树的定义、术语、操作二叉树定义、性质、操作二叉树的存储结构(重点)顺序存储、链接存储线索二叉树(难点)（特殊的链接存储结构）二叉树运算递归遍历非递归遍历二叉树遍历(重点)二叉树其他运算树的存储结构森林与二叉树的转换树和森林的遍历二叉树应用哈夫曼树及其应用(重点、难点)内容及重、难点6.16.26.26.36.36.46.56.1树的定义与术语一、树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则：有一个特定的元素称之为根(root)的结点，除根以外的其他结点划分为m(m0)个互不相交的

3、有限集合T1,…,Tm，每个集合又是一棵树，并且称之为根的子树(subTree)。A只有根结点的树ABCDEFGHIJKLM有子树的树根子树例：ACGBDEFKLHMIJ1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径。(非空)树结构特点：~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)

4、其它数据元素(一个前驱、多个后继)ABCDEFGHIJKLM树形表示(A(B(E(K,L),F),C(G),D(H(M),I,J))广义表二、树的表示方法IJFKLGMCCDBEA文氏图凹入表结点(node)结点的度(degree)结点的子树个数分支(branch)结点度不为0的结点根(root)即根结点(没有前驱)叶(leaf)结点度为0的结点孩子(child)结点双亲(parent)结点兄弟(sibling)结点具有同一双亲的结点三、树的基本术语ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0分支结点：A,B,C,D

5、,E,H叶结点：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟祖先(ancestor)结点结点的祖先是从根到该结点所经分支上的所有结点.子孙(descendant)结点以某结点为根的子树中的任一结点都为该结点的子孙.结点的层次(level)根结点的层数为1，其余结点的层数为双亲结点的层数加1树的高度(depth)树中结点的最大层数树的度(degree)树的基本术语(续)ABCDEFGHIJKLM结点K的祖先：A,B,E结点B的子孙：E,F,K,L树的

6、度：3树的高度：4结点A的层次：1结点M的层次：4有序树——子树的次序不能互换无序树——子树的次序可以互换森林（Forest）——m棵互不相交的树的集合基本术语（续）：树的运算分3大类：第一类：查找类遍历树中每个结点、求树的状态（如树高度、判树空）查找满足某种特定关系的结点,如查找根结点等第二类，插入类包括初始化空树、构造树、在树的当前结点上插入一个新结点等；第三类，删除类包括清空树、销毁树、删除树中结点。四、树的基本操作（P118）五、树的抽象数据类型定义ADTTree{数据对象D：由n个具有相同特性的元素构成的集合数据关系R：若D为空集

7、，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树.基本操作P：Root(T)//求树的根结点Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子CreateTree(&T,definition)//构造树InitTree(&T)//初始化置空树TreeEmpty(T)

8、//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历Assign(T,cur_e,value)//给当前结点赋值Ins