数据结构--严蔚敏-树

《数据结构--严蔚敏-树》由会员分享，可在线阅读，更多相关《数据结构--严蔚敏-树（104页珍藏版）》请在金锄头文库上搜索。

1、数据结构主讲教师：祝建华第6章 树和二叉树1华中科技大学计算机学院线性结构： 线性表,栈,队列串,数组,广义表非线性结构： 树和二叉树图，网2华中科技大学计算机学院6.1树的定义6.1.1 定义和术语1.树（tree):树是n(n0)个结点的有限集T,当n=0时，T为空树；当n0时,(1)有且仅有一个称为T的根的结点,(2)当n1时,余下的结点分为m(m0)个互不相交的有 限集T1,T2,.,Tm ,每个Ti(1im)也是一棵树,且称为 根的子树。3华中科技大学计算机学院A T1例2. 四个结点的树 TA,B,C,DT1=BT2=CT3=DBCADT2例1. 一个结点的树 TA4华中科技大学计

2、算机学院JCFHIGBAEMKPLODN树TCFBEDT1HGT2例3 有16个结点的树T=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,PJIMKPLONT3T1=B,C,D,E,FT11=C,D,ET111=D T112=E T12=F T2=G,HT21=H T3=I,J,K,L,M,N,O,PT31=J,K,L,M,NT32=OT33=PT312=L .T311=K5华中科技大学计算机学院BAFDHECG4度树2.结点的度(degree):结点的子树数目 3.树的度:树中各结点的度的最大值 4.n度树: 度为n的树 5.叶子(终端结点): 度为0的结点 6.分枝结点(非终

3、端结点,非叶子):度不为0的结点 7.双亲(父母,parent)和孩子(儿子,child) : 若结点C是结点P的子树的根,称P是C的双 亲，C是P的孩子。6华中科技大学计算机学院BAFDHECG4度树1层2层3层8.结点的层(level):规定树T的根的层为1，其余任一结点的 层等于其双亲的层加1。 9.树的深度(depth,高度):树中各结点的层的最大值。 10.兄弟(sibling):同一双亲的结点之间互为兄弟。 11.堂兄弟:同一层号的结点互为堂兄弟。7华中科技大学计算机学院BADFECG无序树T1BADFC无序树T1有序树T1有序树T2EGBADFECGBADFCEG12.祖先: 从

4、树的根到某结点所经分枝上的所有结点为该 结点的祖先。 13.子孙: 一个结点的所有子树的结点为该结点的子孙。 14.有序树:若任一结点的各棵子树，规定从左至右是有次 序的,即不能互换位置,则称该树为有序树。 15.无序树: 若任一结点的各棵子树，规定从左至右是无 次序的,即能互换位置,则称该树为无序树。 8华中科技大学计算机学院DAFHCEBGT1IMJLKNT2T3森林F=T1,T2,T316.森林:m(m0)棵互不相交的树的集合。9华中科技大学计算机学院树TFAGEBCD树T的广义表形式=(A(B(C,D),E,F(G,)广义表A=(B,E,F)=(C,D),( ),(G)=( ),( )

5、）,( ),( )广义表A的树形表示ABCDEFG6.1.2.树的其它表示形式 1.广义表树T的广义表=(T的根(T1,T2,.,Tm)其中Ti是T的子树，也是广义表。 (1im)10华中科技大学计算机学院2.嵌套集合：EDCBGFA3.凹入表/书目表 树TFAGEBCDA -B -C -D -E -F -G - 凹入表11华中科技大学计算机学院6.1.3 树的基本操作1.置T为空树：T= 2.销毁树T3.生成树T4.遍历树T：按某种规则(次序)访问树T的每一个结点一次且一次的过程。5.求树T的深度6.求树T的度7.插入一个结点8.删除一个结点9.求结点的层号10.求结点的度11.求树T的叶子

6、/非叶子12.12华中科技大学计算机学院6.2 二叉树(binary tree)6.2.1 定义和术语1. 二叉树的递归定义二叉树是有限个结点的集合，它或者为空集；或者是 由一个根结点和两棵互不相交的，且分别称为根的左子树 和右子树的二叉树所组成。若二叉树为空集，则为空二叉树。13华中科技大学计算机学院二叉树T4CAGBEFHAAB二叉树T2二叉树T12.二叉树的5种基本形态: T1 T2 T3 T4 T5ABC二叉树T3例:14华中科技大学计算机学院T4CADBDABCABT3T2C(2)树ABCT2 2度树ABCD T5T3 1度树T4 2度树AT1AT10度树CABCAB3.二叉树与2度

7、树的区别 (1)二叉树15华中科技大学计算机学院T1ABCT2T3T4T5ABCABCABCABC5.三个结点不同形态的树(2种) ABC T1ABCT24.三个结点不同形态的二叉树(5种)16华中科技大学计算机学院6.二叉树的基本操作1.置T为空二叉树：T= 2.销毁二叉树T3.生成二叉树T：生成哈夫曼树、二叉排序树、平衡二叉树、堆4.遍历二叉树T：按某种规则访问T的每一个结点一次且仅一次的过程。5.二叉树 树6.二叉树 平衡二叉树7.求结点的层号8.求结点的度9.求二叉树T的深度10.插入一个结点11.删除一个结点12.求二叉树T的叶子/非叶子 .17华中科技大学计算机学院二叉树CAGBE

8、FH20 =1个23 =8个22 =4个21 =2个20(1- 2k) 1- 22.深度为k的二叉树最多有2k-1个结点(性质2）20+21+ .+ 2k-1= = 2k-16.2.2 二叉树的性质和特殊二叉树1.二叉树的第i(i1)层最多有2i-1个结点(性质1)18华中科技大学计算机学院ABCABCCAGBEFHT1T2T3T1: n0=2, n2=1, 2=1+1 T2: n0=1, n2=0 1=0+1 T3: n0=3, n2=2 3=2+1 3.叶子的数目=度为2的结点数目+1（性质3）n0 = n2 + 119华中科技大学计算机学院T1T2T3T4 (1) n个结点的满二叉树的深

9、度=log2(n+1)（性质4）设深度为k 2k - 1n2kn + 1 k=log2(n+1) 4.满二叉树（full binary tree)-深度为k且有2k-1个结点的二叉树。20华中科技大学计算机学院123124589 10 1136712 13 14 1512345671设满二叉树有n个结点,编号为1,2,.,n 左小孩为偶数，右小孩为奇数； 结点i的左小孩是2i， 2in结点i的右小孩是2i+1, 2i+1n结点i的双亲是i/2； 2in 结点i的层号= log2 i + 1 = log2(i+1) 1inT1T2T3T4(2)顺序编号的满二叉树（性质5）21华中科技大学计算机学

10、院12112345T1T2T3T4T5ABEDCF12345675.完全二叉树（full binary tree):深度为k的有n个结点的二叉树,当且仅当每一个结点 都与同深度的满二叉树中编号从1至n的结点一一对应,称 之为完全二叉树（其它教材称为“顺序二叉树”）。例. 完全二叉树:22华中科技大学计算机学院12123451235641234567例 满二叉树:T2T1T312354T4123T1T2n(n0)个结点的完全二叉树的深度=log2 n+1 = log2(n+1)例 非完全二叉树:23华中科技大学计算机学院ACDBEFT1/ACDBEF123465t160 1 2 3 4 5 6父

11、子关系 元素(结点)ti的双亲是ti/2, 2in 元素(结点)ti的左小孩是t2*i, 2in 元素(结点)ti的右小孩是t2*i+1, 2i+1nT1的顺序结构6.2.3 二叉树的存储结构1.顺序结构(1) n个结点的完全二叉树，使用一维数组: 例. ElemType treen+1； char t7；24华中科技大学计算机学院ABECHGT2A B E CGD EH1234613t1131 2 3 4 5 6 7 8 9 10 11 12 13父子关系 若ti存在,ti的双亲是ti/2； 2in 若t2*i存在,ti的左小孩是t2*i； 2in 若t2*i+1存在,ti的右小孩是t2*i

12、+1。 2i+1nE9 D8 T2的顺序结构(2) 一般二叉树25华中科技大学计算机学院ABT3ABCD13t1151 2 3 4 5 6 7 8 9 10 11 12 13 14 15深度为k的二叉树，最多需长度为2k-1的一维数组。若是右单枝树，空间利用率为:k = 2k - 1k=4, =4/15 ；k=10, =10/10230.0098 CD715T3的顺序结构(3)右单枝树26华中科技大学计算机学院pABCDEFGroot二叉树T1 T1的二叉链表CAFBDEG2.链式存储结构 (1)二叉链表struct BiTNode /结点类型 struct BiTNode * lchild；

13、/左孩子指针 ElemType data； /抽象数据元素类型struct BiTNode * rchild；/右孩子指针 *root,*p；27华中科技大学计算机学院CAFBDEGABCDEFGroot二叉树T2 T2的三叉链表(2)三叉链表struct BiTNode struct BiTNode *parent,*lchild,*rchild ； ElemType data； *root,*p；28华中科技大学计算机学院二叉树/ / / 2 A 34 B 50 C 60 D 00 E 07 F 00 G 001234567lchild data rchild一维数组t07rootCAFB

14、DEG(3)静态链表 struct bnode2 ElemType data；int lchild,rchild；tn+1；29华中科技大学计算机学院6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树按某种规则访问二叉树的每一个结点一次且仅一次的过程 。 设: D-访问根结点,输出根结点；L-递归遍历左二叉树；R-递归遍历右二叉树。遍历规则(方案):DLR-前序遍历(先根,preorder)LDR-中序遍历(中根,inorder)LRD-后序遍历(后根,postorder)DRL-逆前序遍历RDL-逆中序遍历RLD-逆后序遍历30华中科技大学计算机学院CADG TBEFABEFCDGABEG

15、 FC D前序遍历前序遍历二叉树递归定义：若二叉树为空，则遍历结束；否则，执行下列步骤：(1) 访问根结点；(2) 遍历根的左子树；(3) 遍历根的右子树。31华中科技大学计算机学院前序遍历递归算法过程:T1CADG TBEFBEFEFCDGDGGTTTTTTT 左左左左 右右右右访问A访问B访问C访问E访问F访问D访问C32华中科技大学计算机学院先序遍历递归算法:typedef struct BiTNode *BiTree; /结点指针类型 void PreOrderTraverse(BiTree T) /T是指向二叉链表根结点的指针 if (!T) return;else printf(“%c”,T-data); /访问根指针PreOrderTraverse(T-lchild)； /递归访问左子树PreOrderTraverse(T-rchild)； /递归访问右子树return；33华中科技大学计算机学院先序遍历递归算法typedef stru