资源描述：
《数据结构第六章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树1※教学内容：树的基本概念；二叉树的性质和存储结构；遍历二叉树和线索二叉树;树的存储结构和遍历；哈夫曼树及其应用；※教学重点：二叉树的结构特点；二叉树各种存储结构的特点及适用范围；按各种次序遍历二叉树的递归和非递归算法；二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法；树的各种存储结构及其特点；编写树的各种运算的算法；建立最优二叉树和哈夫曼编码的方法。※教学难点：按各种次序遍历二叉树的非递归算法。26.1树的类型定义第6.2二叉树的类型定义六章6.3二叉树的存储结构6.4二叉
2、树的遍历树和6.5线索二叉树二叉6.6树和森林树6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码36.1树的类型定义一、树的定义树是n（n≥0）个结点的有限集。当n=0时称为空树；在任意一棵非空树中，有且仅有一个称为根的结点，其余的结点可分为m(m≥0)个互不相交的有限集T1,T2,…,Tm,其中每一个集合又称为一棵树，并且称为根的子树。同理，每一棵子树又可以分为若干个互不相交的有限集……4二、抽象数据类型树的定义ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称
3、为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。5基本操作：查找类插入类删除类}ADTTree6查找类：Root(T)//求树的根结点Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//
4、求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历7插入类：InitTree(&T)//初始化置空树CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树8删除类：ClearTree(&T)//将树清空DestroyTree(&T)//销毁树的
5、结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树9例如:ABCDEFGHIJKLMA(B(E,F(K,L)),C(G),D(H,I,J(M)))树根TTT12310D有向树：HIJ(１)有确定的根；M(２)树根和子树根之间为有向关系。有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。11对比树型结构和线性结构的结构特点线性结构树型结构第一个数据元素根结点(无前驱)(无前驱)最后一个数据元素多个叶子结点(无后继)(无后继)其它数据元素其它数据元素(一个前驱、
6、(一个前驱、一个后继)多个后继)12三、基本术语D树的结点：包含一个数据元素HIJ及若干个指向其子树的分支；M结点的度：一个结点拥有的子树数目(分支数)；树的度：一棵树上所有结点度的最大值；叶子结点（终端结点）：度为零的结点；分支结点（非终端结点）：度大于零的结点；(从根到结点的)路径：由从根到该结点所经分支和结点构成；13孩子结点：结点的子树的根称为该结点的孩子结点；双亲结点：相应地，该结点称为孩子的双亲结点；兄弟：具有同一父结点的子结点互称兄弟；堂兄弟：其双亲在同一层的结点互为堂兄弟；祖先结点：从
7、根到该结点所经分支上的所有结点；子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；ABCDEFGHIJKLM14结点的层次：从根结点到该结点所经过的路径长度加1；树的深度：树中叶子结点具有的最大层次数；有序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树；第一个孩子：在有序树中，最左边的子树的根称为第一个孩子；A最后一个孩子：最右边的子树的根称为最后一个BCD孩子；EFGHIJKLM15森林：是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即
8、为森林。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点FrootF被称为子树森林ABCDEFGHIJKLM166.2二叉树的类型定义一、二叉树的定义二叉树是n(n≥0)个结点的有限集合，这个集合或是空集，或是由一个根结点以及两棵互不相交的、被称为根的左子树和右子树所组成；左子树和右子树分别又是一棵二叉树。特点：每个结点至多只有两棵子树，且二叉树的子树有左右之分，其次序不能任意颠倒，互不相交。17根结点ABECFDGHK左子
