数据结构_严蔚敏_第6章.ppt

1、第六章：树和二叉树，教学目标和要求。1.掌握二叉树的结构特征，理解相应的证明。2.熟悉二叉树各种存储结构的特点和应用范围。3.掌握二叉树遍历的递归和非递归算法。4.掌握二元线索树的相关算法。5.熟悉树木的各种存储结构和特点，掌握树木、森林和二叉树的方法。6.了解最优树的特征，掌握最优树和霍夫曼编码方法。1数据的逻辑结构，2数据的存储结构，3数据的操作：检索、排序、插入、删除、修改等。主要有三个问题：a线性结构，b非线性结构，a顺序存储，b链式存储，线性表，堆栈，队列，树形结构，图形结构，数据结构，树形结构，全校档案管理的组织模式，树形结构中节点之间的层次连接关系，6.1树形定义，6.2二叉树类

2、型定义和6.3二叉树存储结构，6.5线索二叉树，6.6树和森林表示，6.7树和森林遍历，6.8霍夫曼树和霍夫曼编码，6.1树形定义，数据对象如果d是一个空集合，它被称为空树。否则， (1)在d中有一个唯一的数据元素根叫做根；(2)当n1时，其余节点可被划分为m (m0)个不相交的有限集合t1、T2和TM，每个子集本身就是一棵符合这一定义的树，称为根的子树。数据关系r:a，b，c，d，e，f，g，h，I，j，m，k，l，a (b (e，f (k，l)，c (g)。根(T) /找到树的根节点，找到类：值(T，cur_e) /找到当前节点的元素值，父(T，cur_e) /找到当前节点的父节点，左子(

3、T，cur_e) /找到当前节点的最左边的子节点，右兄弟)。Cur_e) /查找当前节点的右兄弟树空(T) /确定树是否为空，树深度(T) /查找树的深度，遍历树(T，访问()/遍历，初始化树(值(T，e)；家长(T，e)；LeftChild(T，e)；儿童权利(T，e)；左同胞(T，e)；右同胞(T，e)；位为空(T)；比特深度；预订旅行(测试，访问()；在下一次旅行中(测试，访问()；订单后遍历(测试，访问()；水平顺序遍历(测试，访问()；InitBiTree(，ClearBiTree(，是二叉树的一个重要性质，性质1:二叉树的第I层最多有2i-1个节点。(i1)归纳证明：归纳基础：归纳

4、假设：归纳证明：当i=1层时，只有一个根节点：2i-1=20=1；假设这个命题对所有的J，1 j i都成立；二叉树上的每个节点最多有两个子树，那么第I层中的节点数=2i-2 2=2i-1。属性2:深度为k的二叉树最多包含2k-1个节点(k1)。基于上述性质，证明了深度为k的二叉树的节点数至多为20 21 2k-1=2k-1。属性3:对于任何二叉树，如果它包含n0个叶节点和n2个2级节点，则必须有一个关系：n0=N2 1。证明：让二叉树上的节点总数n=n0 n1 n2和分支总数b=n1 2n2和b=n-1=n0 n1 n2-1，因此，n0=n2 1。两种特殊的二叉树：全二叉树：指深度为k，包含2

5、k-1个节点的二叉树。完整二叉树：树中的n个节点与完整二叉树中编号为1到n的节点一一对应。1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，A，B，C，D，E，F，G，H .根据第二个性质，证明了如果完全二叉树的深度是k，那么2k-1 n 2k就是k-1 log2n k .因为k只能是整数，所以k=log2n 1。，属性5:如果具有n个节点的完整二叉树从上到下和从左到右从1到n编号，则完整二叉树中编号为I的任何节点：(1)如果i=1，则该节点是二叉树的根，没有父节点；否则，编号为i/2的节点是其父节点；(2)如果为2，则该节点没有剩余的子节点；否则，编号为2i的节点是它的

6、左子节点；(3)如果2i 1n，则该节点没有右子节点；否则，编号为2i 1的节点就是它的右子节点。6.3二叉树的存储结构，2。二叉树的链式存储表示，1。二叉树的顺序存储表示，#定义最大树大小100 /二叉树的最大节点数。/单元0存储根节点SqBiTree bt1.二叉树的顺序存储表示，例如，a，b，c，d，e，f，a b d c e f，0 1 2 3 4 5 6 7 8 9 10 11 12 13，1，4秒，二叉树的链式存储表示，1。二进制链表。Trident链表，3个父链表，4个线索链表，a、d、e、b、c、f、根、lchild结构BiTNode *lchild，* rchild/左右子指

7、针BiTNode，* BiTree，lchild data rchild，node structure :c语言的类型描述如下：a，d，e，b，c，f，root，struct TriTNode * lchild，* rchild/左右子指针结构TriTNode *父级；/父指针TriTNode，* TriTree，父lchild data rchild，节点结构：C语言的类型描述如下：0 1 2 3 4 5 6，数据父，节点结构：3父链表，lrtag，l r r l，typedef结构bpt node/节点结构远程数据；int *父级；/指向父级的指针字符LRTag/左右子标记字段BPTNod

8、e typedef结构BPTree /树结构BPTNode nodesMAX _ TREE _ SIZEint num _ node/根中的节点数；/根节点BPTree的位置，6.4二叉树的遍历，1。提出问题。从左到右的遍历算法。算法的递归描述，4。中序遍历算法的非递归描述。遍历算法的应用实例，沿着一定的搜索路径访问二叉树中的节点，使每个节点只被访问一次。1.当问题出现时，“访问”的含义可能非常广泛，例如输出节点的信息等。“遍历”是任何类型的操作。对于线性结构，只有一个搜索路径(因为每个节点只有一个后继节点)，所以不需要单独讨论。然而，二叉树是一个非线性结构，每个节点有两个后继节点，因此存在一

9、个如何遍历的问题，即遍历什么样的搜索路径。对于“二叉树”，可以有三种搜索路径：(1)从上到下分层遍历；2遍历左(子树)和右(子树)；3遍历右(子树)然后左(子树)。2。遍历算法从左到右，一阶(根)，中间阶(根)，最后阶(根)，如果二叉树为空，则进行空操作；否则，(1)访问根节点；(2)首先遍历左子树；(3)首先遍历右子树。优先遍历算法(根):如果二叉树是空的，它就是空的；否则，(1)以中间顺序遍历左边的子树；(2)访问根节点；(3)以中间顺序遍历右子树。中序(根)遍历算法：如果二叉树为空，则为空操作；否则，(1)以下一个顺序遍历左边的子树；(2)依次遍历右子树；(3)访问根节点。后序(根)遍历

10、算法：课堂提问：具有以下结构的二叉树写出了前序、中序和后序遍历的顺序，3。算法的递归描述，void preorder (bitree t，void(* visit)(teely PE/遍历右子树，4)。中序遍历算法的非递归描述。返回空值；同时按下按钮；T=T-l child；返回T；void in order _ I (bitree t，void (* visit)(远程类型/堆栈空表示遍历结束/而/Inorder_I，5。遍历算法的例子，1。计算二叉树中叶节点的数量(第一次遍历)，2。计算二叉树的深度(第二次遍历)，3。复制二叉树(后序列遍历)；4.建立二叉树的存储结构；1.计算二叉树中叶节

11、点的数量。该算法的基本思想是：首先遍历二叉树(或中间或后序列)，找到叶节点，并在遍历过程中对它们进行计数。因此，有必要在遍历算法中添加一个“计数”参数，并将算法中“访问节点”的操作改为：如果是叶子，计数器将增加1。void countleaf (bitree t，int/if/countleaf，2，求二叉树的深度(后序遍历)，算法的基本思想是：从二叉树深度的定义可以看出，二叉树的深度应该是其左右子树深度的最大值加1。因此，需要分别获得左和右子树的深度。算法中“访问节点”的操作是获取左右子树的最大深度，然后加1。首先，分析了二叉树的深度与其左右子树的关系。int Depth (BiTree T

12、) /返回二叉树的深度，如果(！t)深度值=0；否则深度=深度；深度=深度(丁字裤)；深度值=1(深度深度？depth left : depth right)；返回深度值；复制二叉树的基本操作是生成一个节点。根元素、t、左子树、右子树、根元素、NEWT、左子树、右子树、(后顺序遍历)、bitnode * gettrineode(teeltypeitem、bitnode * lptr、)。(T=(BitNode *)malloc(sizeof(BitNode)退出(OVERFLOW)；T-数据=项目。T- lchild=lptr。t-archild=rptr。返回T；生成一个二叉树节点(其数据字

13、段为item，左指针字段为lptr，右指针字段为rptr)，位节点* copytree(位节点* t) if(！返回空值；如果(T-l child)new ptr=CopyTree(T-l child)；/复制左子树，否则newlptr=NULL如果(T-archild)new rptr=CopyTree(T-archild)；/复制右子树，否则newrptr=空；NewT=GetStreenode(T-data，new ptr，new rptr)；返回newT/copytree，a，b，c，d，e，f，g，h，k，d，c，b，h，k，g，f，:表示以字符串的形式，根的左子树和右子树定义一个二叉树，如：A，B，C，D，用字符！“说、(乙(！C(！嘿！)，D(！嘿！)，空树，只有一个根节点的二