二叉树的作用

1. 二叉树的作用

树,连通但没有回路的图
二叉树是一类非常重要的树形结构，它可以递归地定义如下：

二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。若用n,n1和n2分别表示T，u(1)和u(2)的结点数，则有n=1+n1+n2 。u(1)和u(2)有时分别称为T的第一和第二子树。

2. 二叉树的介绍

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

3. 树与二叉树的区别

一、性质不同
树：树是一种数据结构。
二叉树：二叉树是每个结点最多有两个子树的一种树结构。
二、结点不同
树：树的每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点。
二叉树：每个结点最多有两个子树。

三、种类不同
树：树的种类包括无序树、有序树、二叉树和霍夫曼树等。
二叉树：二叉树的种类包括完全二叉树、满二叉树和平衡二叉树。

参考资料来源：百度百科-树
                        百度百科-二叉树

4. 树与二叉树的区别

一、性质不同
树：树是一种数据结构。
二叉树：二叉树是每个结点最多有两个子树的一种树结构。
二、结点不同
树：树的每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点。
二叉树：每个结点最多有两个子树。

三、种类不同
树：树的种类包括无序树、有序树、二叉树和霍夫曼树等。
二叉树：二叉树的种类包括完全二叉树、满二叉树和平衡二叉树。
参考资料来源：百度百科-树
 
 
 
 
 
 
 
 
 
 
 
  百度百科-二叉树

5. 二叉树的基本概念

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：(1)空二叉树——如图(a)；(2)只有一个根结点的二叉树——如图(b)；(3)只有左子树——如图(c)；(4)只有右子树——如图(d)；(5)完全二叉树——如图(e)。注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。  (1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。  树的结点：包含一个数据元素及若干指向子树的分支；孩子结点：结点的子树的根称为该结点的孩子；双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；树的深度：树中最大的结点层结点的度：结点子树的个数树的度： 树中最大的结点度。叶子结点：也叫终端结点，是度为 0 的结点；分枝结点：度不为0的结点；有序树：子树有序的树，如：家族树；无序树：不考虑子树的顺序；  (1) 在非空二叉树中，第i层的结点总数不超过 , i>=1；(2) 深度为h的二叉树最多有 个结点(h>=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4) 具有n个结点的完全二叉树的深度为(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则 如果I>1，则其父结点的编号为I/2；如果2*IN，则无左儿子；如果2*I+1N，则无右儿子。(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i  二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；2. 树的结点无左、右之分，而二叉树的结点有左、右之分。

6. 二叉树的基本概念

1、树中每一个节点最多只能有两棵树，即每个节点最多为2
   2、二叉树的子树有左右之分，即左子树与右子树,次序不能颠倒 也就是可以设为: 左子树=0 右子树=1
   3、二叉树即使只有一个子树时，也要区分左子树还是右子树
  
 满二叉树是一种特殊的二叉树,指所有分支节点都存在左右子树，且所有叶子节点都在同一层上。
   可以理解为是一个二进制树 由祖节点开始分支 第一节点只有一棵树 设为: 0
   第二节点开始 分支为 0 1 两颗树 且第二节点最多为两颗树
   第三节点则根据第二节点的两颗树进行分支 且每个分支根据节点特征最多为2 则 第三节点最多存在 四颗树
   且这四颗树中 两颗树存在于 第二节点的0树 两颗树存在于第二节点的1树
   节点依次类推 1、2、4、8、16、32、64
  
 若设二叉树的深度为h，除第h层外，其它层 (1~h -1)的节点都为最大树
   例: 深度为4 则深度在4之前所有节点全部存在
   根据二进制算 则整棵树的节点最少为 1+2+4颗树 而第4层则为+2+4+1 ～ 1+2+4+8 颗树之间
   完全二叉树的特点为:
   1、叶子节点可以在最后一层或倒数第二层
   2、最后一层的叶子节点一定集中在左部连续位置
   3、完全二叉树严格按照层序编号
   4、若一个节点为叶子节点，那么编号比其大的节点均为叶子节点
  
 1、在非空的二叉树的i层上,至多有2的i-1次方个节点(i >= 1)
   2、在深度为h的二叉树上最多有2的h-1次方个节点(h >= 1)
   3、对于任何一颗非空的二叉树，如果叶子节点数为n0,深度数为2的节点个数为n2,则 n0 = n2 + 1
  
 1、具有n个节点的完全二叉树的深度为log2n + 1
   2、如果有一颗n个节点的完全二叉树的节点按层次序号编号，对其任意一层的节点i,(1 >= i >= n) 有一下三种可能
   2.1 如果i = 1 则节点是二叉树的根,无双亲,如果i > 1,则其双亲节点为 i/2
   2.2 如果2i > n 那么节点i没有左孩子,否则左孩子为2i
   2.3 如果2i+1 > n 那么节点i没有右孩子,否则右孩子为2i + 1

7. 二叉树的特点总结

非空二叉树的特点：
  
 1、每一层的结点个数: 最多是  （i>=1） 
  
 2、高度是h的二叉树总结点个数：最多   
  
 3、设度为0的结点个数是n0，度为2的结点个数是n2，则有 n0 = n2 + 1
  
 n = n0 + n1 + n2
  
 边数 = n1 + 2*n2 = n - 1 = n0 + n1 + n2 - 1
  
 n1 + 2*n2 = n0 + n1 + n2 -1
  
 n0 = n2 + 1
  
 1、真二叉树
  
 定义：所有结点的度都是0或2的二叉树
  
 2、满二叉树
  
 定义：满足所有叶子结点都在最后一层的真二叉树叫满二叉树
  
 性质：
  
 a.同样高度的二叉树中，满二叉树的叶子结点数最多，总结点数也是最多的
  
 b.满二叉树一定是真二叉树，真二叉树不一定是慢二叉树
  
 c.高度为h(>=1)的满二叉树的第i层节点数是 2的(i-1)次方，总结点数是2的h次方-1
  
 3、完全二叉树
  
 定义1：叶子结点只会出现在最后2层，且最后一层的叶子结点靠左对齐
  
 定义2：将满二叉树的叶子结点从右向左依次移除x个，得到完全二叉树
  
 性质：
  
 a.满二叉树一定是完全二叉树
  
 b.完全二叉树度为1的结点，最多有一个，且一定是左子树
  
 c. h = ceiling(log2n)

8. 树和二叉树

 树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并且具有层次关系的结构。
   树：是n(n>=0)个结点的有限集，满足：
    结点 ：有一个数据元素及若干指向其它结点的分支所组成。
    度 ： 结点的度 ：所拥有的子树的数目； 树的度 ：树中所有结点的度的最大值。
    叶子（终端结点） ：度为 0 的结点。
    非终端结点 ：度不会 0 的结点。
    孩子（子结点） ：结点的子树的根称为该结点的孩子。
    双亲（父结点） ：一个结点称为该结点所有子树根的双亲。
    祖先 ：结点祖先指根到此节点的一条路径上的所有结点。
    子孙 ：从某节点到叶节点的分支上的所有结点称为该结点的子孙。
    兄弟 ：同一双亲的孩子之间互称兄弟。（父结点相同的点）
    结点的层次 ：从根开始算起，根的层次为1，其余结点的层次为双亲的层次加1。
    堂兄弟 ：其双亲在同一层的结点。
    树的深度（高度） ：一个树中所有结点层次数的最大值。
    有序树 ：若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。
    无序树 ：若树中各结点的子树是无次序的，可以互换，称为无序树。
    森林 ：是 m(m>=0) 棵树的集合。
   二叉树是 n(n>=0) 各结点的有限集合，它或为空（n=0），或是由一个  根  及  两棵  互不相交的  左子树  和  右子树  组成，其左子树和右子树也是二叉树。
   二叉树的  特点 ：
   二叉树和树的比较：
    完全二叉树 ：深度为 k 的二叉树中，k-1 层结点数是满的   ，k 层结点是左连续的（即结点编号是连续的）。
    满二叉树 ：深度为 k(k>=1) 且有    个结点的二叉树。满二叉树是完全二叉树的特例。
   在二叉树的第 i(i>=1) 上至多有    个结点；
   深度为 k(k>=1) 的二叉树至多有    个结点；
   对任何一棵二叉树，如果其叶结点数为   ，度为2的结点数为   ，有：  ；
   含有 n 个结点的  完全二叉树  的深度为   ；
   如果将一棵有 n 个结点的  完全二叉树  按层编号（从上到下，从左到右进行编号），则对任一编号为 i(1 <= i <= n) 的结点 A 有：
   它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，可用编号的方法。
   二叉树的顺序存储结构 -- 即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中  编号为i  的结点存储在数组中  下标为i  的分量中。
   该方法称为 “ 以编号为地址 ” 策略。
   从树根起，从上层至下层，每层从左至右的给所有结点编号， 缺点  是：
   对于  完全二叉树  采用此方法，则：
   对于  一般二叉树  采用此方法，首先需要用某种方法将其转换成完全二叉树，为此可增设若干个  虚拟结点 ，则：
                                            遍历二叉树 ：是指按  某种次序访问  二叉树上的所有结点，使每个结点被  访问一次  且仅被访问一次。
    先序遍历，DLR ：根 -> 左子树 -> 右子树
    中序遍历，LDR ：左子树 -> 根 -> 右子树
    后序遍历，LRD ：左子树 -> 右子树 -> 根
                                            二叉树的层次遍历 ：从二叉树的  根结点  的这一层开始， 逐层向下  遍历，在每一层上按  从左到右  的顺序对结点逐个访问。
                                           以一组连续空间存储树的结点，即一个一个数组构成，数组每个分量包含两个域：
   双亲链表的类型定义，如下：
    孩子链表 ：树中每个结点的孩子串成一单链表。
   n 个结点 - n 个孩子链表
    表头数组 ：n 个头指针用顺序表存储，数组元素存储：
   孩子链表表示法的类型定义，如下：
   在  孩子链表表示法  的基础上，在用一维数组顺序存储树中的各结点，数组元素存储：
   双亲孩子表示法的类型定义，如下：