树和二叉树数据结构

线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树与线索二叉树6.4树和森林6.5霍夫曼树及其应用1.掌握二叉树的基本概念、性质和存储结构2.熟练掌握二叉树的前、中、后序遍历方法3.了解线索化二叉树的思想4.熟练掌握：霍夫曼树的实现方法、构造霍夫曼编码的方法5.了解：森林与二叉树的转换，树的遍历方法教学目标6.1树的定义和基本术语ACBGFEHIJDMKLA树是n个结点的有限集T1T2T3ADTTree{数据对象D:数据关系R:基本操作P：}ADTTree若D为空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明D是具有相同特性的数据元素的集合。//至少有15个树的抽象数据类型定义ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示ABFEKLGCDHMIJ嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)))广义表树的其它表示方式根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。ACBGFEHIJDMKL基本术语——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点双亲孩子兄弟堂兄弟祖先子孙ACBGFEHIJDMKL基本术语——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值——指所有结点中最大的层数ACBGFEHIJDMKL层次1234基本术语MINEBDAGJKCFLH1)哪是根节点2）哪是叶子节点3）哪个节点是G的双亲4）哪些是G的祖先5）哪些节点是G的孩子6）哪些节点是E的子孙7）哪些节点是E的兄弟8）节点B和N的层次号是分别是多少9）树的深度是多少10）以节点C为根的子树的深度是多少11）树的度数是多少MINEBDAGJKCFLH6.2二叉树普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。二叉树基本特点：•结点的度小于等于2•有序树（子树有序，不能颠倒）二叉树的五种不同形态具有3个结点的二叉树可能有几种不同形态？普通树呢？练习5种/2种•一棵度为2的树与一棵二叉树有何区别？•解：二叉树是颗有序树，但度为2的树则未必有序。ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明④……//关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个二叉树的抽象数据类型定义性质1:在二叉树的第i层上至多有2i-1个结点二叉树的性质提问：第i层上至少有个结点？性质2:深度为k的二叉树至多有2k-1个结点提问：深度为k时至少有个结点？1k1891011124526731891011124526731nB1212nnB11212nnn012nnn性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）189101112131415452673满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）189101112452673特殊形态的二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。189101112131415452673189101112452673满二叉树和完全二叉树的区别一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（）。练习2500性质4:具有n个结点的完全二叉树的深度必为log2n＋1189101112452673k层nk-1层121k12k12121kkn性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。二叉树的顺序存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。abcde0000fg012345678910abcdefg特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树单支树二叉树的顺序存储DATAPARENTLCHILDRCHILDlchilddatarchildlchilddatarchildparent二叉树的链式存储ABCDEFGABCDEFG^^^^^^^^二叉链表typedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild;//左右孩子指针}BiNode,*BiTree;分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。空指针数目＝2n－(n-1)=n+1在n个结点的二叉链表中，有个空指针域练习ABCDEFG^^^^^^^^n+1三叉链表ABCDEFGABCDEFG^^^^^^^^^lchilddataparentrchildtypedefstructTriTNode{TelemTypedata;structTriTNode*lchild,*parent,*rchild;}TriTNode,*TriTree;6.3遍历二叉树和线索二叉树遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。ROOTLCHILDRCHILDDLRDLRLDRLRDDRLRDLRLD遍历规则先左后右先序遍历：中序遍历：后序遍历：ABCDEABDECDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根+*A*/EDCB先序遍历+**/ABCDE前缀表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB用二叉树表示算术表达式DLRADLRDLRBDCDLRADBC先序遍历序列：ABDC若二叉树为空，则空操作否则访问根结点(D)前序遍历左子树(L)前序遍历右子树(R)遍历的算法实现－先序遍历则三种遍历算法可写出:遍历的算法实现－－用递归形式格外简单！longFactorial(longn){if(n==0)return1;//基本项elsereturnn*Factorial(n-1);//归纳项}回忆:StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{coutT-data;//访问根结点PreOrderTraverse(T-lchild);//递归遍历左子树PreOrderTraverse(T-rchild);//递归遍历右子树}}先序遍历算法StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{coutT-data;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T左是空返回pre(TR);T左是空返回T右是空返回T左是空返回T右是空返回pre(TR);先序序列：ABDC遍历的算法实现－中序遍历若二叉树为空，则空操作否则:中序遍历左子树(L)访问根结点(D)中序遍历右子树(R)ADBCLDRBLDRLDRADCLDR中序遍历序列：BDACStatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{InOrderTraverse(T-lchild);//递归遍历左子树coutT-data;//访问根结点InOrderTraverse(T-rchild);//递归遍历右子树}}中序遍历算法遍历的算法实现－后序遍历若二叉树为空，则空操作否则后序遍历左子树(L)后序遍历右子树(R)访问根结点(D)ADBCLRDLRDLRDADCLRDB后序遍历序列：DBCAStatusPostOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{PostOrderTraverse(T-lchild);//递归遍历左子树PostOrderTraverse(T-rchild);//递归遍历右子树coutT-data;//访问根结点}}后序遍历算法StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{coutT-data;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}}StatusPostOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);coutT-data;}}StatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{InOrderTraverse(T-lchild);coutT-data;InOrderTraverse(T-rchild);}}遍历算法的分析如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径上，每个结点经过3次。AFEDCBG第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历遍历算法的分析AFEDCBG时间效率:O(n)//每个结点只访问一次空间效率:O(n)//栈占用的最大辅助空间遍历算法的分析ABCDEFGA^B^C^D^E^F^^G^按先序遍历序列建立二叉树的二叉链表例：已知先序序列为：ABCDEGF（动态演示）二叉树的建立（算法6.3）计算二叉树结点总数计算二叉树叶子总数计算二叉树高度二叉树遍历算法的应用若二叉树中各结点的值均不相同，则：由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。重要结论练习已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECB