树的基本概念
树的基本概念
石飞飞 发表于10个月前
树的基本概念
  • 发表于 10个月前
  • 阅读 27
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

摘要: 本篇主要记录树的相关概念以及树的存储结构设计

【1】树的定义以及相关术语

  • 树:树(tree)是包含n(n>0)个结点的有穷集,其中:
    • 每个元素称为结点(node)

    • 有一个特定的结点被称为根结点或树根(root)

    • 除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,... Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)

  • 树的结点:

    • 结点拥有的子树数称为结点的

    • 度为零的结点称为叶子结点;

    • 度不为零的结点称之为分支结点,分支结点也称之为内部结点;

    • 树的度是树内各个结点度的最大值;

    • 树中结点的最大层次称为树的深度
  • 树的存储结构探索
    • 双亲表示法:树的这种存储结构,除了根结点以外,其余每个结点,不一定有孩子结点,但一定有且仅有一个双亲结点;假设我们用一组连续的存储空间来存储树的所有结点,在每个结点中另外存储双亲结点所在的位置;如下图所示:
    • 用Java代码表示其数据结构形式:
    • public class Tree {
          
          Node[] elements;
      
          /*根节点位置,由于根节点没有双亲,约定其位置-1*/
          int rootIndex;
      
          /*元素个数*/
          int size;
      
          static class Node {
              /*结点数据*/
              Object data;
      
              /*双亲位置*/
              int parent;
          }
      }

      用图的形式来展示这种数据结构的设计会更直观的理解,现有如下图所示的树:

    • 当用双亲表示法来存储其数据结构时,我们可以用表格来直观的表示其数据存储形式:

    • 我们看到,数组依次存储了树的元素,我们很容易找到树的双亲结点,时间复杂度为O(1),直到parent=-1时,表示找到了根节点,如果要找孩子结点,只能遍历整棵树了;

    • 为了减少遍历,我们可以进行如下改进:我们增加一个结点左边孩子的域,简称左孩子域,这样就很容易得到结点的孩子;没有孩子的结点,其左孩子域设置-1,如下图所示:

    • 孩子表示法:为了遍历整棵树,我们把每个结点放到一个顺序存储结构的数组中,但每个结点的孩子有多少是不确定的,所以我们在对每个结点孩子建立一个单链表来存储,这就是孩子表示法,具体设计方法是:把每个结点的孩子结点排列起来,以单链表作为存储结构,则n个结点有n个孩子链表,如果是叶子结点则单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放到一个一维数组中,如下图所示:

    • Java代码表示形式如下:

    • package com.promotion.action.data.struct.tree.data.model;
      
      /**
       * 树的孩子表示法
       */
      public class CTree {
      
          private Integer maxSize = 100;
      
          /*存储所有树结点*/
          private Node[] data;
          /*树的结点个数*/
          private int size;
      
      
          /*表头结点*/
          private static class Node<T> {
              T data;
              ChildNode firstChild;
          }
      
          /*孩子结点链表*/
          private static class ChildNode {
      
              int child; //孩子结点下标
              ChildNode next;  //指向下一个孩子结点
      
          }
      
      }
      

       

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 1
博文 60
码字总数 38376
×
石飞飞
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: