首页 > 代码库 > 树与二叉树(一)

树与二叉树(一)

定义

树是n(n≥0)个结点的有限集,它或为空树(n=0)。或为非空树

非空树T满足下面条件:

(1) 有且仅有一个称为根的结点;

(2)除根结点以外的其余结点可分为m(m>0)个互补相交的有限集T1,T2,…Tm,当中每个集合本身又是一棵树,而且称为根的子树。

技术分享

                         空树

技术分享

                       一般的树

基本术语

根———即根结点(没有前驱)

叶子———即终端结点(没有后继)

森林———指m棵不相交的树的集合

有序树———结点各子树从左至右有序,不能互换

无序树———结点各子树可互换位置。

双亲———即上层的那个结点(直接前驱)

孩子———即下层结点的子树的根(直接后继)

兄弟———同一双亲下的同层结点(孩子之间互称为兄弟)

堂兄弟———即双亲位于同一层的结点(但并不是同一双亲)

祖先———即从根到该结点所经分支的全部结点

子孙———即该结点下层子树种的任一结点

结点———即树的数据元素

结点的度———结点挂接的子树数

结点的层次———从根到该结点的层数(根结点算第一层)

终端结点———即度为0的结点,即叶子

分支结点———即度不为0的结点(也称为内部结点)

树的度———全部结点度中的最大值

树的深度———指全部结点中最大的层数(或高度)


二叉树

二叉树是一种特殊的树结构,普通树若不转化成二叉树,则运算非常难实现

为什么要重点研究二叉树呢?

  • 二叉树的结构最简单,规律性最强

  • 全部的树都能转为唯一相应的二叉树,不失一般性。

定义:

每个节点至多有两个子树。

基本特点:

  • 结点的度小于等于2
  • 有序树(子树有序。不能颠倒)
    技术分享

                         二叉树的五种形态
    

二叉树的性质

性质1 : 一棵非空二叉树的第i层上最多有2^i-1个结点(i≥1)。

性质2 :若规定空树的深度为0,则深度为k的二叉树最多有(2^k)-1个结点

(k≥0)。

性质3: 具有n个结点的全然二叉树的深度k为log2n+1。

性质4 :对于一棵非空二叉树。假设度为0的结点数目为n0,度为2的结点数目为n2。则有n0= n2+1。

性质5 :对于具有n个结点的全然二叉树,假设依照从上到下和从左到右的顺序对全部结点从1開始编号,则对于序号为i的结点,有:

  1. 假设i>1,则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)。假设i=1,则该结点是根结点,无双亲结点。

  2. 假设2i≤n,则该结点的左孩子结点的序号为2i;若2i>n。则该结点无左孩子。

  3. 假设2i+1≤n。则该结点的右孩子结点的序号为2i+1。若2i+1>n,则该结点无右孩子。

满二叉树:一棵深度为k且有2k-1个结点的二叉树。

意思是树上挂满了结点)

技术分享

全然二叉树:深度为k的,有n个结点的二叉树,当且仅当其每个结点都与深度为k的满二叉树中编号从1至n的结点一一相应(意思是仅仅有最后一层叶子不满,且全部集中在左边)

技术分享

                    Unfinished, see the next
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

树与二叉树(一)