资源描述
第五章第五章 树和二叉树树和二叉树5.1 5.1 树的概念树的概念 Tree=(K,R)K=ki|1in,n0,kiElemType 其中n为树中结点数，n=0为空树，n0则为非空树。对于一棵非空树 关系 R应满足下列条件：(1)有且仅有一个结点有且仅有一个结点没有前驱没有前驱，该，该 结点被称为树的结点被称为树的根根；(2)除树根结点外，其余每个结点有除树根结点外，其余每个结点有 且且仅有一个前驱结点仅有一个前驱结点；(3)包括树根结点在内的每个结点，包括树根结点在内的每个结点，可以有可以有任意多个任意多个(含含0个个)后继。后继。+*d/cf-ba*e数学数学加法加法减法减法乘法乘法王庭贵王庭贵两位加两位加一位加一位加王万胜王万胜王万利王万利树应用的例子树应用的例子 一棵目录结构树的例子一棵目录结构树的例子 ABCDEFGHIJMKLA(B(E,F(K,L),C(G),D(H,I,J(M)T1T3T2树根树根 二元组表示二元组表示:K=A,B,C,D,E,F,G,H,I R=,A(B(D,E(H,I),F),C(G)通常有通常有:集合图集合图 凹入表凹入表 广义表广义表 线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据最后一个数据 元素元素(无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)5.1.3 5.1.3 树的基本术语树的基本术语 1.1.结点结点:结点的度结点的度:树的度树的度:数据元素数据元素+指向指向子树的分支子树的分支分支的个数分支的个数树中所有结点度的树中所有结点度的 最大值最大值DHIJM2.2.叶子结点叶子结点:分支结点分支结点:度为零的结点度为零的结点度大于零度大于零的结点的结点3.3.结点结点:孩子孩子 双亲双亲兄弟兄弟 堂兄弟堂兄弟祖先祖先 子孙子孙ABCDEFGHIJMKL4.4.结点的结点的 层次层次:树的深度：树的深度：ABCDEFGHIJMKL设设根根结点结点的层次为的层次为1 1，第第L L 层结点层结点的子树根结的子树根结点层次为点层次为L+1L+1叶子结点所在的最大层次叶子结点所在的最大层次ABCACB 5.5.有序树和无序树有序树和无序树 若树中各结点的子树是按照一定若树中各结点的子树是按照一定 的次序从左向右安排的，则称之的次序从左向右安排的，则称之 为为有序树有序树，否则称之为否则称之为无序树无序树。任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=（root，F）root 称为称为根根结点结点,F 称为子树森林称为子树森林6.森林：森林：是是m m（m0m0）棵互不相交的棵互不相交的树的集合树的集合ArootBCDEFGHIJMKLF5.1.4 5.1.4 树的性质树的性质性质性质1 1 树中的结点数等于所有树中的结点数等于所有 结点的度数加结点的度数加1 1。除树根结点外，除树根结点外，每个结点有且每个结点有且 仅有一个前驱仅有一个前驱 结点，除树根结点，除树根 结点之外的结点之外的 结点数等于结点数等于 所有结点的所有结点的 分支数（即度数）分支数（即度数）ABCDEFGHIJMKL性质性质2 度为度为k的树中第的树中第i层上至多有层上至多有 ki-1个结点（个结点（i1）。）。用数学归纳法证明：用数学归纳法证明：i=1 k1-1=1;第第i-1层（层（i1）k(i-1)-1=ki-2 第第i层上的结点数至多为第层上的结点数至多为第i-1层上层上 结点数的结点数的k倍倍 即至多为即至多为ki-2*k=ki-1个个性质性质3 深度为深度为h的的k叉树至多有叉树至多有 个结点。个结点。性质性质4 具有具有n个结点的个结点的k叉树的最小叉树的最小 深度为深度为 logk(n(k-1)+1)设设:深度为深度为 h 符号符号 x x 表示向下取整，即取小于等于表示向下取整，即取小于等于 x x的最大整数，反之的最大整数，反之 x x 表示向上取整，表示向上取整，即取大于等于即取大于等于x x的最小整数的最小整数 可变换为可变换为 k kh h-1-1 n(k-1)+1n(k-1)+1k kh h h-1h-1loglogk k(n(k-1)+1)h(n(k-1)+1)hloglogk k(n(k-1)+1)(n(k-1)+1)h h loglogk k(n(k-1)+1)(n(k-1)+1)+1+1 h h只能是整数，所以只能是整数，所以 h=h=loglogk k(n(k-1)+1)(n(k-1)+1)5.2 5.2 二叉树二叉树二叉树的递归定义为：二叉树或者是二叉树的递归定义为：二叉树或者是一棵一棵空树空树，或者是一棵由一个，或者是一棵由一个根结点根结点和两棵互不相交的分别称作根的和两棵互不相交的分别称作根的左子左子树树和和右子树右子树所组成的非空树，左子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。和右子树又同样都是一棵二叉树。根结点根结点左子树左子树右子树右子树ABCDEFGHKBCD二叉树的五种基本形态：二叉树的五种基本形态：空树空树N只含根结点只含根结点NL右子树为空右子树为空NR左子树为空左子树为空NRL左右子树均不为空树5.2.2 二叉树二叉树 的性质的性质vv性质性质1：在二叉树的第：在二叉树的第 i 层上层上 至多有至多有2i-1个个结点。结点。(i1)k=1 层时层时,2k-1=20=1 (根结点根结点)二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，则则 k=i 层层时时i 层的层的结点数结点数=2(i-1)-1 2=2i-1k=i-1 层时，层时，2i=2(i-1)-1 成成立立；性质性质2 度为度为k的树中第的树中第i层上至多有层上至多有 ki-1个结点（个结点（i1）。）。vv性质性质 2：深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点（个结点（k1）。）。证明：证明：基于上一条性质，深度为基于上一条性质，深度为 k k 的二叉树的二叉树上的结点数至多为上的结点数至多为 20+21+2k-1=2k-1 第第 i 层上层上2i-1 性质性质3 深度为深度为h的的k叉树至多有叉树至多有 个结点。个结点。vv性质性质3 vv 二叉树上终端结点数等于双分支二叉树上终端结点数等于双分支vv 结点数加结点数加 1。vv 若含有若含有n0 个叶子结点、个叶子结点、n2 个度为个度为 2vv 的结点，则必存在关系式：的结点，则必存在关系式：vv n0=n2+1 n=n0+n1+n2 b=n-1 b=n1+2n2 =n0+n1+n2-1 由此由此:n0=n2+1 n0=n2+1ABCDEFGHK结点总数结点总数 n分支总数分支总数 b两类两类特殊特殊的二叉树：的二叉树：满二叉树：满二叉树：深度为深度为k 且且 含有含有 2k-1个个 结点的结点的 二叉树。二叉树。12345678910 11 12 13 14 15完全二叉树完全二叉树：树中所含的树中所含的 n n 个结点和个结点和满二叉树中满二叉树中编号为编号为 1 1 至至 n n 的结点的结点一一对应。一一对应。abcdefghij 性质性质4 4：具有具有 n n 个结点的完全二叉树的个结点的完全二叉树的深度深度 为为 loglog2 2n n +1+1 或或 loglog2 2(n+1)(n+1)证明：证明：设完全二叉树的深度为设完全二叉树的深度为 k k 第二条性质第二条性质 2 2k-1k-1 n 2 n 2k k 即即 k-1 logk-1 log2 2 n kn k k k 只能是整数，只能是整数，因此，因此，k=k=loglog2 2n n +1+1 性质性质4 具有具有n个结点的个结点的k叉树的最小叉树的最小 深度为深度为 logk(n(k-1)+1)v性质性质 5 5：对完全二叉树中编号为对完全二叉树中编号为i i的结点的结点 (1 (1in,n1in,n1，n n为结点数为结点数)有：有：(1)(1)若若ii n/2n/2，即即2 2inin，则编号为则编号为i i的的 结点为结点为分支结点分支结点，否则为，否则为叶子结点叶子结点。(2)(2)若若n n为奇数，则树中每个分支结点都既为奇数，则树中每个分支结点都既 有左孩子，又有右孩子；若有左孩子，又有右孩子；若n n为偶数，为偶数，编号编号最大的分支结点最大的分支结点（编号为（编号为n/2n/2）只有左孩子，没有右孩子，其余分支只有左孩子，没有右孩子，其余分支 结点左、右孩子都有。结点左、右孩子都有。(4)(4)除树根结点外，若一个结点编号为除树根结点外，若一个结点编号为i i，则它双亲结点的编号为则它双亲结点的编号为 n/2n/2,即当即当i i为为 偶数时，它是双亲结点的左孩子，其双偶数时，它是双亲结点的左孩子，其双 亲结点编号为亲结点编号为i/2;i/2;当当i i为奇数时，它是为奇数时，它是 双亲结点的右孩子双亲结点的右孩子，其双亲结点编号为其双亲结点编号为 (i-1)/2i-1)/2。(3)(3)若编号为若编号为i i的结点有左孩子，则左孩的结点有左孩子，则左孩 子结点的编号为子结点的编号为2 2i i；若编号为若编号为i i的结的结 点有右孩子，则右孩子结点的编号为点有右孩子，则右孩子结点的编号为 2 2i+1i+1，即遵循对一般二叉树的编号规即遵循对一般二叉树的编号规 则。则。设设:i 结点所在为结点所在为h 层层 i=(2h-1-1)+1=2h-1j 结点所在结点所在为为h+1 层层j=(2h-1)+1=2h 结论结论:j=2i12345678910 11 12ij5.2.3 5.2.3 二叉树二叉树的抽象数据类型的抽象数据类型 基本操作基本操作:void InitBTree(BTreeType&BT)；void CreateBTree (BTreeType&BT,char*a);bool BTreeEmpty(BTreeType&BT);void TraverseBTree(BTreeType&BT);int BTreeDepth(BTreeType&BT);void PrintBTree(BTreeType&BT);void ClearBTree(BTreeType&BT);1 1顺序存储结构顺序存储结构#define MAX_TREE_SIZE 100 /二叉树的最大结点数typedef ElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点 SqBiTree bt;5.2.4 5.2.4 二叉树的存储结构二叉树的存储结构 例如例如:1ABCDEF251437 A B D C E F 0 1 2 3 4 5 6 7 8 9 10 1112 1314 2 2链接存储结构链接存储结构1.二叉链表二叉链表2带双亲链表带双亲链表E ADBCF root left data right结点结构结点结构:1.1.二叉链表二叉链表 struct BTreeNode ElemType data;BTreeNode *left;BTreeNode *right;类型描述如下类型描述如下:left data right结点结构结点结构:AE D B C F root 2三叉链表三叉链表parent left data right结点结构结点结构:5.3 5.3 二叉树二叉树 的遍历的遍历 顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树二叉树 中的结点，使得每个结点中的结点，使得每个结点均被访均被访 问一次，问一次，而且而且仅被访问一次。仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广的含义可以很广 如：输出结点的信息等。如：输出结点的信息等。对对“二二叉叉树树”而而言言，可可以以有有三三条搜索路径：条搜索路径：v1 1先上后下先上后下的按层次遍历；的按层次遍历；v2 2先左先左（子树）（子树）后右后右（子树）（子树）v 的遍历；的遍历；v3 3先右先右（子树）（子树）后左后左（子树）（子树）v 的遍历。的遍历。二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法（根）序的遍历算法中中（根）序的遍历算法（根）序的遍历算法后后（根）序的遍历算法（根）序的遍历算法 若二叉树为空树，则空操作；若二叉树为空树，则空操作；否则否则（1 1）访问根结点；）访问根结点；（2 2）先序遍历左子树；）先序遍历左子树；（3 3）先序遍历右子树。）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：DLRD L RABCDEFABCDEF先序遍历先序遍历 D L R先序遍历序列先序遍历序列:A B C D E FABDCEHGFK先序遍历先序遍历序列序列:A B D C E H G F K 若二叉树为空树，则空操作；若二叉树为空树，则空操作；否则否则（1 1）中序遍历左子树；）中序遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中序遍历右子树。）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：DLRL D RABCDEFABCDEF中序遍历中序遍历 L D R中序遍历序列中序遍历序列:B C A D F EABDCEHGFK中序遍历中序遍历序列序列:B C D A E F G K HFKGHEC DBAB C D A E F G K H 若二叉树为空树，则空操作；若二叉树为空树，则空操作；否则否则（1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树。）后序遍历右子树。（3 3）访问根结点；）访问根结点；后（根）序的遍历算法：后（根）序的遍历算法：DLRL R DABCDEFABCDEF后序遍历后序遍历 L R D后序遍历序列后序遍历序列:C B F E D AABCGFHEID后序遍历序列后序遍历序列:G D H E B I F C AG D H E B I F C AABCGFHEID层次遍历序列层次遍历序列:A,B,C,D,E,F,G,H,IA,B,C,D,E,F,G,H,I 仅知二叉树的先序序列仅知二叉树的先序序列“abcdefg”不不 能唯一确定一棵二叉树，能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二叉树的中序序列如果同时已知二叉树的中序序列 “cbdaegf”，则会如何？则会如何？先序序列先序序列中序序列中序序列左子树左子树左子树左子树右子树右子树右子树右子树根根根根a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列先序序列中序序列中序序列三、算法的递归描述三、算法的递归描述 1.前序遍历算法前序遍历算法 void Preorder(BTreeNode*BT)if(BT!=NULL)coutdataleft);/遍历左子树遍历左子树 Preorder(BT-right);/遍历右子树遍历右子树 2.2.中序遍历算法中序遍历算法 void Inorder(BTreeNode*BT)if(BT!=NULL)Inorder(BT-left);/遍遍历左子左子树 coutdataright);/遍遍历右子右子树 3.3.后序遍历算法后序遍历算法void Postorder(BTreeNode*BT)if(BT!=NULL)Postorder(BT-left);/遍历左子树遍历左子树 Postorder(BT-right);/遍历右子树遍历右子树 coutdatadata=ch;/生成根结点生成根结点 T-lchild=CreateBiTree();/构造左子树构造左子树 T-rchild=CreateBiTree();/构造右子树构造右子树 return T;A B C D A BCD上页算法执行过程举例如下：上页算法执行过程举例如下：ATBCD(1)(1)每棵树的每棵树的根根结点作为由子树构成结点作为由子树构成 的表的名字放在前面；的表的名字放在前面；(2)(2)每个结点的每个结点的左子树左子树和和右子树右子树用用 逗号分开，若只有右子树没有逗号分开，若只有右子树没有 左子树，逗号不能省略；左子树，逗号不能省略；(3)(3)在整个表的结尾加上一个特殊在整个表的结尾加上一个特殊 符号符号(字符字符)作为作为结束标志结束标志。采用采用广义表表示的输入法广义表表示的输入法A(B(C),D(E(F,G),H(,I)其广义表表示为：其广义表表示为：TABCDEH 算法的基本思路是：算法的基本思路是：若遇若遇字母字母，建立，建立新结点新结点，把该结点，把该结点 (非根结点非根结点)作为左孩子作为左孩子(k=1)k=1)或右或右 孩子孩子(k=2)k=2)链到链到双亲结点上；双亲结点上；若遇若遇左括号左括号，把前字母，把前字母进栈进栈,k k置置1 1;若遇若遇右括号右括号，退栈退栈；若遇若遇逗号逗号，k k置置2 2。while(ch!=)switch(ch)case(:top+;stop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=new BTreeNode;p-data=ch;p-left=p-right=NULL;if(BT=NULL)BT=p;/根结点根结点 else if(k=1)stop-left=p;else stop-right=p;/switch endA(B(C),D(E(F,G),H(,I)APBCDABK=1BTK=1K=2DK=16.6.清除二叉树清除二叉树 void DeleteBTree(BTreeNode*BT)if(BT!=NULL)DeleteBTree(BT-left);/删左子树删左子树 DeleteBTree(BT-right);/删右子树删右子树 delete BT;/删根结点删根结点 清除一棵二叉树的算法如下：清除一棵二叉树的算法如下：void ClearBTree(BTreeNode*&BT)DeleteBTree(BT);BT=NULL;5.5 5.5 树的存储树的存储 结构和运算结构和运算 5.5.1 树的存储结构树的存储结构 1.标准形式标准形式 2.广义标准形式广义标准形式3.二叉树形式二叉树形式ABCDEFG AB C E D F Groot AB C E D F G 3.二叉树形式二叉树形式二叉链表二叉链表(孩子孩子-兄弟）存储兄弟）存储 2.树的遍历树的遍历树的遍历可有三条搜索路径树的遍历可有三条搜索路径:先先根根(次序次序)遍历遍历:后后根根(次序次序)遍历遍历:按按层层次遍历次遍历:按层次遍历按层次遍历:先根遍历先根遍历:后根遍历后根遍历:若树不空，则先访问根结点，然后若树不空，则先访问根结点，然后依次先根遍历各棵子树。依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵若树不空，则先依次后根遍历各棵子树，然后访问根结点。子树，然后访问根结点。若树不空，则自上而下自左至右访若树不空，则自上而下自左至右访问树中每个结点。问树中每个结点。A B C DE F G H I J K 先根遍历：先根遍历：A B E F C D G H I J K 后根遍历：后根遍历：E F B C I J K H G D A 层次遍历：层次遍历：A B C D E F G H I J K 树的树的后根后根遍历算法如下：遍历算法如下：void PostRoot(GTreeNode*GT)/后根后根遍历一棵三叉树遍历一棵三叉树 if(GT!=NULL)for(int i=0;iti);/递归遍历每一个子树递归遍历每一个子树 coutdata;/访问根结点访问根结点 void LayerOrder(GTreeNode*GT)Queue q;InitQueue(q);GTreeNode*p;if(GT!=NULL)QInsert(q,GT);/树根树根指针进队指针进队 while(!QueueEmpty(q)/队列队列非空非空 p=QDelete(q);/出队出队 coutdata;for(int i=0;iti!=NULL)QInsert(q,p-ti);按按层层遍历三叉树遍历三叉树 A B C DE F G H I J KqGTAGHFEDCBABCDEFGHIJK 森林和二叉树的对应关系森林和二叉树的对应关系设森林设森林 F=(T1,T2,Tn);T1=(root，t11,t12,t1m);二叉树二叉树 B=(LBT,Node(root),RBT);由森林转换成二叉树规则为由森林转换成二叉树规则为:若若 F=，则则 B=；否则，否则，由由 ROOT(T1)对应得到对应得到 Node(root)；由由(t11,t12,t1m)对应得到对应得到 LBT；由由(T2,T3,Tn)对应得到对应得到 RBT。D G H I J KAFEBCAJIGKBECFDH由二叉树转换为森林由二叉树转换为森林的规则为：的规则为：若若 B=，则则 F=；否则，否则，由由 Node(root)对应得到对应得到 ROOT(T1)；由由LBT 对应得到对应得到(t11,t12,，t1m)；由由RBT 对应得到对应得到(T2,T3,Tn)。由此，树的各种操作均可对应二叉树由此，树的各种操作均可对应二叉树的操作来完成。的操作来完成。应当注意的是应当注意的是:和树对应的二叉树，其左、右子树和树对应的二叉树，其左、右子树的概念已改变为：的概念已改变为：左是孩子，右是兄弟。左是孩子，右是兄弟。ABCDEFG AB C E D F Groot3.二叉树形式二叉树形式二叉链表二叉链表(孩子孩子-兄弟）存储兄弟）存储 孩子孩子-兄弟法统计树中叶子结点兄弟法统计树中叶子结点 void count(BTreeNode*T，int&n)if(BT!=NULL)if(T-left=NULL)n+;/访问根结点访问根结点 count(T-left);/遍历左子树遍历左子树 count(T-right);/遍历右子树遍历右子树
展开阅读全文