术语
树和子树
以根结点为根的树为全树(或树),以其他结点作为根结点的树为子树
叶子结点
度为0的结点就是叶子结点,它位于树最深层,并且树只要非空,就一定存在叶子结点
分支结点
度大于0的结点为分支结点,显然除了叶子结点之外的结点都为分支结点。
父节点和<br>子结点
一个结点若干分支下的结点都为该结点的子结点(或称孩子(children)),<br>并且,该结点称为子结点的父节点
兄弟结点和<br>堂兄弟结点
兄弟结点:父节点下的所有子结点互为兄弟结点,如下图,B,C,D结点互为兄弟结点
堂兄弟结点:位于同一层的,并且父节点之间是兄弟结点的结点互为堂兄弟结点,<br>下图中,E,G为堂兄弟结点,F和G也是堂兄弟结点,他们的父节点是兄弟结点。
子主题
祖先和子孙
这个关系就同父亲和孩子一样。从根结点到该结点路径上的所有结点都为该结点的祖先,<br>如下图所示
反之,C,G,H就是A的子孙,G和H都为C的子孙,H也可以称为G的子孙,不过因为G和H只隔一代,<br>所以一般称为孩子,如下图
所有的结点都有一个公共祖先,就是根结点,但任意两个结点可以不只一个祖先,比如E和F的公共祖先有A和B
路径
从一个结点到另一个结点之间的边和结点构成路径,如下图<br>
A到H的路径包含A,C,G,H结点和连接这些结点的三条边
子树的根节点
如图,A的子树根结点为B,C,D。B的子树根结点为E,F,D没有子树根结点
子主题
层次
结点的层次为从结点到根结点的路径中边的条数,并且认为根结点的层次为0,<br>因为根结点到自身的路径中边的条数为0(但有些教科书也会认为根结点的层次为1)<br>
结点的层次有时也称为结点的深度
树的深度
树的深度是结点中的最大深度(或最大层次)
结点的高度
从一个结点出发,一直到它的叶子结点的最大路径中的边的条数,<br>就是该结点的高度,叶子结点的高度认为是0
高度与深度不同,高度的描述是自下向顶的,而深度是自顶向下的,<br>同一层次的结点的高度是可以不同的
森林
森林就是彼此不相交的树的集合,树也可以看成是森林共有一个根结点后的结构
子主题
性质
树的结点数等于所有结点的度+1<br>即n=n0+n1+n2+n3<br> =0*n0+1*n1+2*n2+3*n3+1
在一棵三元树中度为3的结点数为2个,度为2的结点数为1个,<br>度为1的结点数为2个,则度为0的结点数为<br>树中结点数等于所有结点度数的和加1。<br>所以:2+1+2+X=2*3+1*2+2*1+X*0+1,所以X=6<br>
度m的树第i层至多有m^(i-1)个结点
高度为h的m叉树至多有(m^h-1)/(m-1)个结点,至少h+m-1个
具有n个结点的m叉树最小高度为logm(n(m-1)+1)向上取整