树的概念和定义课堂PPT

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