资源描述：
《数据结构课辅导（二）.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构课程辅导（二）---树和二叉树徐孝凯一、树的概念1.树的定义
树(Tree)是树型结构的简称。它是一种重要的非线性数据结构。树——或者是一棵空树，即不含有任何结点（元素），或者是一棵非空树，即至少含有一个结点。在一棵非空树中，它有且仅有一个称作根(root)的结点，其余的结点可分为m棵(m≥0)互不相交的子树(即称作根的子树)，每棵子树(SubTree)又同样是一棵树。显然，树的定义是递归的，树是一种递归的数据结构。树的递归定义，将为以后实现树的各种运算提供方便。图5-1(a)就是一棵树T，它由根结点A和两棵子树T1和T2所组成,T1和T2分别对应图5-1(b)
2、和(c)所示；T1又由它的根结点B和三棵子树T11,T12和T13所组成，这三棵子树分别对应图5-1(d),(e)和(f)所示；T11和T13只含有根结点，不含有子树（或者说子树为空树），不可再分；T12又由它的根结点E和两棵只含有根结点的子树所组成，每棵子树的根结点分别为H和I；T2由它的根结点C和一棵子树所组成，该子树也只含有一个根结点G，不可再分。图5-1树的结构在一棵树中，每个结点被定义为它的每个子树的根结点的前驱，而它的每个子树的根结点就成为它的后继。由此可用二元组给出树的定义：tree=(K,R)K={ki
3、1≤i≤n,n≥0,ki∈ElemType}R={
4、r}其中n为树中结点数，n=0则为空树，n>0则为非空树。对于一棵非空树，关系r应满足下列条件：(1)有且仅有一个结点没有前驱，该结点被称为树的根；(2)除树根结点外，其余每个结点有且仅有一个前驱结点；(3)包括树根结点在内的每个结点，可以有任意多个(含0个)后继。22对于图4-1(a)所示的树T，若采用二元组表示，则结点的集合K和K上二元关系r分别为：K={A,B,C,D,E,F,G,H,I}r={,,,,,,,}其中A结点无前驱结点，被称为树的根结点；其余每个结点有且仅有一个前驱结点；在
5、所有结点中，B结点有三个后继结点，A结点和E结点分别有两个后继结点，C结点有一个后继结点，其余结点均没有后继结点。在日常生活和计算机领域，树结构广泛存在。例1可把一个家族看作为一棵树，树中的结点为家族成员的姓名及相关信息，树中的关系为父子关系，即父亲是儿子的前驱，儿子是父亲的后继。图5-2(a)就是一棵家族树，王庭贵有两个儿子王万胜和王万利，王万胜又有三个儿子王家新、王家中和王家国。例2可把一个地区或一个单位的组织结构看作为一棵树，树中的结点为机构的名称及相关信息，树中的关系为上下级关系。如一个城市分为若干个区，每个区又分为若干个街道，每个街道又分为若干个居委会等。例3
6、可把一本书的结构看作为一棵树，树中的结点为书、章、节的名称及相关信息，树中的关系为包含关系。图5-2(b)是一本书的结构，根结点为书的名称数学，它包含三章，每章名称分别为加法、减法和乘法，加法一章又包含两节，分别为一位加和两位和，减法和乘法也分别包含若干节。例4可把一个算术表达式表示成一棵树，运算符作为根结点，它的前后两个运算对象分别作为根的左、右两棵子树。如把算术表达式a*b+(c-d/e)*f表示成树，则如图5-2(c)所示。图5-2树应用的例子3.树的基本术语(1)结点的度和树的度每个结点具有的子树数或者说后继结点数被定义为该结点的度(degree)。树中所有结点
7、的度的最大值被定义为该树的度。如在图5-1的树T中，B结点的度为3，A,E结点的度均为2，C结点的度为1，其余结点的度均为0。因结点的最大的度为3，所以树T的度为3。(2)分支结点和叶子结点在一课树中，度等于0的结点称作叶子结点或终端结点，度大于0的结点称作分支结点或非终端结点。在分支结点中，每个结点的分支数就是该结点的度数，如对于度为1的结点，其分支数为1，所以被称之为单分支结点；对于度为2的结点，其分支数为2，所以被称之为双分支结点，其余类推。如在图5-1的树T中，D,H,I,F,G都是叶子结点；A,B,C,22E是分支结点，其中C为单分支结点，A和E为双分支结点，
8、B为三分支结点。(3)孩子结点、双亲结点和兄弟结点在一棵树中，每个结点的子树的根，或者说每个结点的后继，被习惯地称作该结点的孩子、儿子或子女(child)，相应地，该结点被称作孩子结点的双亲、父亲或父母(parent)。具有同一双亲的孩子互称兄弟(brothers)。每个结点的所有子树中的结点被称作该结点的子孙。每个结点的祖先则被定义为从树根结点到达该结点的路径上经过的所有结点。如在图5-1的树T中，B结点的孩子为D,E,F结点，双亲为A结点，D,E,F互为兄弟，B结点的子孙为D,E,H,I,F结点，I结点的祖先为A,B,E结点，对于树T
