树和二叉树

6.1树的类型定义和基本术语6.2二叉树的类型定义及性质6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码6.1树的类型定义和基本术语树的定义定义：树(Tree)是n(n≥0)个结点的有限集T，其中：当n≥1时，有且仅有一个特定的结点，称为树的根(Root)，当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(SubTree)。特点：树中各子树是互不相交的集合。树是一类重要的非线性数据结构，是以分支关系定义的层次结构。A只有根结点的树ABCDEFGHIJKLM有子树的树根子树ABCDEFGHIJMKLA()T1T3T2树根B(E,F(K,L)),C(G),D(H,I,J(M))树的四种表示法：一、树形表示法二、凹入表示法三、嵌套集合表示法四、广义表表示法一、树形表示法二、凹入表示法三、嵌套集合表示法四、广义表表示法ABCDFEGHIJMKLABEKLFCGDHMIJGFKLIJMHABDCE(A(B(E(K,L),F),C(G),D(H(M),I,J)))(树根(子树1，子树2，…，子树n))一、树形表示法二、凹入表示法三、嵌套集合表示法四、广义表表示法ABCDFEGHJMKLABEKGLCFDHMJ(A(B(E(K,G,L),C,F),D(H(M),J)))FKLJMHABDEGC练习基本术语结点:结点的度:树的度:叶子结点:分支结点:一个数据元素+若干指向子树的分支。分支的个数。(结点拥有子树数目)树中所有结点的度的最大值。度为零的结点。度大于零的结点。DHIJM（终端结点）（非终端结点）(从根到结点的)路径：结点的层次:树的深度：由从根到该结点所经分支和结点构成。ABCDEFGHIJMKL从根结点算起，根为第一层，它的孩子为第二层……。树中叶子结点所在的最大层次。孩子结点：某结点子树的根结点称为该结点的孩子结点。双亲结点：孩子结点的上层结点叫该结点的双亲结点。兄弟结点：同一双亲的孩子结点。祖先结点：从根结点到该结点所经分支上的所有结点。子孙结点：以某结点为根的子树中的任一结点称为~。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林。森林：是m（m≥0）棵互不相交的树的集合。ArootBEFKLCGDHIJMF子树之间不存在确定的次序关系（能互换）。子树之间存在确定的次序关系（不能互换）。有序树：无序树：DHIJMDIHJM=双亲在同一层的结点ABCDEFGHIJKLM结点A的度：结点B的度：结点M的度：叶子：结点A的孩子：结点B的孩子：结点I的双亲：结点L的双亲：结点B，C，D为兄弟结点K，L为兄弟树的度：结点A的层次：结点M的层次：树的深度：结点F，G为堂兄弟结点A是结点F，G的祖先结点B的子孙：320B，C，DE，F3K，L，F，G，M，I，JDE14例E，K，L，F4对比树形结构和线性结构的结构特点线性结构树形结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)树的基本操作：(1)initlate(T)初始化操作，置T为空树。例：φ(2)root(T)或root(x)求根函数。例：root(T)=Aroot(k)=Aroot(P)=null(3)parent(T,x)求双亲函数,求树T中结点X的双亲结点。例：parent(T,B)=Aparent(T,A)=null(4)child(T,x,i)求孩子结点函数,求树T中结点X的第i个孩子结点。例：child(T,D,2)=Ichild(T,A,4)=nullchild(T,K,1)=nullGBDCEFIHMJKALT(5)right_sibling(T,x)求右兄弟函数,求树T中结点X的右边的兄弟结点。GBDCEFIHMJKAL例：right_sibling(T,B)=Cright_sibling(T,F)=null(6)crt_tree(x,F)建树函数，生成一棵以X为根、以森林F为子树的树。例:X=AF:BFCJMABFCJM(7)ins_child(y,i,x)插入子树操作，把以结点X为根的树插入为结点y的第i棵子树。例：GBDCEFIHMJKALUVIns_child(D,3,U)GBDCEFIHMJKALUV(8)del_child(x,i)删除子树操作，删除结点X的第i棵子树。del_child(D,1)GBDCEFIJKAL(9)traverse(T)遍历操作，按某个次序访问树中各个结点，并使每个结点只被访问一次。例：ABFCJM先序遍历：A、B、F、C、J、M(10)clear(T)清除结构操作,将树T置为空树。6.2二叉树的类型定义及性质二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：空树只含根结点LR右子树为空树左子树为空树左右子树均不为空树二叉树特点：每个结点至多有二棵子树(即不存在度大于2的结点)。二叉树的子树有左、右之分，其次序不能任意颠倒。NNNLRN思考：二叉树与树的区别？二叉树与无序树的区别二叉树与有序树的区别二叉树就是度为2的有序树吗？否练习：具有3个结点的二叉树有多少种？二叉树的主要基本操作：查找类插入类删除类Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit())//先序遍历;InOrderTraverse(T,Visit())//中序遍历;PostOrderTraverse(T,Visit())//后序遍历;LevelOrderTraverse(T,Visit())//层序遍历;InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c)//根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原右或左子树成为c的右子树。ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);二叉树的重要特性性质1：在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点，2i-1=20=1；假设对所有的j，1≤ji，命题成立;即第j层上至多有2j-1个结点那么，第i-1层至多有2i-2个结点二叉树上每个结点至多有两棵子树，则第i层的结点数至多=2i-22=2i-1。性质2：深度为k的二叉树上至多含2k-1个结点.(k≥1)证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1性质3：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1由此，n1+2n2=n0+n1+n2-1即n0=n2+1两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数.完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。特点:(1)叶子结点只可能在层次最底的两层上出现.(2)对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+1.123456789101112131415abcdefghij1231145891213671014151231145891267101234567123456证明：设完全二叉树的深度为k即k-1≤log2nk因为k只能是整数，因此，k=log2n+1性质4：具有n个结点的完全二叉树的深度为log2n+1则根据性质2得2k-1-1n≤2k-12k-1≤n2k性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲,否则，编号为i/2的结点为其双亲结点;(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。例：112345678910121i=6其双亲为|i/2|=3；其左孩子为2*i=12;i=1是树的根,无双亲;其左孩子为2*i=2,右孩子为2*i+1=3.∵2*i=18122*i+1=1912∴其无左、右孩子。∵2*i+1=1312∴其无右孩子。i=9其双亲为|i/2|=4；6.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;一、二叉树的顺序存储表示例：37217945791851619可用一维数组bt(0:11)作为它的存储结构，将二叉树中编号为i的结点的数据元素存放在分量bt[i－1]中，如图：完全二叉树bt0123456789101192179457918516371左孩子保存在第2i-1号单元中;右孩子保存在第2i号单元中;第i号结点的双亲结点保存在第|i/2|-1号单元中;实现：按满二叉树中结点的编号，依次存放二叉树中的数据元素。特点：结点间关系蕴含在其存储位置中；浪费空间，适于存满二叉树和完全二叉树。abcdefgabcde0000fg1234567891011二、二叉树的链式存储表示1.二叉链表2．三叉链表3．线索链表typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;C语言的类型描述如下:1.二叉链表lchilddatarchild结点结构:ADEBCFrootABDCFE在有n个结点的二叉链表中，有？个空指针域n+1typedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild,*parent;//左右孩子指针、双亲指针}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:2．三叉链表ADEBCFrootABDCFE练习：画出下面二叉树的三叉链表。abcdefgh6.4二叉树的遍历一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、中序遍历算法的非递归描述遍历：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。即找一个完整而有规律的走法，得到树中所有结点的一个线性排列。一、问题的提出“访问”的含义可以很广，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。对“二叉树”而言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。DLRLDR、LRD、DLRRDL、RLD、DRL二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法