张小弟博客

梦想需要付诸行动,否则只能是梦

数据结构 树 笔记

  7.1

  7.1.1 树的定义

  :由n(n≥0)个结点(或元素)组成的有限集合(记为T)。

  如果n=0,它是一棵空树,这是树的特例;

  如果n>0,这n个结点中有且仅有一个结点作为树的根结点,简称为,其余结点可分为m(m≥0)个互不相交的有限集T1, T2, …, Tm,其中每个子集本身又是一棵符合本身定义的树,称为根结点的子树

  7.1.2 树的逻辑表示方法

  (1)树形表示法

  (2)文氏图表示法

  (3)凹入表示法

  (4)括号表示法

  7.1.3 树的基本术语

  (1)结点的度与树的度

  结点的度:树中某个结点的子树的个数

  树的度:树中所有结点的度中的最大值

  m次树:度为m的树

  (2)分支结点与叶子结点

  分支结点(非终端结点):树中度不为0的结点

  叶子结点:度为0的结点

  单分支结点:度为1的结点(分支数为1)

  双分支结点:度为2的结点(分支数为2)

  (3)路径与路径长度

  路径:对于树中的任意两个结点ki和kj,若树中存在一个结点序列(ki, ki1, ki2, …, kin, kj),使得序列中除ki以外的任一结点都是其在序列中的前一个结点的后继结点,则称该结点序列为由ki到kj的一条路径

  路径长度:是该路径所通过的结点数目减1(即路径上分支数目)

  (4)孩子结点、双亲结点和兄弟结点

  孩子结点、双亲结点:在一棵树中,每个结点的后继结点被称为该结点的孩子结点。相应地,该结点被称为孩子结点的双亲结点

  兄弟结点:具有同一双亲结点的孩子结点互为兄弟结点

  子孙结点:每个结点对应子树中的所有结点(除自身外)称为该结点的子孙结点

  祖先结点:把从根结点到达某个结点的路径上经过的所有结点(除自身外)称为该结点的祖先结点

  (5)结点层次和树的高度

  结点层次结点深度:从树根开始定义,根结点为第一层,它的孩子结点为第二层,依此类推,一个结点所在的层次为其双亲结点的层次加1。

  树的高度树的深度:树中结点的最大层次

  (6)有序树和无序树

一般情况下,如果没有特别说明,默认树都是指有序树

  树中各结点的子树按照一定次序从左向右安排,且相对次序不能随意变换,称为有序树,否则称为无序树

  (7)森林

把含有多棵子树的树时的根结点删去就成了森林。反之,给m(m>1)棵独立的树加上一个根结点,并把这m棵树作为该结点的子树,则森林就变成了一棵树。

  森林:n(n>0)个互不相交的树的集合

  7.1.4 树的性质(证明见书P192-193)

  性质1:树中的结点数等于所有结点的度数之和加1

  性质2:度为m的树中第i层上最多有m^(i-1)个结点(i≥1)

  性质3:高度为h的m次树最多有(m^h - 1) / (m - 1)个结点

  性质4:具有n个结点的m次树的最小高度为┌log m ( n(m-1) + 1 )┐

  7.1.5 树的基本运算

  1. 先根遍历

  (1)访问根结点

  (2)按照从左到右的顺序先根遍历根结点的每一棵子树

  2. 后根遍历

  (1)按照从左到右的顺序后根遍历根结点的每一棵子树

  (2)访问根结点

  3. 层次遍历

  从根结点开始,从上到下、从左到右的顺序访问树中的每一个结点

  7.1.6 树的存储结构(书P195-P198)

  1. 双亲存储结构

  2. 孩子链存储结构

  3. 孩子兄弟链存储结构

  7.2 二叉树

  7.2.1 二叉树的定义

  二叉树:一个有限的结点集合,这个集合或者为空,或者由一个根结点和两棵互不相交的【书上这里似乎掉了点东西】称为左子树和右子树的二叉树组成

  满二叉树

  在一棵二叉树中,所有分支结点都有左孩子结点和右孩子结点,且叶子结点都集中在二叉树的最下一层

  一棵高度为h且有2^h - 1个结点的二叉树

  特点:

  叶子结点都在最下一层

  只有度为0和度为2的结点

  完全二叉树:二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶子结点都依次排列在该层最左边的位置上

  特点:

  叶子结点只可能在最下面两层

  对于最大层次中的叶子结点,都依次排列在该层最左边的位置上

  如果有度为1的结点,只可能有1个,且该结点只有左孩子而无右孩子

  按层序编号时,一旦出现编号为i的结点是叶子结点或只有左孩子,则编号大于i的结点均为叶子结点

  当结点总数n为奇数时,n1=0,当结点总数n为偶数时,n1=1

  (满二叉树是完全二叉树的一种特例)

  层序编号:约定编号从树根为1开始,按照层序从小到大、同一层从左到右的次序进行。

  7.2.2 二叉树的性质

  P199 待完善


张小弟之家

本文链接:
文章标题:

本站文章除注明转载/出处外,均为原创,若要转载请务必注明出处。转载后请将转载链接通过邮件告知我站,谢谢合作。本站邮箱:admin@mail.only4.work

尊重他人劳动成果,共创和谐网络环境。点击版权声明查看本站相关条款。

    打赏

    发表评论:

    本文二维码
    搜索
    标签列表
    站点信息
    • 文章总数:198
    • 页面总数:20
    • 分类总数:69
    • 标签总数:121
    • 评论总数:25
    • 浏览总数:29963
    • 订阅本站的 RSS 2.0 新闻聚合

    || |||||||

    ||


                MySSL 安全签章
    Z-BlogPHP