文档章节

树的基本概念

石飞飞
 石飞飞
发布于 2017/07/04 20:36
字数 853
阅读 36
收藏 0

【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;  //指向下一个孩子结点
      
          }
      
      }
      

       

© 著作权归作者所有

共有 人打赏支持
上一篇: 二叉树
下一篇: 栈和队列
石飞飞
粉丝 2
博文 64
码字总数 39883
作品 0
朝阳
程序员
私信 提问
Java HashMap涉及的数据结构及实现

提供的功能 基于哈希表实现的Map; 非线程安全的Map实现; 键和值都可以为null(因为有处理null的情形); 基本操作和的时间消耗是固定的; 数据存储结构会随着HashMap的数量而变换成不同的数据...

666B
11/30
0
0
求解一道这个实验的代码

实验六 堆和搜索树 一、要求完成时间 实验开始后的第七周之前完成 二、实验目的 掌握堆和搜索树的基本概念,插入、删除方法。 三、实验内容 1、输入一系列不为零的正整数(最多不超过20个),...

扭屁股的大师兄
2012/12/12
218
2
二叉树的基本概念

二叉树的定义 一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 二叉树的5种基本形态,任意一棵二叉树都由这...

大胖和二胖
2016/11/29
15
0
《算法导论》学习笔记之Chapter13红黑树

第13章 红黑树 红黑树是一种平衡搜索树中的一种,他可以保证在最坏情况下基本动态集合操作时间复杂度为O(logn)。所以,在学习红黑树之前,我需要先去调研一下平衡树; 先看一下平衡树的定义:...

u010483897
2017/12/13
0
0
Trie 树实现与应用

Trie树 基本概念  Trie树又称字典树,它是用来查询字符串的一种数据结构。它每一个节点都有26个子节点,所以是26叉树。优点查询字符串的时候速度快,缺点浪费大量空间。  当一个字符串长为...

sdoyuxuan
01/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

《Maven官方文档》-Maven依赖机制简介

《Maven官方文档》-Maven依赖机制简介 原文地址 译者:Tyrian 依赖机制是Maven最为用户熟知的特性之一,同时也是Maven所擅长的领域之一。单个项目的依赖管理并不难, 但是当你面对包含数百个...

tantexian
11分钟前
0
0
基于 Docker 快速部署多需求 Spark 自动化测试环境

引言 在进行数据分析时,Spark 越来越广泛的被使用。在测试需求越来越多、测试用例数量越来越大的情况下,能够根据需求快速自动化部署 Spark 环境、快速完成所有测试越来越重要。 本文基于 ...

呐呐丶嘿
29分钟前
2
0
支付宝APP支付之查看支付宝商户ID

1、登录支付宝蚂蚁金服开放平台 2、查看账号详情,选择合作伙伴管理,账户管理,查看角色身份,此处的PID就是商户ID 3、点击秘钥管理,可查看绑定的相关应用及其APPID等信息

Code辉
32分钟前
2
0
崛起于Springboot2.X之通讯WebSocket(40)

技术简介:Springboot2.0.3+freemaker+websocket 1、添加pom依赖 <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-bo......

木九天
40分钟前
1
0
Java常用四大线程池用法以及ThreadPoolExecutor详解

为什么用线程池? 1.创建/销毁线程伴随着系统开销,过于频繁的创建/销毁线程,会很大程度上影响处-理效率 2.线程并发数量过多,抢占系统资源从而导致阻塞 3.对线程进行一些简单的管理 在Java中...

孟飞阳
42分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部