文档章节

树的基本概念

石飞飞
 石飞飞
发布于 2017/07/04 20:36
字数 853
阅读 32
收藏 0
点赞 0
评论 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;  //指向下一个孩子结点
      
          }
      
      }
      

       

© 著作权归作者所有

共有 人打赏支持
石飞飞
粉丝 1
博文 64
码字总数 39883
作品 0
朝阳
程序员
求解一道这个实验的代码

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

扭屁股的大师兄
2012/12/12
161
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
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
设计模式知识梳理(3) - 结构型 - 组合模式

一、基本概念 1.1 定义 组合模式将一组看似相似的对象看作一个对象处理,并根据一个树状结构来组合对象,然后提供一个统一的方法去访问相应的对象,以此 忽略掉对象与对象集合 之间的差别。 ...

泽毛
06/28
0
0
python快速求解不定积分和定积分

欢迎点击「算法与编程之美」↑关注我们! 本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列博客。 基本概念 定积分的定义如下: 不定积分定义如下: 如果想了解更多,...

算法与编程之美
07/10
0
0
union/find--不相交集合

前言 大家好,今天提供不相交集合的笔记(即union/find).不相交集合有实现简单,证明困难的特点,若有想证明的可以自行查阅相关文献。我就不做赘述啦! 用途 不相交集类解决动态等价类问题,...

温安适
2016/12/02
229
2
数据结构的基本概念

(一)什么是数据结构 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效...

九劫散仙
02/01
0
0
算法知识梳理(11) - 二叉树相关算法第一部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/19
0
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

shell中的函数、shell中的数组、告警系统需求分析

shell中的函数 格式: 格式: function f_name() { command } 函数必须要放在最前面 示例1(用来打印参数) 示例2(用于定义加法) 示例3(用于显示IP) shell中的数组 shell中的数组1 定义数...

Zhouliang6
46分钟前
1
0
用 Scikit-Learn 和 Pandas 学习线性回归

      对于想深入了解线性回归的童鞋,这里给出一个完整的例子,详细学完这个例子,对用scikit-learn来运行线性回归,评估模型不会有什么问题了。 1. 获取数据,定义问题     没有...

wangxuwei
今天
1
0
MAC安装MAVEN

一:下载maven压缩包(Zip或tar可选),解压压缩包 二:打开终端输入:vim ~/.bash_profile(如果找不到该文件新建一个:touch ./bash_profile) 三:输入i 四:输入maven环境变量配置 MAVEN_HO...

WALK_MAN
今天
0
0
33.iptables备份与恢复 firewalld的9个zone以及操作 service的操作

10.19 iptables规则备份和恢复 10.20 firewalld的9个zone 10.21 firewalld关于zone的操作 10.22 firewalld关于service的操作 10.19 iptables规则备份和恢复: ~1. 保存和备份iptables规则 ~2...

王鑫linux
今天
1
0
大数据教程(2.11):keeperalived+nginx高可用集群搭建教程

上一章节博主为大家介绍了目前大型互联网项目的系统架构体系,相信大家应该注意到其中很重要的一块知识nginx技术,在本节博主将为大家分享nginx的相关技术以及配置过程。 一、nginx相关概念 ...

em_aaron
今天
1
0
Apache Directory Studio连接Weblogic内置LDAP

OBIEE默认使用Weblogic内置LDAP管理用户及组。 要整理已存在的用户及组,此前办法是导出安全数据,文本编辑器打开认证文件,使用正则表达式获取用户及组的信息。 后来想到直接用Apache Dire...

wffger
今天
2
0
HFS

FS,它是一种上传文件的软件。 专为个人用户所设计的 HTTP 档案系统 - Http File Server,如果您觉得架设 FTP Server 太麻烦,那么这个软件可以提供您更方便的档案传输系统,下载后无须安装,...

garkey
今天
1
0
Java IO类库之BufferedInputStream

一、BufferedInputStream介绍 /** * A <code>BufferedInputStream</code> adds * functionality to another input stream-namely, * the ability to buffer the input and to * sup......

老韭菜
今天
0
0
STM 32 窗口看门狗

http://bbs.elecfans.com/jishu_805708_1_1.html https://blog.csdn.net/a1985831055/article/details/77404131...

whoisliang
昨天
1
0
Dubbo解析(六)-服务调用

当dubbo消费方和提供方都发布和引用完成后,第四步就是消费方调用提供方。 还是以dubbo的DemoService举例 -- 提供方<dubbo:application name="demo-provider"/><dubbo:registry address="z...

青离
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部