• 1. 二叉树
  • 2. 线性结构: 线性表;栈,队列,双队列;串;数组,广义表 非线性结构:树,二叉树;图,网
  • 3. 定义和术语1.树(tree)---- 树是n(n≥0)个结点的有限集T,当n=0时,T为空树; 当n>0时,(1)有且仅有一个称为T的根的结点,(2)当n>1时, 余下的结点分为m(m>0)个互不相交的有限集T1,T2,...,Tm , 每个Ti(1≤i≤m)也是一棵树,且称为根的子树。
  • 4. 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
  • 5. 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层
  • 6. 12.祖先----从树的根到某结点所经分枝上的所有结点为该结点的祖先。 13.子孙----一个结点的所有子树的结点为该结点的子孙。 14.有序树----若任一结点的各棵子树,规定从左至右是有次序的,即不能互换位置,则称该树为有序树。 15.无序树----若任一结点的各棵子树,规定从左至右是无次序的,即能互换位置,则称该树为无序树。 BADFECG无序树T1BADFC无序树T1有序树T2有序树T3EGBADFECGBADFCEG==≠
  • 7. 二叉树(binary tree)1.二叉树的定义 二叉树是有限个结点的集合,它或者为空集;或者是由一个根结点和两棵互不相交的,且分别称为根的左子树和右子树的二叉树所组成。 若二叉树为空集,则为空二叉树。
  • 8. 二叉树的性质二叉树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个结点
  • 9. 满二叉树(full binary tree)---- 深度为 k 且有2k-1个结点的二叉树。T1T2T3T4n个结点的满二叉树的深度=log2(n+1) 设深度为k ∵ 2k - 1=n 2k=n + 1 ∴ k=log2(n+1)
  • 10. 二叉树的存储结构1.顺序结构 (1) n个结点的完全二叉树,使用一维数组: 例. ElemType tree[n+1]; char t[7];ACDBEFT1//ACDBEF123465t[1..6]0 1 2 3 4 5 6父子关系  元素(结点)t[i]的双亲是t[i/2] 2≤i≤n  元素(结点)t[i]的左小孩是t[2*i] 2i≤n  元素(结点)t[i]的右小孩是t[2*i+1] 2i+1≤nT1的顺序结构
  • 11. 一般二叉树ABECHGT2ABECGDEH1234613t[1..13]1 2 3 4 5 6 7 8 9 10 11 12 13 父子关系  若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的顺序结构
  • 12. 链式存储结构 (1)二叉链表 struct bnode //结点类型 { struct bnode * lchild; //左孩子指针 ElemType data; //抽象数据元素类型 struct bnode * rchild; //右孩子指针 } *root, *p; //root,p是指针变量lchild data rchildpAB∧C∧D∧∧E∧F∧∧G∧root二叉树T1T1的二叉链表CAFBDEG
  • 13. 三叉链表 struct bnode { struct bnode *parent,*lchild,*rchild ; ElemType data; } *root, *p;parent lchild data rchildpCAFBDEG∧AB∧C∧D∧∧E∧F∧∧G∧root二叉树T2T2的三叉链表双亲 左孩子 值 右孩子
  • 14. 遍历(traverse)二叉树---- 按某种规则访问二叉树的每一个结点一次且仅一次的过程。 设: D----访问根结点,输出根结点; L----递归遍历左二叉树; R----递归遍历右二叉树。 遍历规则(方案):  DLR----前序遍历(先根,preorder)  LDR----中序遍历(中根,inorder)  LRD----后序遍历(后根,postorder) ● DRL----逆前序遍历 ● RDL----逆中序遍历 ● RLD----逆后序遍历
  • 15. 1.前序遍历二叉树递归定义: 若二叉树为空,则遍历结束; 否则,执行下列步骤: (1) 访问根结点; (2) 遍历根的左子树; (3) 遍历根的右子树。 例1. 前序遍历 ABEFCDG● 遍历T: ● 访问A; ● 遍历T1: ● 访问B; ● 遍历T11: ● 访问E; ● 左子树为空,遍历结束; ● 右子树为空,遍历结束。 ● T11遍历结束。 ● 遍历T12:CADGTBEFTypedef struct BTNode { TElemType data; struct BTNode *lchild,*rchild; }BTNode,*BTree; /*先序遍历递归算法*/ void PreorderTraverse(BTree T) { if(T) { printf("%c",T->data); PreorderTraverse(T->lchild); PreorderTraverse(T->rchild); } }
  • 16. PreorderTraverse1(BiTree T) /*先序遍历非递归算法*/ { struct BiTNode *stack[maxsize]; /*定义栈*/ int top=0; /*置空栈*/ do{ while(T) { printf(“%c”,T->data); top++; if(top>=maxsize) return overflow; stack[top]=T; /*根结点进栈*/ T=T->lchild; } if(top) { T=stack[top--]; T=T->rchild; } }while(top||T); }
  • 17. 2.中序遍历二叉树递归定义: 若二叉树为空,则遍历结束; 否则,执行下列步骤: (1) 遍历根的左子树; (2) 访问根结点; (3) 遍历根的右子树。 例1. 中序遍历 EBFACGD● 遍历T: ● 遍历T1: ● 遍历T11: ● 左子树为空,遍历结束 ● 访问E; ● 右子树为空,遍历结束。 ● T11遍历结束。 ● 访问B; ● 遍历T12:TCADGBEF/*中序遍历递归算法*/ InorderTraverse(BiTree T) { if(T) { InorderTraverse(T->lchild); printf(“%c”,T->data); InorderTraverse(T->rchild); } }
  • 18. 3.后序遍历二叉树递归定义: 若二叉树为空,则遍历结束; 否则,执行下列步骤: (1) 遍历根的左子树; (2) 遍历根的右子树; (3) 访问根结点。 例1. 后序遍历 EFBGDCA● 遍历T: ● 遍历T1: ● 遍历T11: ● 左子树为空,遍历结束 ● 右子树为空,遍历结束。 ● 访问E; ● T11遍历结束。 ● 遍历T12:TCADGBEF/*后序遍历递归算法*/ PostorderTraverse(BiTree T) { if(T) { PostorderTraverse(T->lchild); PostorderTraverse(T->rchild); printf(“%c”,T->data); } }
  • 19. 表达式二叉树 表达式二叉树T = (第一操作数) 运算符 (第二操作数) 其中:第一操作数----T的左子树 第二操作数----T的右子树 运算符----表达式最后执行的算符 左子树是表达式二叉树 右子树是表达式二叉树运算符第一 操作数第二 操作数表达式二叉树 的一般形式左子树右子树-+CABA+B-C+A*BCA+B*C例表达式二叉树
  • 20. 例 表达式: A + B * C - D /(E - F) -+/A*D-BCEF▲ 前序遍历:- + A * B C / D - E F 前缀表示,前缀表达式,波兰式 ▲ 中序遍历: A + B * C - D /( E - F ) 中缀表示,中缀表达式 ▲ 后序遍历: A B C * + D E F - / - 后缀表示,后缀表达式,逆波兰式表达式二叉树
  • 21. 课 堂 练 习 画出表达式二叉树 A + B * (C – D)/(E -F)- G
  • 22. 课 堂 练 习 画出表达式二叉树 A + B * (C - D )/(E - F)- G+*/B--CDEF表达式二叉树A-G
  • 23. 6.3.5 二叉排序树(二叉查找树) 1.定义: 如果二叉树的任一结点大于其非空左子树的所有结点, 而小于等于其非空右子树的所有结点,则这棵二叉树 称为二叉排序树(Binary Sort Tree)。 2.特点:对一棵二叉排序树进行中序遍历,所得的结点序列一 定是递增有序的8514103585401080353LDR:5,8,10,14,35LDR:3,5,8,8,10,35,40,808
  • 24. 判断:下列二叉树是否为二叉排序树?30111815196410556026803010281522T1T230T3
  • 25. 3. 生成二叉排序树 设输入序列为:30,11,18,4,55,19,15,70,58303011183011184193011301118419301118455193011184551570193011184551570583011184555515
  • 26. 赫夫曼(Huffman哈夫曼)树及其应用 1.路径长度----路径上分枝的数目(连线的数目) 2.树T的路径长度----从树T的根到其余每个结点的路径长度之和, 记作 PL(T)T1T2T3PL(T1)=1+1+2+2+2=8 PL(T2)=1+2+3+4+5=15 PL(T1)=1+1+2+3+3=10
  • 27. 3.树T的带权路径长度----每个叶子的权与根到该叶子的路径 长度的乘积之和,记作 WPL(T) WPL(T) = ∑ wklk 其中: n --- 树T的叶子数目 wk--- 叶子k的权 lk--- 树T的根到叶子k的路径长度T49226WPL(T) = 6*1+3*2+4*3+9*3 = 51 PL(T) = 1+1+2+2+3+3=123nk=1
  • 28. 4.最优二叉树/最佳二叉树(optimal binary tree)/赫夫曼树 在具有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
  • 29. 5.赫夫曼算法 例 给定权集合{4,5,3,6,10},构造赫夫曼树 1.按权值大小排序: 3,4,5,6,10 2.生成森林:536410T1 T2 T3 T4 T53.合并两棵权最小的二叉树,并排序,直到为一棵二叉树.5364107561134107341071756113410717561128
  • 30. 课 堂 练 习 给定权集合 { 10,1,2,8,4,5 } 1.构造赫夫曼树 2.计算树的路径长度 PL 3.计算树的带权路径长度 WPL
  • 31. 讨论:谁的商品布局合理?为什么? 烟酒食品化 妆 品服 装鞋 类文化用品艺 术 品家 具古 董古 董家 具艺 术 品文化用品鞋 类服 装化 妆 品烟酒食品布局 A布局 B一楼二楼八楼家 具古 董文化用品艺 术 品鞋 类服 装化 妆 品烟酒食品布局 C