数据结构——树的概念和二叉树VIP免费

第四章树的概念和二叉树吉林大学计算机学院谷方明fmgu2002@sina.com4.1树的基本概念树是一种非常重要的非线性数据结构，可用来描述客观世界中中广泛存在的具有分支或层次关系的对象。1.树的定义(递归版)定义4.1：一棵树（或树形）是一个有限非空的结点集合T，其中：1.有一个被称为根的结点，记为root(T)；2.其余结点被分成m0个不相交的集合T1，T2，…，Tm，且T1，T2，…，Tm又都是树。树T1，T2，…，Tm称作root(T)的子树，每一棵子树的根都和root(T)有一条边连接。AECDBIHGF定义4.2（非递归版）树是包含n(n≥1)个结点有限集合，满足如下条件：1.存在一个唯一的结点v0，没有前驱结点，称为树的根（或根结点）；2.任一非根结点都有且仅有一个前驱结点，称为该结点的父结点；（任何结点都可能有零或多个后继结点，称之为该结点的子结点）3.任一非根结点vk都有且仅有一条从v0到该结点的路径：v0v1…vk，其中vi是vi1（1ik）的子结点。2.树的相关术语1.度一个结点的子结点的数目，称为该结点的度。一棵树的度为maxi=1,…,nD(i)，其中n为树中结点总数，i指树中的第i个结点，D(i)表结点i的度。2.叶结点、分支结点度为0的结点被称为叶结点；度大于0的结点被称为分支结点。3.结点的层数⑴root(T)层数为零；⑵其余结点的层数为其前驱结点的层数加1；4.树的高度树的高度是指树中结点的最大层数，即maxi=1,…,nNL(i)，其中n为树中结点总数，i指树中第i个结点，NL(i)之值为结点i的层数。5.路径若树T中存在结点序列v1v2…vk，满足(vi,vi+1)是树的边，则称此结点序列为v1到vk的路径。路径所经历的边数被称为路径长度。6.子孙结点、祖先结点、兄弟结点一棵树中若存在结点vm到vn的路径，则称vn为vm的子孙结点，vm为vn的祖先结点。同一个父亲的诸子结点称为兄弟结点。树作为无向图的性质1.有n-1条边；2.连通3.无环树的等价定义1.连通无环图（自由树或无根树，没有确定根，选定一顶点作根，则成为一棵通常的树）2.n-1条边的连通图（归纳、必有度为1的点）3.n-1条边的无环图（归纳、每个连通分支）3、树在计算机领域有广泛的应用操作系统中，文件及文件夹的存储，软件的菜单等都是树；在分析算法时，可用树来描述其执行过程，如递归调用、搜索等；……4.2二叉树定义4.3：二叉树是结点的有限集合，它或者是空集，或者由一个根及左、右两个不相交的的二叉树构成。这两棵子树分别称为左、右子树。树与二叉树的主要区别I.二叉树每个结点最多有2个子结点，树则无此限制；II.二叉树中结点的子树分成左子树和右子树，即使某结点只有一棵子树，也要指明该子树是左子树，还是右子树，即二叉树是有序的；III.树决不能为空（换言之树不能为空集），它至少有一个结点，而一棵二叉树可以是空的（或者说二叉树可以为空集）。A(a)(b)(c)(d)(e)ACBACBCBACBACB含有3个结点的不同二叉树引理4.1二叉树中层数为i的结点至多有2i个，i≥0。引理4.2高度为k的二叉树中至多有2k+1-1(k≥0)个结点。引理4.3设T是由n个结点构成的二叉树，其中叶子结点个数为n0，度为2的结点个数为n2，则有：n0＝n2＋1证明：设度为1的结点有n1个，总结点个数为n，总边数为e，则：n=n0+n1+n2(1)e=n-1(2)e=2n2+n1(3)因此，有n0+n1+n2-1=2n2+n1n0=n2+1证毕。满二叉树定义4.4一棵非空高度为k(k0)的满二叉树，是有2k+11个结点的二叉树。156437298101311121415满二叉树的特点①叶结点都在第k层上；②每个分支结点都有两个子结点；③叶结点的个数等于非叶结点个数加1完全二叉树定义4.5一棵包含n个结点高为k的二叉树T，当按层次顺序编号T的所有结点，对应于一棵高为k的满二叉树中编号由1至n的那些结点时，T被称为完全二叉树。56437298101完全二叉树的特点树中叶结点只能在层数最大的两层上出现；树中最下一层的结点都集中在该层最左边的若干位置上；仅仅编号最大的分支结点可以没有右孩子，其余分支结点都有两个孩子；引理4.4若将一颗具有n个结点的完全二叉树按层次次序从1开始编号，则对编号为i(1in)的结点有：①若i≠1，则编号为i的结点的父结点的编号为i/2。②若2in，则编号为i的结点的左孩...