【图解数据结构】 树

树的定义

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。 在任意一颗非空树中: (1)有且仅有一个特定的称为根(Root)的结点。 (2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2、.....、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。

下图就符合树的定义:

其中根结点A有两个子树:

需要注意的是虽然子树的个数没有限制,但是它们一定是互不交互的。下面的图明显不符合互不交互的原则,所以不是树。

树的结点

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)树的度是树内各结点度的最大值。

结点的层次从根开始定义起,根为第一层,根的孩子为第二层,以此类推。树的深度(Depth)或高度是树中结点的最大层次。

树的存储结构

二叉树

二叉树的定义

二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成(子树也为二叉树)。

二叉树的特点

  • 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点
  • 左子树和右子树是有顺序的,次序不能任意颠倒。
  • 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

二叉树五种基本形态

  1. 空二叉树
  2. 只有一个根结点
  3. 根结点只有左子树
  4. 根结点只有右子树
  5. 根结点既有左子树又有右子树

几种特殊的二叉树

斜树

左斜树:

右斜树:

满二叉树

满二叉树:

完全二叉树

完全二叉树:

二叉树的性质

二叉树性质1

性质1:在二叉树的第i层上至多有2i-1个结点(i>=1)

二叉树性质2

性质2:深度为k的二叉树至多有2k-1个结点(k>=1)

二叉树性质3

性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2+1。

一棵二叉树,除了终端结点(叶子结点),就是度为1或2的结点。假设n1度为1的结点数,则数T 的结点总数n=n0+n1+n2。我们再换个角度,看一下树T的连接线数,由于根结点只有分支出去,没有分支进入,所以连接线数为结点总数减去1。也就是n-1=n1+2n2,可推导出n0+n1+n2-1 = n1+2n2,继续推导可得n0 = n2+1。

二叉树性质4

性质4:具有n个结点的完全二叉树的深度为[log2n ] + 1([X]表示不大于X的最大整数)。

由性质2可知,满二叉树的结点个数为2k-1,可以推导出满二叉树的深度为k=log2(n + 1)。对于完全二叉树,它的叶子结点只会出现在最下面的两层,所以它的结点数一定少于等于同样深度的满二叉树的结点数2k-1,但是一定多于2k-1 -1。因为n是整数,所以2k-1 <= n < 2k,不等式两边取对数得到:k-1 <= log2n<k。因为k作为深度也是整数,因此 k="[log</k。因为k作为深度也是整数,因此>

二叉树性质5

性质5:如果对一颗有n个结点的完全二叉树(其深度为[log2n ] + 1)的结点按层序编号(从第1层到第[log2n ] + 1层,每层从左到右),对任一结点i(1<=i<=n)有:

  1. 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点[i/2]。
  2. 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点i。
  3. 如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。

结合下图很好理解:

二叉树的存储结构

二叉树顺序存储结构

^代表不存在的结点。

对于右斜树,顺序存储结构浪费存储空间:

二叉树的顺序存储结构缺点很明显:不能反应逻辑关系;对于特殊的二叉树(左斜树、右斜树),浪费存储空间。所以二叉树顺序存储结构一般只用于完全二叉树。

二叉链表

链表每个结点包含一个数据域和两个指针域:

其中data是数据域,lchild和rchild都是指针域,分别指向左孩子和右孩子。

二叉树的二叉链表结点结构定义:

/*二叉树的二叉链表结点结构定义*/
typedef struct BiNode
{
    char data;      /*结点数据*/
    struct BiNode *lchild, *rchild;     /*左右孩子指针*/
}BiNode,*BiTree;

原文发布于微信公众号 - 撸码那些事(lumanxs)

原文发表时间:2018-05-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

1966
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1505
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

2258
来自专栏F_Alex

数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)

前言:前面了解了树的概念和基本的存储结构类型及树的分类,而在树中应用最广泛的种类是二叉树

622
来自专栏Android相关

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

3153
来自专栏张俊红

数据结构—树与二叉树

之前谈到的线性表、栈和队列都是一对一的数据结构,但是现实中也存在很多一对多的数据结构,这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分:

983
来自专栏菩提树下的杨过

数据结构C#版笔记--树与二叉树

                图1 上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以...

2488
来自专栏mathor

二叉树的下一个结点&二叉树的上一个结点

 最笨的方法就是一直网上回溯,直到找到了头结点,然后从头结点开始重新中序遍历一次树,然后得到答案  还有一种比较巧妙的方法,先判断当前结点有没有右子树,如果有...

572
来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

59611
来自专栏Android相关

二叉查找树(Binary Search Tree)

在二叉搜索树b中查找x的过程为: 若b是空树,则搜索失败,否则: 若x等于b的根节点的数据域之值,则查找成功;否则: 若x小于b的根节点的数据域之值,则搜...

2403

扫码关注云+社区