第6章-树和二叉树

东北大学信息学院计算机应用技术研究所杨雷[e-mail]第六章树和二叉树6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码6.1树的类型定义数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：•树的表示AABCDEFGHIJKL•树的其他表示嵌套集合、广义表表示、凹入表示GCABDHIJEKFL(A(B(E,F(K,L)),C(G),D(H,I,J)))A*****************B****************E***************F***************K**************L**************C****************G***************D****************H***************I***************J***************基本术语结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。基本操作：查找类插入类删除类Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树对比树型结构和线性结构的结构特点线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)6.2二叉树的类型定义二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树二叉树的主要基本操作：查找类插入类删除类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);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);二叉树的重要特性在二叉树的第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对所有的j，1≤ji，命题成立；二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。推广：深度为h的k叉树中，第i层上最多具有个结点。ki－1性质1：•深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1。性质2：推广：深度为h的k叉树至多含个结点。(kh-1)/(k-1)•对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：利用结点总数=结点总度数+1n0+n1+n2=n1+2*n2+1=n0=n2+1推广：已知一棵树度为m的树中有n1个度为1的结点，n2个度为2的结点，…nm个度为m的结点，问该树中有多少片叶子？证明：根据结点总数=结点总度数+1n0+n1+n2+…+nm=n1+2*n2+…+m*nm+1=n0=1+n2+…+(m-1)nm性质3：两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。1.前k-1层为满二叉树；2.第k层结点依次占据最左边的位置；3.一个结点有右孩子，则它必有左孩子；4.度为1的结点个数为0或15.叶结点只能在层次最大的两层上出现；123456789101112131415abcdefghij具有n个结点的完全二叉树的深度为log2n+1。证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立2k-1≤n2k2k-1-1…2k-12k-1———第k-1层———第k层…性质4：•具有n个结点的完全二叉树的深度为log2n+1。证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立2k-1≤n2k对不等式取对数，有：k-1≤log2n＜k即：log2n＜k≤log2n+1由于k是整数，故必有k＝log2n+1log2n+1[log2n]log2n[log2n]+1k所在区间性质4：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。性质5：–例：若一个完全二叉树有1450个结点，则度为1的结点个数为1，度为2的结点个数为724，叶子结点的个数为725，有725个结点有左孩子，有724个结点有右孩子；该树的高度为11。(性质3、性质4以及完全二叉树的特征)6.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;一、二叉树的顺序存储表示例如:ABCDEFABDCEF0123456789101112131401326二、二叉树的链式存储表示1.二叉链表2．三叉链表3．双亲链表4．线索链表ADEBCFrootlchilddatarchild结点结构:1.二叉链表typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:ADEBCFroot2．三叉链表parentlchilddatarchild结点结构:typedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild;//左右孩子指针structTriTNode*parent;//双亲指针}TriTNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:0123456B2C0A-1D2E3F4dataparent结点结构:3．双亲链表LRTagLRRRLtypedefstructBPTNode{//结点结构TElemTypedata;int*parent;//指向双亲的指针charLRTag;//左、右孩子标志域}BPTNodetypedefstructBPTree{//树结构BPTNodenodes[MAX_TREE_SIZE];intnum_node;//结点数目introot;//根结点的位置}BPTree6.4二叉树的遍历一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、遍历算法的应用举例五、遍历算法的非递归描述顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一、问题的提出“访问”的含义可以很广，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。对“二叉树”而言，可以有三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；3．先右（子树）后左（子树）的遍历。二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法–先/中/后序遍历的区别如右图，三者经过的搜索路线是相同的；只是访问结点的时机不同。每一结点在整个搜索路线中会经过3次：•第一次进入到该结点此时访问该结点，称为先序遍历•由左子树回溯到该结点此时访问该结点，称为中序遍历•由右子树回溯到该结点此时访问该结点，称为后序遍历若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：遍历结果：-+a*b-cd/ef表达式语法树若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：表达式语法树遍历结果：a+b*c-d-e/f若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：表达式语法树遍历结果：abcd-*+ef/-两个推论•若已知一棵二叉树的前序序列和中序序列,则可以唯一的确定这棵二叉树.•若已知一棵二叉树的后序序列和中序序列,则也可以唯一的确定这棵二叉树.例：已知前序序列为{ABHFDECKG}，中序序列为{HBDFAEKCG},试构造二叉树。解：过程如下：算法的递归实现–遍历算法的递归实现•二叉树的递归定义性质，决定了它的很多算法都可用递归实现，遍历算法就是其中之一。•对于二叉树的遍历，可以不去具体考虑各子问题(左子树、根、右子树)的遍历结果是什么，而去考虑如何由各子问题的求