二叉数

二叉树•线性结构：线性表；栈,队列,双队列；串；数组,广义表•非线性结构：树,二叉树；图,网定义和术语•1.树（tree)----•树是n(n≥0)个结点的有限集T,当n=0时，T为空树；•当n0时,(1)有且仅有一个称为T的根的结点,(2)当n1时,余下的结点分为m(m0)个互不相交的有限集T1,T2,...,Tm,•每个Ti(1≤i≤m)也是一棵树,且称为根的子树。•T1={B,C,D,E,F}•T11={C,D,E}•T111={D},112={E}•T12={F}•T2={G,H}•T21={H}•T3={I,J,K,L,M,N,O}•T31={J,K,L,M}•T311={K},T312={L}•T313={M}•T32={N}•T33={O}JCFHIGBAEMKOLND树T例15个结点的树T={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O}CFBEDT1HGT2JIPOT3MKL•2.结点的度(degree)---结点的子树数•3.树的度----树中各结点的度的最大值•4.n度树----度为n的树•5.叶子(终端结点)----度为0的结点•6.分枝结点(非终端结点,非叶子)----度不为0的结点•7.双亲(父母,parent)和孩子(儿子,child)----若结点C是结点P的子树的根,称P是C的双亲，C是P的孩子•8.结点的层(level)----根的层为1，其余任一结点的层等于其双亲的层加1•9.树的深度(depth,高度)----树中各结点的层的最大值•10.兄弟(sibling)----同一双亲的结点互为兄弟•11.堂兄弟(brother-in-law)---同一层号的结点互为堂兄弟BAFDHECG4度树1层2层3层•12.祖先----从树的根到某结点所经分枝上的所有结点为该结点的祖先。•13.子孙----一个结点的所有子树的结点为该结点的子孙。•14.有序树----若任一结点的各棵子树，规定从左至右是有次序的,即不能互换位置,则称该树为有序树。•15.无序树----若任一结点的各棵子树，规定从左至右是无次序的,即能互换位置,则称该树为无序树。BADFECG无序树T1BADFC无序树T1有序树T2有序树T3EGBADFECGBADFCEG==≠二叉树(binarytree)•1.二叉树的定义•二叉树是有限个结点的集合，它或者为空集；或者是由一个根结点和两棵互不相交的，且分别称为根的左子树和右子树的二叉树所组成。•若二叉树为空集，则为空二叉树。二叉树的性质二叉树CAGBEFH≤20=1个≤23=8个≤22=4个≤21=2个2.深度为k的二叉树最多有2k-1个结点20+21+...+2k-1=2k-1二叉树的第i(i≥1)层最多有2i-1个结点深度为k的二叉树最多有2k-1个结点满二叉树（fullbinarytree)----深度为k且有2k-1个结点的二叉树。T1T2T3T4n个结点的满二叉树的深度=log2(n+1)设深度为k∵2k-1＝n2k＝n+1∴k=log2(n+1)二叉树的存储结构•1.顺序结构•(1)n个结点的完全二叉树，使用一维数组:•例.ElemTypetree[n+1]；•chart[7]；ACDBEFT1//ACDBEF123465t[1..6]0123456父子关系元素(结点)t[i]的双亲是t[i/2]2≤i≤n元素(结点)t[i]的左小孩是t[2*i]2i≤n元素(结点)t[i]的右小孩是t[2*i+1]2i+1≤nT1的顺序结构一般二叉树ABECHGT2ABECGDEH1234613t[1..13]12345678910111213父子关系若t[i/2]存在,t[i]的双亲是t[i/2]；2≤i≤n若t[2*i]存在,t[i]的左小孩是t[2*i]；2i≤n若t[2*i+1]存在,t[i]的右小孩是t[2*i+1]。2i+1≤nE9D8T2的顺序结构•链式存储结构•(1)二叉链表structbnode//结点类型{structbnode*lchild；//左孩子指针ElemTypedata；//抽象数据元素类型structbnode*rchild；//右孩子指针}*root,*p；//root,p是指针变量lchilddatarchildpAB∧C∧D∧∧E∧F∧∧G∧root二叉树T1T1的二叉链表CAFBDEG三叉链表structbnode{structbnode*parent,*lchild,*rchild；ElemTypedata；}*root,*p；parentlchilddatarchildpCAFBDEG∧AB∧C∧D∧∧E∧F∧∧G∧root二叉树T2T2的三叉链表双亲左孩子值右孩子•遍历(traverse）二叉树----•按某种规则访问二叉树的每一个结点一次且仅一次的过程。•设:D----访问根结点,输出根结点；•L----递归遍历左二叉树；•R----递归遍历右二叉树。•遍历规则(方案):•DLR----前序遍历(先根,preorder)•LDR----中序遍历(中根,inorder)•LRD----后序遍历(后根,postorder)•●DRL----逆前序遍历•●RDL----逆中序遍历•●RLD----逆后序遍历•1.前序遍历二叉树递归定义：•若二叉树为空，则遍历结束；•否则，执行下列步骤：•(1)访问根结点；•(2)遍历根的左子树；•(3)遍历根的右子树。•例1.前序遍历ABEFCDG●遍历T：●访问A；●遍历T1：●访问B；●遍历T11：●访问E；●左子树为空,遍历结束；●右子树为空,遍历结束。●T11遍历结束。●遍历T12：CADGTBEFTypedefstructBTNode{TElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BTree;/*先序遍历递归算法*/voidPreorderTraverse(BTreeT){if(T){printf(%c,T-data)；PreorderTraverse(T-lchild)；PreorderTraverse(T-rchild)；}}PreorderTraverse1(BiTreeT)/*先序遍历非递归算法*/{structBiTNode*stack[maxsize];/*定义栈*/inttop=0;/*置空栈*/do{while(T){printf(“%c”,T-data);top++;if(top=maxsize)returnoverflow;stack[top]=T;/*根结点进栈*/T=T-lchild;}if(top){T=stack[top--];T=T-rchild;}}while(top||T);}•2.中序遍历二叉树递归定义：•若二叉树为空，则遍历结束；•否则，执行下列步骤：•(1)遍历根的左子树；•(2)访问根结点；•(3)遍历根的右子树。•例1.中序遍历EBFACGD●遍历T：●遍历T1：●遍历T11：●左子树为空,遍历结束●访问E；●右子树为空,遍历结束。●T11遍历结束。●访问B；●遍历T12：TCADGBEF/*中序遍历递归算法*/InorderTraverse(BiTreeT){if(T){InorderTraverse(T-lchild);printf(“%c”,T-data);InorderTraverse(T-rchild);}}•3.后序遍历二叉树递归定义：•若二叉树为空，则遍历结束；•否则，执行下列步骤：•(1)遍历根的左子树；•(2)遍历根的右子树；•(3)访问根结点。•例1.后序遍历EFBGDCA●遍历T：●遍历T1：●遍历T11：●左子树为空,遍历结束●右子树为空,遍历结束。●访问E；●T11遍历结束。●遍历T12：TCADGBEF/*后序遍历递归算法*/PostorderTraverse(BiTreeT){if(T){PostorderTraverse(T-lchild);PostorderTraverse(T-rchild);printf(“%c”,T-data);}}•表达式二叉树•表达式二叉树T=(第一操作数)运算符(第二操作数)•其中：第一操作数----T的左子树•第二操作数----T的右子树•运算符----表达式最后执行的算符•左子树是表达式二叉树•右子树是表达式二叉树运算符第一操作数第二操作数表达式二叉树的一般形式左子树右子树-+CABA+B-C+A*BCA+B*C例表达式二叉树•例表达式：A+B*C-D/（E-F）-+/A*D-BCEF▲前序遍历：-+A*BC/D-EF前缀表示,前缀表达式,波兰式▲中序遍历:A+B*C-D/(E-F)中缀表示,中缀表达式▲后序遍历:ABC*+DEF-/-后缀表示,后缀表达式，逆波兰式表达式二叉树•课堂练习•画出表达式二叉树•A+B*(C–D)/（E-F）-G•课堂练习•画出表达式二叉树•A+B*(C-D)/（E-F）-G+*/B--CDEF表达式二叉树A-G•6.3.5二叉排序树(二叉查找树）•1.定义:如果二叉树的任一结点大于其非空左子树的所有结点，•而小于等于其非空右子树的所有结点，则这棵二叉树•称为二叉排序树(BinarySortTree)。•2.特点：对一棵二叉排序树进行中序遍历，所得的结点序列一•定是递增有序的8514103585401080353LDR：5,8,10,14,35LDR：3,5,8,8,10,35,40,808•判断:下列二叉树是否为二叉排序树？30111815196410556026803010281522T1T230T3•3.生成二叉排序树•设输入序列为：30,11,18,4,55,19,15,70,58303011183011184193011301118419301118455193011184551570193011184551570583011184555515•赫夫曼(Huffman哈夫曼)树及其应用•1.路径长度----路径上分枝的数目(连线的数目)•2.树T的路径长度----从树T的根到其余每个结点的路径长度之和,记作PL(T)T1T2T3PL(T1)=1+1+2+2+2=8PL(T2)=1+2+3+4+5=15PL(T1)=1+1+2+3+3=10•3.树T的带权路径长度----每个叶子的权与根到该叶子的路径•长度的乘积之和，记作WPL(T)••WPL(T)=∑wklk••其中:n---树T的叶子数目•wk---叶子k的权•lk---树T的根到叶子k的路径长度T49226WPL(T)=6*1+3*2+4*3+9*3=51PL(T)=1+1+2+2+3+3=123nk=1•4.最优二叉树/最佳二叉树(optimalbinarytree)/赫夫曼树在具有n个相同叶子的各二叉树中,WPL最小的二叉树。T1531462814●PL(T1)=1+1+2+2+2+2+3+3=16●WPL(T1)=5*3+6*3+3*2+4*2+10*2=67●PL(T2)=1+1+2+2+3+3+4+4=20●WPL(T2)=10*1+6*2+5*3+4*4+3*4=65●PL(T3)=1+1+2+2++2+2+3+3=16●WPL(T3)=5*2+6*2+3*3+4*3+10*2=6341011T237104281861253611428177105T3•5.赫夫曼算法•例给定权集合{4,5,3,6,10}，构造赫夫曼树•1.按权值大小排序：3,4,5,6,10•2.生成森林：536410T1T2T3T4T53.合并两棵权最小的二叉树,并排序,直到为一棵二叉树.5364107561134107341071756113410717561128•课堂练习••给定权集合•{10,1,2,8,4,5}•1.构造赫夫曼树•2.计算树的路径长度PL•3.计算树的带权路径长度WPL•讨论：谁的商品布局合理？为什么？烟酒食品化妆品服装鞋类文化用品艺术品家具古董古董家