二叉树定义和性质

简介

定义

二叉树(Binary Tree)是一个连通的无环图,并且每一个顶点的度最大为2。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。二叉树是顺序树的一种。

性质

  1. 在二叉树的第i层上至多有$2^{i - 1}$个结点。
  2. 下一层的结点数最多是上一层结点数的两倍。
  3. 深度为k的二叉树至多有$2^{k}-1$个结点。
  4. 对于任何二叉树,若2度的结点数有$n_2$个,则叶子数(度为0)$n_0$必定为$n_2+1$(即$n_0=n_2+1$)。
  5. 设$n$为结点总数,$n_0$为叶节点数,$n_1$为1度结点数,$n_2$为2度结点数,则分支数($B$)为:$B = n_1 + 2n_2$或$B=n-1$。

满二叉树

定义

深度为$k$且含有$2^k-1$个结点的二叉树。

特点

  1. 每一层上的结点数都是最大结点数。
  2. 每一层的结点数都具有最大值$2^i-1$。

图示

                    A
                  /   \
                 B     C
                / \   / \
               D   E F   G

完全二叉树

定义

深度为$k$的,有$n$个结点的二叉树,当且仅当其每一个结点都与深度为$k$的满二叉树中(自上而下,从左往右)编号从1至$n$的结点一一对应。

判断方法

看着树的图示,心中默默给每个结点按照满二叉树的结构逐层顺序编号,如果编号出现空档,则说明不是完全二叉树(非完全二叉树);如果不出现空档,就是完全二叉树。

特点

  1. 叶结点只能出现在最下两层。
  2. 最下层的叶结点一定集中在左部连续位置。
  3. 倒数第二层若有叶结点,一定在右部连续位置。
  4. 若结点度为1,则该结点只有左孩子(既不存在只有右孩子的情况)。
  5. 同样结点数的二叉树,完全二叉树的深度最小。

性质

  1. 具有$n$个结点的完全二叉树的深度必为$[log_2n] + 1$($[n]表示对n进行向下取整$)。
  2. 对于完全二叉树,若从上至下,从左至右编号,则编号为i的结点,其中左孩子编号必为$2i$,其右孩子编号必为$2i+1$;其双亲的编号必为$[i/2]$。

图示

                    A
                  /   \
                 B     C
                / \   / \
               D   E F   G  

                    i/2
                  /     \
                 i       i+1
               /   \    /   \
              2i  2i+1 2i+2  2i+3                     
手机上阅读

本文由 giao创作, 采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文地址:《二叉树定义和性质》

 最后一次更新于2019-03-15

0 条评论

添加新评论

Markdown is supported.