《树与二叉树(4h)【基础教学】》由会员分享，可在线阅读，更多相关《树与二叉树(4h)【基础教学】（67页珍藏版）》请在金锄头文库上搜索。
1、2.4.1 树的基本概念树的基本概念2.4.2 二叉树及其基本性质二叉树及其基本性质2.4.3 二叉树的存储结构二叉树的存储结构2.4.4 二叉树的遍历二叉树的遍历2.4.5 二叉树的应用二叉树的应用2.4 2.4 树与二叉树树与二叉树1内容提要1.1.树的定义树的定义2.2.树的基本概念树的基本概念 结点、结点度、根、支、叶结点 子结点、父结点、兄弟结点 树的度、路径、长度、深度 森林、有序、无序2内容提要3.3.二叉树二叉树 二叉树的定义二叉树的定义 二叉树的性质（每层结点个数、总结点数）二叉树的性质（每层结点个数、总结点数） 二二叉叉树树的的存存储储结结构构: :顺顺序序存存储储、记记录
2、录数数组组结结构构( (结结点点、左左子子、右子右子) )、链式存储结构（二叉链表三叉链表）、链式存储结构（二叉链表三叉链表）4.4.特殊二叉树特殊二叉树 满二叉树（性质）、完全二叉树（性质）、平衡二叉树、满二叉树（性质）、完全二叉树（性质）、平衡二叉树、 二叉排序树）二叉排序树）5.5.二叉树的遍历操作二叉树的遍历操作（前序、中序、后序）（前序、中序、后序） 6.6.树的存储结构树的存储结构: : 数组实现方法数组实现方法（双亲表示法）、链表实现方式（孩子表（双亲表示法）、链表实现方式（孩子表 示法）、二叉链表实现方式（孩子兄弟表示法）示法）、二叉链表实现方式（孩子兄弟表示法）7.7.树、森
3、林与二叉树的转换树、森林与二叉树的转换32.4.1 树的基本概念南京理工大学南京理工大学信息学院信息学院经管院经管院 计算机学院计算机学院自动化学院自动化学院210121022103张三张三李四李四王五王五理学院理学院树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：n人类社会的族谱、家谱、行政 区域划分管理；n各种社会组织机构；n在计算机领域中，用树表示源程序的语法结构；n在OS中，文件系统、目录等组织结构也是用树来表示的。456线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数
4、最后一个数据元素据元素( (无后继无后继) )多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )7一、树的定义1（逻辑结构）n树是一种数据结构：Tree=（D，R）其中：D 是具有相同特性的n个数据元素的集合；R 是D上逻辑关系的集合，且满足：n在D中存在唯一的称为根的数据元素，没有前件；nD中其余数据元素都有且只有一个前件；nD中所有元素，或有若干个互不相同的后件（子树），或无后件（叶结点）； 则称Tree为树。8树的定义2（递归结构）n树是一个
5、或多个结点组成的有限集合T，有一个特定结点称为根，其余结点分为m（m0）个互不相交的集合T1，T2，,Tm。每个集合又是一棵树，被称为这个根的子树。n树是一种递归结构，可以包含一个结点，该结点包含不相交的树的指针（即子树）。9二、树的表示形式1. 1. 一般形式一般形式2. 2. 嵌套形式嵌套形式3. 3. 凹入形式凹入形式4. 4. 广义表形式广义表形式101. 一般形式 A(a)(a)只有根结点的树只有根结点的树ABCDEFKLGHIJM(b)(b)一般的树一般的树112. 嵌套形式 ACGBFEKLMHDJI12树的表示(凹入形式)A B E KLCDFGHIJM13树的表示(广义表形式
6、)( A ( B ( E (K,L),F),C(G),D( H (M),I,J ) 第一层第一层第二层第二层第三层第三层第四层第四层14二、基本术语n结点：包括一个数据元素及若干个指向其它子树 的分支；例如，A，B，C，D等。n叶结点：无后件结点为叶结点；如K，L，M。n根结点：无前件的结点为根；例如，A结点。n子结点：某结点后件为该结点的子结点；例如， 结点A的子结点为B，C，D。n父结点：某结点的前件称为该结点的父结点；例 如子结点C，B，D的父结点为A。15基本术语续n兄弟结点：同一父亲的孩子之间互为兄弟结点 （Sibling）；H，I，J互为兄弟。n路径：结点的序列n1，n2，,nk(
7、K1)是一条路径。n长度：长度等于路径中结点数-1。n结点度：结点拥有的子树数数目；例如，A的度为3。n树的度：树中结点的最大度数；上述树的度为3。n子树：以某结点的一个子结点为根构成的树称为该 结点的一棵子树。 16基本术语续n高度：从一结点到叶结点的最长路径为该结点的高度；例如，结点A到M的高度为4。n深度：从根结点到某结点的路径为该结点的深度； M的深度为4。n树的深度：树的最大层次称为树的深度。 n森林：0棵或多棵互不相交的树的集合。对树中每个 结点而言，其子树的集合即为森林。n有序：如果将树中结点的各子树看成从左至右是有顺序的（即不能互换），则称该树为有序树。否则，称为无序树。17例
8、：用树结构来表示算术表达式 n用树来表示算术表达式的原则如下： n表达式中的每一个运算符在树中对应一个结点，称为运算符结点。n运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。n运算对象中的单变量均为叶子结点。例如：a*（bcd）e*h-g*f（s，t，xy） 182.4.2 二叉树及其基本性质n定义一：二叉树是另一种树形结构： Binary_Tree =( D,R) 其中：D 是具有相同性质的数据元素的集合； R 是在D上某个两元关系的集合，且满足：nD中存在唯一称为根的数据元素，没有前件；中存在唯一称为根的数据元素，没有前件；nD中其余元素都有且仅有一个前件；中其
9、余元素都有且仅有一个前件；n每个结点至多只有两个子树每个结点至多只有两个子树；nD中元素，或有两个互不相交后件，或无后件；中元素，或有两个互不相交后件，或无后件；n左、右子树分别又是一棵二叉树左、右子树分别又是一棵二叉树。一、定义19定义二 n个结点的集合（个结点的集合（n 0） T 的度的度 2 所有子树都有左、右之分所有子树都有左、右之分 （次序不能任意颠到）（次序不能任意颠到）v 二叉树不一定是树二叉树不一定是树v 二叉树可以为空；而树则不能为空；二叉树可以为空；而树则不能为空；v 二叉树的结点最多只有两个直接后件二叉树的结点最多只有两个直接后件v 二叉树的结点的子树分左子树和右子树，而
10、树则无此区分。二叉树的结点的子树分左子树和右子树，而树则无此区分。v 二叉树是有序树二叉树是有序树 二叉树的度二叉树的度=21,则结点i父结点的编号为i/2(取整)。28（2）完全二叉树特点: 叶结点只可能出现在层次最大的两层上.n深度为k的二叉树T，每层结点数目若满足：n第i层(1 i k-1)上的结点个数均为2i-1i-1;n第k层从右边连续缺若干个结点(即只能从右至左不间断缺少); 称这样的树为完全二叉树。OOOOOO（a） 完全二叉树OOOOO（b） 非完全二叉树29完全二叉树的性质n设完全二叉树的结点总数为n，深度为k，某结点编号为i（1 i n ），则有：n若若i1,i1,则结点则
11、结点i i的双亲结点的编号为的双亲结点的编号为i/2;i/2;n若若2* 2* i i n,n,则则结结点点i i 的的左左子子结结点点的的编编号号为为2* 2* i,i,否否则则, ,结结点点i i为叶结点为叶结点; ;n若若2* i +12* i +1 n, n,则结点则结点i i 的右子结点的编号为的右子结点的编号为2*i+1,2*i+1,否则否则, ,结点结点i i为叶结点为叶结点. .n同理,完全二叉树也可以采用一维树组作为存储结构,且方法完全同满二叉树,只不过n 2k -1 罢了.ni i 父结点：父结点：int(I/2)int(I/2)，n左子结点：2*i n，右子结点：2*i+
12、1 n30（3）二叉排序树定义一n二叉排序树n或者是空二叉树；或者是空二叉树；n或者是：或者是：n左子树上所有结点的值均小于根结点的值；左子树上所有结点的值均小于根结点的值；n右子树上所有结点的值均大于等于根结点的值；右子树上所有结点的值均大于等于根结点的值；n左、右子树本身又是一棵二叉排序树。左、右子树本身又是一棵二叉排序树。 n最后一句话可否去掉？n区别与有序树31二叉排序树定义（二）nX是二叉排序树T中的一个结点；n所有的左后裔小于X；n所有的右后裔大于等于X；nT可以为空树；nT称为二叉排序树。104712141814（a）二叉排序树14141841012137（b）非二叉排序树322
13、.4.3 二叉树的存储结构 一、顺序存储（一维数组）n用数组存放 存储描述为： #define MAXSIZE 100； typedef TElemType SBTreeMAXSIZE； SBTree bt；n查找不便。a1 a2 a3 a4 . an33满二叉树存储举例1432476 1 2 3 4 4 6 71 2 3 4 4 6 7第第i i个结点就存放在第个结点就存放在第i i个位置上；个位置上；第第i i个结点（个结点（i1)i1)的父结点就存放在第的父结点就存放在第 i/2i/2个位置个位置; ;第第i i个结点（个结点（i i 2 2k-1k-1 - 1)- 1)的左子结点就存放
14、在第的左子结点就存放在第2*i2*i的个位置的个位置; ;右子存放在第右子存放在第2*i+12*i+1位置位置. .34二、记录数组结构n存储结构描述: #define MAXSIZE 100; typedef struct SBNode TElemType data ; int Lchild,Rchild; SBNode; typedef structSBNode nodesMAXSIZE; SBTree;35举例1 2 62 3 43 0 44 0 04 0 06 0 0结点结点 左子左子 右子右子126344特点特点:找子方便找子方便,找父找父结点不便结点不便.36三、二叉链表存储结构d
15、ata leftprightp左指针左指针 数据数据 右指针右指针ABCDEFGABDCEFG特点特点: 找子易找子易, 找父难找父难.37四、三叉链表存储结构左指针左指针 数据数据 父结点父结点 右指针右指针parent datarightpABCDEFGleftp特点特点: 找子、找父都易找子、找父都易。CABDEGF382.4.4 二叉树的遍历n遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。n遍历的方法很多，常用的有：n前序法（前序法（PreOrder）n中序法（中序法（InOrder）n后序法（后序法（PostO
16、rder）39一、前序法（PreOrder）n方法描述：n从根结点从根结点a开始访问，开始访问，n接着访问左子结点接着访问左子结点b，n最后访问右子结点最后访问右子结点c。n即：根根左子左子右子右子abcA 访问根结点访问根结点B 先序遍历左子树先序遍历左子树C 先序遍历右子树先序遍历右子树40二、中序法（InOrder）n方法描述：n从左子结点从左子结点b开始访问，开始访问，n接着访问根结点接着访问根结点a，n最后访问右子结点最后访问右子结点c。n即：根根左子左子右子右子abcA 中序遍历左子树中序遍历左子树B 访问根结点访问根结点C 中序遍历右子树中序遍历右子树41三、后序法（PostOr
17、der）n方法描述：n从左子结点从左子结点b开始访问，开始访问，n接着访问右子结点接着访问右子结点c，n最后访问根结点最后访问根结点a。n即：根根左子左子右子右子abcA 后序遍历左子树后序遍历左子树B 后序遍历右子树后序遍历右子树C 访问根结点访问根结点42二叉树的遍历举例oooooooooABCDEFGHI前序遍历序列：前序遍历序列：中序遍历序列：中序遍历序列：后序遍历序列：后序遍历序列：A B D E G C F H ID B G E A C H F ID G E B H I F C A 43四、二叉树遍历算法 二叉链表描述 struct tnode intdata； struct tn
18、ode *lchild， *rchild ； ； typedef struct tnode TNODE;定义定义结点结点数据类型数据类型44二叉树遍历算法 1.递归、前序法程序n头指针为头指针为BT的二叉树的前序遍历。的二叉树的前序遍历。PROCEDURE PRETRAV(BT)IF(BT0) THENOUTPUT(V(BT);PRETRAV(L(BT);PRETRAV(R(BT)RETURN前序遍历二叉树的序列为：前序遍历二叉树的序列为： A B C D E FABCDEF45二叉树遍历算法 1.递归、前序法程序void preorder_t (TNODE *root) if ( root
19、!= NULL ) printf(“%d n”,root-data); if (root-lc!=NULL) preorder_t(root-lc); if (root-rc!=NULL) preorder_t(root-rc); 前序遍历二叉树的序列为：前序遍历二叉树的序列为： A B C D E FABCDEF46二叉树二叉树遍遍历算法历算法（递归、前序法程序验证）（递归、前序法程序验证）n打印打印A An取取A A . .左子左子(B)(B)n打印打印B Bn取取B B . .左子左子(C)(C)n打印打印C Cn取取C C . .左子左子( (空空) )n取取C C . .右子右子(
20、(空空) ) n取取B B . .右子右子(D)(D)n打印打印D Dn取取D D . .左子左子(E)(E)n打印打印E En取取E E . .左子左子( (空空) )n取取E E . .右子右子( (空空) )n取取D D . .右子右子(F)(F)n打印打印F Fn取取F F . .左子左子( (空空) )n取取F F . .右子右子( (空空) )n取取A A . .右子右子( (空空) )n结束结束A AB BC CD DE EF FABCDEF472.非递归算法-前序法n算法步骤算法步骤: :nstep1 step1 初始化初始化, ,置栈为空置栈为空(top=-1),(top=-
21、1), 工作变量工作变量p p指向指向root;root;nstep2 pstep2 p非空非空(p!=NULL)(p!=NULL) 或栈非空或栈非空(top!=-1)(top!=-1)循环循环; ;nstep3 pstep3 p非空循环非空循环; ; 访问访问p p( (打印打印p-data)p-data); ;nstep4 step4 当前元素进栈当前元素进栈,p,p取取p-lcp-lc( (进左子树进左子树) ); ; 执行执行step3step3；nstep4 pstep4 p为空，栈非空，则出栈，为空，栈非空，则出栈， p p取取p-rcp-rc（进右子树）（进右子树）, ,返回返回
22、step2.step2.48#define N mvoid preorder_t(TNODE * root) TNODE *p, *stackN; int top=-1; p=root; while (p!= NULL)|(top!= -1) while ( p!=NULL) printf(“%dn”,p-data);/访问节点访问节点 top +; stacktop=p; /进栈进栈 p=p-lc; /进左子树进左子树 if ( top !=-1) p=stacktop; top - - ; /出栈出栈 p=p-rc;/进右子树进右子树 ABCDEF49二叉树二叉树遍遍历算法历算法（非递归、
23、前序法（非递归、前序法程序验证）程序验证）n打印打印A AnA A进栈，取进栈，取A A . .左子左子( B )( B )n打印打印B BnB B进栈，取进栈，取B B . .左子左子( C )( C )n打印打印 C CnC C 进栈，进栈， 取取C C . .左子左子( ( 空空 ) )nC C 退栈，退栈， 取取C C . .右子右子( ( 空空 ) )nB B 退栈，退栈， 取取 B B . .右子右子( D )( D )n打印打印 D D nD D进栈，取进栈，取D D . .左子左子( E )( E )n打印打印E EnE E进栈，取进栈，取E E . .左子左子( ( 空空 )
24、 )nE E退栈，退栈， 取取E E . .右子右子( ( 空空) )nD D退退栈，取栈，取D D . .右子右子( F )( F )n打印打印F FnF F进栈，取进栈，取F F . .左子左子( ( 空空 ) )nF F退栈，退栈， 取取F F . .右子右子( ( 空空) )nA A退退栈，取栈，取A A . .右子右子( ( 空空 ) )n结束结束FEDCBAABCDEF50 2.5.5树的应用一、表达式树n在在计计算算机机中中对对表表达达式式进进行行分分析析和和计计算算是是一一项重要的任务；项重要的任务；n表达式可以用有序树表示；表达式可以用有序树表示；n树处理不方便，可以转化为二
25、叉树处理；树处理不方便，可以转化为二叉树处理；n转化原则：转化原则：n有序树有序树T的结点与二叉树的结点与二叉树BT的结点一一对应；的结点一一对应；n有有序序树树T中中某某个个结结点点N的的第第一一个个子子结结点点N1,在在二二叉树叉树BT中为对应结点中为对应结点N的左子结点；的左子结点；n其其他他子子结结点点，在在二二叉叉树树BT中中被被依依次次链链接接成成一一串串起始于起始于N1的右子结点。的右子结点。51表达式线性化n将表达式用有序树表示；n将表达式树转化为二叉树；n对对应的二叉树进行中序遍历，其遍历序列即为表达式的波兰表达式；n前序遍历为波兰表达式。52表达式处理规则表达式处理规则分析
26、：分析：每个叶结点为运算对象；每个叶结点为运算对象；每个非叶结点为运算符；每个非叶结点为运算符；每个子树对应一个子表达式。每个子树对应一个子表达式。见运算数入栈见运算数入栈见见运运算算符符，取取两两个个栈栈顶顶元元素素运运算算后后再再压压栈；栈；直到处理结束。直到处理结束。53表达式树应用举例（6）遇）遇-，a+b*（c-d） 和和e/f出栈，运算后再压栈出栈，运算后再压栈。（6）a+b*（c-d）- e/f（2） c - d b a（2）遇）遇-，c d 出栈，出栈， 运算后再压栈；运算后再压栈；（3） b*（c-d） a（3）遇）遇*，（，（c - d）和）和 b 出栈，出栈， 运算后再压
27、栈；运算后再压栈；（5）e/fa+b*（c-d）（5）遇）遇/，f e 出栈，出栈， 运算后再压栈；运算后再压栈；（1）（1） a b c d 入栈入栈dcbaa+b*（c-d）（4）（4）（4）遇）遇+，b*（c-d）和）和a出栈，出栈， 运算后再压栈运算后再压栈；a+b*（c-d）fe54二、Huffman(哈夫曼）树（1）Huffman树的定义（2）构造Huffman树（3）Huffman编码（4）Huffman编码的译码551. Huffman树的定义nHuffman树也称为最优树，是一类带权路径最短的二叉树。n树的带权路径长度定义为： WPL = wkLkk = 1n 其中：其中：
28、n 是树中叶结点的个数是树中叶结点的个数 wi 是第是第i个结点的权值个结点的权值 Li 是第是第i个结点的路径长度个结点的路径长度 56Huffman树举例n以下有三棵树：（a）abcd7424WPLa =7x2+4x2+2x2+4x2 = 34（b）acbd7424WPLb =7x3+4x3+2x1+4x2 = 43（c）abcd7424 WPLc = 7x1+4x2+2x3+4x3 = 33 l事实证明按哈夫曼树构造二叉树，可得到很好的特性，事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。应用于实际问题，可提高处理效率。57应用举例n由统计规律可知，考试成
29、绩的分布符合正态分布：-1 1 0 分数分数 059 60 69 70 79 80 89 90 100比例数比例数 0.06 0.14 0.40 0.30 0.10 l根据正态分布规律，在根据正态分布规律，在60 89分之间的同学占分之间的同学占84%，而不及格和优秀成绩的同学是少数。，而不及格和优秀成绩的同学是少数。58将百分制转换成五分制n判定树比较：a60?a70?a80?a90?不及格 及格及格 中等 良好良好 优秀优秀YYYYNNNN不及格不及格 中等中等(A)a80?a70?a90?a60? 优秀优秀 良好良好 中等中等 及格及格不及格不及格YYYNNNNYY(B)l若输入若输入1
30、 1万个数据，按万个数据，按A A的判定过程进行操作，约需比较的判定过程进行操作，约需比较3.23.2万万次，而按次，而按B B比较比较, ,则仅需则仅需2.22.2万次。万次。592. 构造Huffman树构造构造Huffman树算法步骤：树算法步骤：1）将）将n个带权值个带权值wi（in）的结点构成）的结点构成n棵二叉树的集合棵二叉树的集合T=T1，T2，Tn，每棵二叉树只有一个根结点。，每棵二叉树只有一个根结点。2）在）在T中选取两个权值最小的结点作为左右子树，构成中选取两个权值最小的结点作为左右子树，构成一个新的二叉树，其根结点的权值取左右子树权值之一个新的二叉树，其根结点的权值取左右
31、子树权值之和；和；3）在）在T中删除这两棵树，将新构成的树加入到中删除这两棵树，将新构成的树加入到T中；中；4）重复）重复2）、）、3）步的操作，直到）步的操作，直到T中只含一棵树为止，中只含一棵树为止，该树就是该树就是Huffman树。树。60构造Huffman树举例n以权值分别为7，4，2，4的结点a、b、c、d构造Huffman树。T= a b c d cdT3246bT3T26410bT26410cd2417aT2710T1617a7T1bT3T241017a7T1b410cd264（d）T= T1 （c）T= a T2 （b）T= a b T3 （a）T= a b c d 代入代入T
32、2代代入入T3代入代入T1613. Huffman编码n编码：用二进制数的不同组合来表示字符的方法。n前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。 a0b01cd011编码：编码：A（0） B（10） C（110） D（111）方法约定：方法约定：1）左分支为）左分支为02）右分支为）右分支为13）由叶到根路径上字符组）由叶到根路径上字符组成的二进制串就是该叶结点成的二进制串就是该叶结点的编码。的编码。nHuffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。62Huffman编码举例n
33、在某系统的通信联络中可能出现在某系统的通信联络中可能出现8种字符，其频率种字符，其频率分别为分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设权值分别为，设权值分别为5，29，7，8，14，23，3，11，n=8，其，其Huffman树为：树为：810000000111111537142911234258100Huffman编码为：编码为：A 5 0110B 29 10C 7 1110D 8 1111E 14 110F 23 00G 3 0111H 11 010634.Huffman编码存储结构n由于由于Huffman树中没有度为树中没有度为1的结点，则的
34、结点，则n个叶结点个叶结点的的Huffman树共有树共有2n-1个结点。例如，个结点。例如，4个叶结点的个叶结点的Huffman树，共有树，共有7个结点。因此可以用长度为个结点。因此可以用长度为2n-1的一维数组存放。的一维数组存放。n求求Huffman编码：编码： 从根到叶的编码从根到叶的编码。因此要知道每。因此要知道每个结点的父结点。个结点的父结点。000000011111115378142911234258100Huffman编码为：编码为：A 5 0110B 29 10C 7 1110D 8 1111E 14 110F 23 00G 3 0111H 11 010645.Huffman编
35、码的译码n从从Huffman编码树上不难看出，编码树上不难看出，代码全部在叶结点上代码全部在叶结点上，根据根据Huffman编码，就能求出相应的字符。该过程称编码，就能求出相应的字符。该过程称为为“译码译码”。n译码是根据译码是根据从根到叶从根到叶的的Huffman编码求相应的字符。编码求相应的字符。因此要知道每个结点的左右子结点。因此要知道每个结点的左右子结点。n例如，根据例如，根据“1111”，就能求出对应的字符是，就能求出对应的字符是“8”。53000000011111117814291123425810065作业n在某系统的通信联络中可能出现在某系统的通信联络中可能出现10种字种字符（符（A-I），其频率分别为），其频率分别为0.04、0.15、0.07、0.08、0.14、0.21、0.02、0.12、0.16、0.09。试建立其。试建立其Huffman树并给树并给出其出其Huffman编码。编码。66总结1.1.树的定义树的定义2.2.树的基本概念树的基本概念 3.3.二叉树二叉树4.4.特殊二叉树特殊二叉树5.5.二叉树的遍历操作二叉树的遍历操作67
