文档章节

树的基本概念

石飞飞
 石飞飞
发布于 2017/07/04 20:36
字数 853
阅读 34
收藏 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
朝阳
程序员
求解一道这个实验的代码

实验六 堆和搜索树 一、要求完成时间 实验开始后的第七周之前完成 二、实验目的 掌握堆和搜索树的基本概念,插入、删除方法。 三、实验内容 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
数据结构的基本概念

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

九劫散仙
02/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

多线程

1. 多线程概念。并发和并行的概念。 多线程指的是一段时间内cpu同时执行多个线程。一个程序至少运行>=1个进程,进程就是运行中的程序,而一个进程至少运行>=1个线程,线程是操作系统能调度的...

鱼想吃肉
36分钟前
0
0
HBase 表修复在线方式和离线方式

一、在线修复 1.1 使用检查命令 $ ./bin/hbase hbck 该命令可完整修复 HBase 元数据信息;存在有错误信息会进行输出; 也可以通过如下命令查看详细信息: $ ./bin/hbase hbck -details 1.2 ...

Ryan-瑞恩
今天
2
0
redis 系列二 -- 常用命令

1.基础命令 info ping quit save dbsize select flushdb flushall 2.键命令 2.1 set 直接赋值 set a a 2.2 get 取值 get a 2.3 exists 是否存在 exists a 2.4 expire 设置剩余时间 秒 expire......

imbiao
今天
2
0
php foreach

<?php// 数组的引用$a=array(1,2,3,4,5);foreach($a as $key=>&$value){$value=$value*2;}print_r($a);echo " $key -------------------$value\r\n";/** * ...

小张525
今天
3
0
12-利用思维导图梳理JavaSE-多线程

12-利用思维导图梳理JavaSE-多线程 主要内容 1.线程概念 2.线程开发 3.线程的状态 4.线程的同步和死锁 5.Java5.0并发库类 QQ/知识星球/个人WeChat/公众号二维码 本文为原创文章,如果对你有一...

飞鱼说编程
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部