《树的概念和定义学习教案.pptx》由会员分享，可在线阅读，更多相关《树的概念和定义学习教案.pptx（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1树的概念树的概念(ginin)和定义和定义第一页，共43页。树是n（n0）个结点的有限集合 T。当n=0时，称为空树；当 n0时，该集合满足如下条件：(1)其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。(2)其余(qy)n-1 个结点可以划分成 m（m0）个互不相交的有限集 T1，T2，T3，Tm，其中Ti又是一棵树，称为根 root的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。第1页/共43页第二页，共43页。图6.1 树的图示方法(fngf)第2页/共43页第三页，共43页。结点(ji din)：包含一个数据元素及若干指向
2、其它结点(ji din)的分支信息。结点(ji din)的度：一个结点(ji din)的子树个数称为此结点(ji din)的度。叶结点(ji din)：度为0的结点(ji din)，即无后继的结点(ji din)，也称为终端结点(ji din)。分支结点(ji din)：度不为0的结点(ji din)，也称为非终端结点(ji din)。孩子结点(ji din)：一个结点(ji din)的直接后继称为该结点(ji din)的孩子结点(ji din)。双亲结点(ji din)：一个结点(ji din)的直接前驱称为该结点(ji din)的双亲结点(ji din)。兄弟结点(ji din)：同一双亲
3、结点(ji din)的孩子结点(ji din)之间互称兄弟结点(ji din)。第3页/共43页第四页，共43页。祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图中，结点K的祖先是A、B、E。子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。在图中，结点D的子孙是H、I、J、M。树的度：树中所有结点的度的最大值。结点的层次(cngc)：从根结点开始定义，根结点的层次(cngc)为1，根的直接后继的层次(cngc)为2，依此类推。树的高度（深度）：树中所有结点的层次(cngc)的最大值。有序树：在树 T中，如果各子树 Ti之间是有先后次序的，则称为有序树。森林：
4、m（m0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。第4页/共43页第五页，共43页。ADT Tree 数据对象D：一个集合(jh)，该集合(jh)中的所有元素具有相同的特性。数据关系R：若D为空集，则为空树。若D中仅含有一个数据元素，则 R为空集，否则 R=H，H是如下的二元关系：(1)在D中存在唯一的称为根的数据元素 root，它在关系H下没有前驱。(2)除root以外，D中每个结点在关系 H下都有且仅有一个前驱。第5页/共43页第六页，共43页。基本操作：(1)InitTree（Tree）：将Tree初始化为一棵
5、空树。(2)DestoryTree（Tree）：销毁树Tree。(3)CreateTree（Tree）：创建树Tree。(4)TreeEmpty（Tree）：若Tree为空，则返回TRUE，否则(fuz)返回FALSE。(5)Root（Tree）：返回树Tree的根。(6)Parent（Tree，x）：树Tree存在，x是Tree中的某个结点。若x为非根结点，则返回它的双亲，否则(fuz)返回“空”。第6页/共43页第七页，共43页。n n(7)FirstChild(7)FirstChild（TreeTree，x x）：）：树树TreeTree存在，存在，x x是是TreeTree中的某个结点
6、。若中的某个结点。若x x为非叶子结为非叶子结点，则返回它的第一个孩子结点，点，则返回它的第一个孩子结点，否则返回否则返回“空空”。n n(8)NextSibling(8)NextSibling（TreeTree，x x）：）：树树TreeTree存在，存在，x x是是TreeTree中的某个结点。若中的某个结点。若x x不是其双亲不是其双亲的最后的最后(zuhu)(zuhu)一个孩子结点，则返回一个孩子结点，则返回x x后面的下一个兄弟结点，后面的下一个兄弟结点，否则返回否则返回“空空”。第7页/共43页第八页，共43页。(9)InsertChild（Tree，p，Child）：树Tree存
7、在，p指向Tree中某个结点(ji din)，非空树Child与Tree不相交。将Child插入Tree中，做p所指向结点(ji din)的子树。(10)DeleteChild（Tree，p，i）：树Tree存在，p指向Tree中某个结点(ji din)，1id，d为p所指向结点(ji din)的度。删除Tree中p所指向结点(ji din)的第i棵子树。(11)TraverseTree（Tree，Visit（）：树Tree存在，Visit（）是对结点(ji din)进行访问的函数。按照某种次序对树 Tree的每个结点(ji din)调用Visit（）函数访问一次且最多一次。若 Visit（）
8、失败，则操作失败。第8页/共43页第九页，共43页。n n二叉树的定义二叉树的定义(dngy)与基本与基本操作操作 第9页/共43页第十页，共43页。定义：我们把满足以下两个条件的树形结构叫做二叉树（Binary Tree）：（1）每个结点的度都不大于 2；（2）每个结点的孩子结点次序不能任意颠倒。由此定义可以看出，一个二叉树中的每个结点只能含有0、1或2个孩子，而且每个孩子有左右(zuyu)之分。我们把位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。第10页/共43页第十一页，共43页。图给出了二叉树的五种基本(jbn)形态。第11页/共43页第十二页，共43页。与树的基本操作类似，二叉
9、树有如下基本操作：(1)Initiate（bt）：将bt初始化为空二叉树。(2)Create(bt)：创建一棵非空二叉树 bt。(3)Destory（bt）：销毁(xiohu)二叉树bt。(4)Empty（bt）：若bt为空，则返回 TRUE，否则返回FALSE。(5)Root(bt)：求二叉树bt的根结点。若 bt为空二叉树，则函数返回“空”。第12页/共43页第十三页，共43页。(6)Parent（bt，x）：求双亲函数。求二叉树 bt中结点x的双亲结点。若结点 x是二叉树的根结点或二叉树 bt中无结点x，则返回“空”。(7)LeftChild（bt，x）：求左孩子(hi zi)。若结点x
10、为叶子结点或 x不在bt中，则返回“空”。(8)RightChild（bt，x）：求右孩子(hi zi)。若结点x为叶子结点或 x不在bt中，则返回“空”。(9)Traverse（bt）:遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。(10)Clear（bt）：清除操作。将二叉树bt置为空树。第13页/共43页第十四页，共43页。n n二叉树二叉树的性质的性质(xngzh)第14页/共43页第十五页，共43页。性质1:在二叉树的第i层上至多有2i-1个结点(i1)。证明：用数学归纳法。归纳基础：当i=1时，整个二叉树只有一根结点，此时(c sh)2i-1=20=1，结论成立。归纳假
11、设：假设i=k时结论成立，即第k层上结点总数最多为2k-1个。现证明当i=k+1时，结论成立：因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即22k-1=2(k+1)-1，故结论成立。第15页/共43页第十六页，共43页。性质2:深度为k的二叉树至多有 2k-1个结点（k1）。证明：因为深度为 k的二叉树，其结点总数(zngsh)的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数(zngsh)至多为 故结论(jiln)成立。第16页/共43页第十七页，共43页。性质3:对任意一棵二叉树 T，若终端结点数为 n0，而其度数为 2的结
12、点数为n2，则n0=n2+1。证明：设二叉树中结点总数为 n，n1为二叉树中度为 1的结点总数。因为二叉树中所有结点的度小于等于 2，所以(suy)有n=n0+n1+n2 设二叉树中分支数目为 B，因为除根结点外，每个结点均对应一个进入它的分支，所以(suy)有n=B+1第17页/共43页第十八页，共43页。又因为二叉树中的分支(fnzh)都是由度为1和度为2的结点发出，所以分支(fnzh)数目为B=n1+2n2 整理上述两式可得到 n=B+1=n1+2n2+1 将n=n0+n1+n2 代入上式，得出 n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故结论成立。第18页/共43页第
13、十九页，共43页。满二叉树：深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。图6.3(a)所示的二叉树，即为一棵满二叉树。满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层内从左到右，逐层进行(jnxng)编号（1，2，n）。例如图6.3(a)所示的满二叉树的顺序表示为(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15)。第19页/共43页第二十页，共43页。完全二叉树：深度为k，结点(ji din)数为n的二叉树，如果其结点(ji din)1n的位置序号分别与满二叉树的结点(ji din)1n的位置序号一一对应，则为
14、完全二叉树，如图6.3(b)所示。满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。第20页/共43页第二十一页，共43页。图6.3 满二叉树与完全(wnqun)二叉树 第21页/共43页第二十二页，共43页。性质4：具有n个结点的完全二叉树的深度(shnd)为log2n+1。证明：假设n个结点的完全二叉树的深度(shnd)为k，根据性质2可知，k-1层满二叉树的结点总数为n1=2k-1-1 k层满二叉树的结点总数为 n2=2k-1 显然有n1nn2，进一步可以推出 n1+1nn2+1。将n1=2k-1-1 和n2=2k-1 代入上式，可得 2k-1n2k，即k-1log2n1，则序号为i
15、的结点的双亲结点序号为 i/2。（2）如2in，则序号为i的结点无左孩子；如 2in，则序号为i的结点的左孩子结点的序号为 2i。（3）如2i1n，则序号为i的结点无右孩子；如 2i1n，则序号为i的结点的右孩子结点的序号为 2i1。第23页/共43页第二十四页，共43页。可以用归纳法证明其中(qzhng)的（2）和（3）：当i=1时，由完全二叉树的定义知，如果 2i=2n，说明二叉树中存在两个或两个以上的结点，所以其左孩子存在且序号为2；反之，如果2n，说明二叉树中不存在序号为 2的结点，其左孩子不存在。同理，如果 2i+1=3n，说明其右孩子存在且序号为 3；如果3n，则二叉树中不存在序号
16、为 3的结点，其右孩子不存在。假设对于序号为 j(1ji)的结点，当2jn时，其左孩子存在且序号为 2j，当2jn 时，其左孩子不存在；当 2j+1n 时，其右孩子存在且序号为 2j+1，当2j+1n 时，其右孩子不存在。第24页/共43页第二十五页，共43页。当i=j+1时，根据完全(wnqun)二叉树的定义，若其左孩子存在，则其左孩子结点的序号一定等于序号为 j的结点的右孩子的序号加 1，即其左孩子结点的序号等于 （2j+1）+1=2（j+1）=2i，且有2in；如果2in，则左孩子不存在。若右孩子结点存在，则其右孩子结点的序号应等于其左孩子结点的序号加1，即右孩子结点的序号为 2i+1，
17、且有2i+1n；如果2i+1n，则右孩子不存在。故（2）和（3）得证。第25页/共43页第二十六页，共43页。由（2）和（3）我们可以很容易证明（1）。当i=1时，显然该结点为根结点，无双亲结点。当 i1时，设序号为 i的结点的双亲结点的序号为 m，如果序号为 i的结点是其双亲结点的左孩子，根据(gnj)（2）有i=2m，即m=i/2;如果序号为i的结点是其双亲结点的右孩子，根据(gnj)（3）有i=2m+1，即m=（i-1）/2=i/2-1/2，综合这两种情况，可以得到，当 i1时，其双亲结点的序号等于 i/2。证毕。第26页/共43页第二十七页，共43页。二叉树的存储(cn ch)结构 第
18、27页/共43页第二十八页，共43页。二叉树的结构是非线性的，每一结点最多可有两个后继(huj)。二叉树的存储结构有两种：顺序存储结构和链式存储结构。1.顺序存储结构(jigu)图6.4 二叉树与顺序存储结构(jigu)第28页/共43页第二十九页，共43页。图6.5 单支二叉树与其(yq)顺序存储结构 第29页/共43页第三十页，共43页。2.链式存储(cn ch)结构 对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子：LChildDataRChild其中(qzhng)，LChild域指向该结点的左孩子，Data域记录该结
19、点的信息，RChild域指向该结点的右孩子。第30页/共43页第三十一页，共43页。用C语言可以这样(zhyng)声明二叉树的二叉链表结点的结构：typedef struct NodeDataType data;struct Node*LChild;struct Node*RChild;BiTNode,*BiTree;有时，为了便于找到父结点，可以增加一个(y)Parent域，Parent域指向该结点的父结点。该结点结构如下：LChildDataparentRChild第31页/共43页第三十二页，共43页。图6.6 二叉树和二叉链表 第32页/共43页第三十三页，共43页。若一个二叉树含有
20、n个结点，则它的二叉链表中必含有 2n个指针域，其中必有n1个空的链域。此结论(jiln)证明如下：证明：分支数目 B=n-1，即非空的链域有 n-1个，故空链域有 2n-(n-1)=n+1 个。不同的存储结构实现二叉树的操作也不同。如要找某个结点的父结点，在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找。可见，在具体应用中，需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。第33页/共43页第三十四页，共43页。二叉树的遍历(bin l)第34页/共43页第三十五页，共43页。图6.7 二叉树结点(ji din)的基本结构 第35页/共43页第三十六页，共43页。我们用
21、L、D、R分别表示(biosh)遍历左子树、访问根结点、遍历右子树，那么对二叉树的遍历顺序就可以有六种方式：(1)访问根，遍历左子树，遍历右子树（记做 DLR）。(2)访问根，遍历右子树，遍历左子树（记做 DRL）。(3)遍历左子树，访问根，遍历右子树（记做 LDR）。(4)遍历左子树，遍历右子树，访问根（记做 LRD）。(5)遍历右子树，访问根，遍历左子树（记做 RDL）。(6)遍历右子树，遍历左子树，访问根（记做 RLD）。第36页/共43页第三十七页，共43页。注意：先序、中序、后序遍历是递归定义(dngy)的，即在其子树中亦按上述规律进行遍历。下面就分别介绍三种遍历方法的递归定义(dn
22、gy)。先序遍历（DLR）操作过程：若二叉树为空，则空操作，否则依次执行如下 3个操作：(1)访问根结点；(2)按先序遍历左子树；(3)按先序遍历右子树。第37页/共43页第三十八页，共43页。中序遍历（LDR）操作过程：若二叉树为空，则空操作，否则依次执行如下(rxi)3 个操作：(1)按中序遍历左子树；(2)访问根结点；(3)按中序遍历右子树。后序遍历（LRD）操作过程：若二叉树为空，则空操作，否则依次执行如下(rxi)3 个操作：(1)按后序遍历左子树；(2)按后序遍历右子树；(3)访问根结点。第38页/共43页第三十九页，共43页。先序遍历(bin l)：A、B、D、F、G、C、E、H
23、。中序遍历(bin l)：B、F、D、G、A、C、E、H。后序遍历(bin l)：F、G、D、B、H、E、C、A。图6.8 二叉树 第39页/共43页第四十页，共43页。中序遍历(bin l)二叉树的递归过程 第40页/共43页第四十一页，共43页。最早提出遍历问题是对存储在计算机中的表达式求值。例如：（a+b*c）-d/e。该表达式用二叉树表示如图所示。当我们对此二叉树进行先序、中序、后序(hu x)遍历时，便可获得表达式的前缀、中缀、后缀书写形式：前缀：-+a*bc/de 中缀：a+b*c-d/e 后缀：abc*+de/-其中中缀形式是算术表达式的通常形式，只是没有括号。前缀表达式称为波兰表达式。算术表达式的后缀表达式被称作逆波兰表达式。在计算机内，使用后缀表达式易于求值。第41页/共43页第四十二页，共43页。图6.9 算术(sunsh)式的二叉树表示 第42页/共43页第四十三页，共43页。