欢迎观临
路漫漫其修远兮,吾将上下而求索

二叉树概念基础

1 树的介绍

1.1 树的定义

树是一种数据结构,定义树的一种自然方式是递归法。一颗树是由一些节点组成的具有层次关系的集合。若集合为空集,则称为空树;若不是空集,则树由一个称作 根(root) 的节点r与零个或多个非空子树组成;每个子树的根都与根节点r由一条有向 边(edge) 相连接。子树的根称为根节点r的“儿子(child)”,而根节点r称为子树的根的“父亲(parent)”。

树的示意图

1.2 树的基本术语

  • 叶子节点(leaf node):度为零的结点。
  • 分支结点(branch node):度不为零的结点。
  • 结点的度(degree of node):结点拥有的子树的数目。
  • 树的度(degree of tree):树中结点的最大的度。
  • 节点的层次(level of node):根结点的层次为1,其余结点的层次等于父结点的层次加1。
  • 路径(path):节点n1,n2,…,nk的一个序列,其中对于1<=i<=k,节点ni是ni+1的的父亲,则该序列成为节点n1到nk的路径。
  • 路径的长(length of path):路径上边的条数。
  • 节点的深度(depth of node):从根节点到节点ni的路径的长。因此,根节点深度为0。
  • 树的深度(depth of tree):最深的树叶的深度。
  • 节点的高度(height of node):从节点ni到一片叶子的最长路径长。因此,叶子节点的高度为0。
  • 树的高度(height of tree):根节点的高度。因此,一棵树的深度和高度总是相等。

2 二叉树介绍

2.1 二叉树的定义

二叉树是每个节点最多有两个子树的树。从定义可知,二叉树是度等于2的树。
二叉树有五种基本形态:空集;仅有根;仅有根和左子树;仅有根右子树;有根和左右子树。
二叉树的五种形态

2.2 二叉树的性质

二叉树有以下几个性质:

  1. 二叉树第i层上的结点数目最多为 2i-1 (i≥1)。
  2. 深度为k的二叉树至多有2k-1个结点(k≥1)。
  3. 包含n个结点的二叉树的高度至少为log2 (n+1)。
  4. 在任意一棵二叉树中,若叶子结点的个数为n0,度为2的结点数为n2,则n0=n2+1。

2.3 满二叉树

定义:高度为h,并且由2h –1个结点的二叉树,被称为满二叉树。即节点数达到了二叉树能够拥有的最大数的二叉树。
满二叉树

2.4 完全二叉树

定义:深度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,且第h层所有的结点都连续集中在最左边,被称为完全二叉树。
完全二叉树是对满二叉树的补充,所有满二叉树都是完全二叉树。
完全二叉树

赞(0) 打赏
未经允许不得转载:云海鹰影博客 » 二叉树概念基础
分享到: 更多 (0)

欢迎留言 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏