• 非线性结构
  • 树是n(n >= 0)个元素的集合:
    • (1)每个元素称为结点(node);
    • (2)有一个特定的结点,称为根结点或根(root);
    • (3)除根结点外,其余结点被分成m(m>=0)个互不相交的有限集合,而每个子集又都是一棵树(称为原树的子树Subtree)
  • 注意
    • n = 0时,称为空树
    • 树只有一个特殊的没有前驱的元素,称为树的根(Root)
    • 树中除了根结点外,其余元素只能有一个前驱,可以有零个或多个后继
    • 子树也有自己的根

树的概念

  • 结点(node):树中的数据元素
  • 结点的度(degree):结点拥有的子树的数目称为度(该结点的分支数),记作d(v)
  • 叶子结点:结点的度为0,称为叶子结点leaf、终端结点、末端结点
  • 分支结点:结点的度不为0,称为非终端结点或分支结点
  • 分支:结点之间的关系
  • 内部结点:除根结点外的分支结点,也不包括叶子结点
  • 树的度是树内各结点的度的最大值。  D子树的度就是3

59df2441cf5be4075000000f

  • 孩子结点(Child):
    • B是A的孩子
  • 双亲结点(Parent):
    • C是E,F的双亲
  • 兄弟结点(Sibling):
    • 具有相同双亲结点的结点
    • B和C是兄弟
  • 祖先结点:
    • 从根结点到该结点所经分支上所有的点
    • A,B,D都是G的祖先结点
  • 子孙结点:
    • 结点的所有子树上结点都称为该结点的子孙
    • C的子孙是E,F,J
  • 结点的层次(level):
    • 根结点为第一层,根的孩子为第二层,以此类推,记作L(v)
  • 树的深度(高度Depth):
    • 树的层次的最大值
    • 上图树深度为4
  • 堂兄弟:
    • 双亲在同一层的结点
    • D,E或F是堂兄弟

59df2441cf5be4075000000f

  • 有序树
    • 结点的子树是有顺序的(兄弟有大小,先后次序)
  • 无序树
    • 结点的子树是无序的,可以交换
  • 路径
    • 一条线串下来的,前一个都是后一个的双亲结点
  • 路径长度   =   路径上的结点数 – 1 ,也是分支数
  • 森林
    • m(m>=0)颗不相交的树的集合
    • 对于结点而言,其子树的集合就是森林。
    • A结点的2颗子树的集合就是森林

树的特点

  • 唯一的根
  • 子树不相交
  • 除根以外,每个元素只能有一个前驱,可以有零个或多个后继
  • 根结点没有双亲,叶子结点没有孩子
  • vi是vj的双亲,则L(vi) = L(vj) – 1, 也就是说双亲比孩子结点的层次小1
  • 堂兄弟的双亲未必是兄弟,例如I,J是堂兄弟,而他们的双亲也是堂兄弟

二叉树

  • 每个结点最多2颗子树
    • 二叉树不存在degree > 2 的结点
  • 是有序树,左子树、右子树是顺序的,不能交换次序
  • 即使某个结点有一颗子树,也要确定是左子树还是右子树

 

  • 二叉树的五种基本形态
    • 空二叉树
    • 只有一个根结点
    • 根节点只有左子树
    • 根节点只有右子树
    • 根节点只有左子树和右子树

斜树

  • 左斜树,所有结点都只有左子树
  • 右斜树,相反
    59df2c3acf5be40750000010

满二叉树

  • 一颗二叉树的所有分支结点都有左右子树,并且所有叶子结点都在最下面一层
  • 同样深度二叉树中,满二叉树结点最多
  • k为深度,则结点总数为2**k-1
  • 如下图,深度为4的15个结点的满二叉树
    59df2d42cf5be40750000012

完全二叉树Complete Binary Tree

  • 除了最后一层的所有的结点都集中在最左边,其他层都是满的
  • 完全二叉树有满二叉树引出
  • 区别在于他们的最后一层,完全二叉树最后一层的结点可以不满

59df2efccf5be40750000013

59df2f1ccf5be40750000015


二叉树的性质

59df2f4ecf5be40750000016

1.在二叉树的第i层上最多有2**(i-1)个结点

2.深度为 k 的二叉树,最多有 2**k-1 个结点

3.对任何一颗二叉树,如果其终端结点数为n0,度数为2的结点数为n3,则有n0 = n2 + 1

  • 换句话说,就是叶子结点数 -1 就等于度数为2 的结点数
  • 证明
    59df38cacf5be40750000019

4.其他性质

  • 高度为k的二叉树,至少有k个结点
  • 含有n个的结点的二叉树的高度之多为n,最小为 math.ceil(log2 (n+1))

5.具有n个结点的完全二叉树的深度为 int(log 2 n) + 1或者math.ceil(log2 (n+1))

6.如果有一颗n个结点的完全二叉树,结点按照层序编号,如下图
59df3bbccf5be4075000001a

  • 如果i = 1,则结点i是二叉树的根
  • i > 1,双亲是int(i/2),这是向下取整
  • 双亲结点是 i, 左孩子结点就是 2i, 右孩子结点就是 2i+1
  • 2i > n,则结点 i 无左孩子,即结点i为叶子结点;否则其左孩子结点存在,编号为2i
  • 2i+1 > n,则结点 i 无右孩子;这里不能说明结点i没有左孩子。否则其右孩子结点存在,编号为2i+1

本文来自投稿,不代表Linux运维部落立场,如若转载,请注明出处:http://www.178linux.com/87842

(1)
nolannolan
上一篇 2017-10-16 13:47
下一篇 2017-10-16

相关推荐

  • 使用NFS和Samba文件服务搭建博客站点

    使用NFS和Samba文件服务搭建博客站点 实验目的:分别使用NFS和Smaba文件服务实现wordpress 实验要求: (1) server导出/data/application/web,在目录中提供wordpress; (2) client挂载nfs server导出的文件系统至/var/www/html;(3) 客户端1(lamp),部署w…

    2017-04-30
  • shell脚本之条件测试

    组合条件测试:在多个条件间实现逻辑运算     与:[ condition1 -a condition2 ]、condition1 && condition2     或:[ condition…

    Linux干货 2015-08-24
  • LVS –负载均衡基础

    一 负载均衡的五种解决方案 1 http重定向 HTTP重定向就是应用层的请求转发。用户的请求其实已经到了http重定向负载均衡服务器,服务器根据算法要求用户重定向,用户收到重定向请求后,再次请求真正的集群。 优点:简单 缺点:性能较差 2 DNS域名解析负载均衡 DNS域名解析负载均衡就是在用户请求DNS服务器,获取域名对应的IP地址时,DNS根据服务器直…

    Linux干货 2017-06-22
  • Linux下搭建路由器

    客户端1:CentOS6.9 客户端2:CentOS7.3 路由器:router1(CentOS7.3)、router2(CentOS7.3) r router3(CentOS7.3) 1 准备工作 为了避免干扰,最好建立独立的网络。 打开VMvare的虚拟网络编辑器,点击添加网络按钮,添加VMnet11并且将左下角使用“本地DHCP服务将IP地址分配给虚拟…

    Linux干货 2017-08-20
  • PXE批量部署linux操作系统

       前言    在实际生产环境中,有时候我们会碰到为几十上百甚至上千台服务器安装Linux操作系统的需求,如果我们还是常规的去使用移动介质逐台安装,显然是一件低效又令人抓狂的事情,那要安装到何年何月啊?这对于我们追求高逼格形象的技术人员来讲当然是不可以接受的,为此,pxe模式批量部署系统应运而生。   &n…

    Linux干货 2015-05-23
  • Linux之旅1

    Linux之旅1  一、描述计算机的组成及其功能 计算机的组成: 1、计算机主要由:CPU(控制器、运算器)、存储器、输入设备、和输出设备(输入设备、和输出设备又称为I/O设备)四部分组成; 计算机个组成部分的功能: CPU:主要有控制器和运算器组成; 控制器:控制器是整个计算机的中枢神经;其功能是对程序规定的控制信息进行解释,根据其要求进行控制,…

    2016-09-12