二叉树的基本概念

1. 二叉树的基本概念

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：(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. 树的结点无左、右之分，而二叉树的结点有左、右之分。

2. 二叉树的定义

二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

3. 二叉树的定义

二叉树（Binary Tree）是n（n>=0）个数据元素的有限集合，该集合可以为空（空二叉树），也可以由一个称为根（root）的元素及两个不相交的，被分别称为左子树和右子树的二叉树组成。
如下图中含有7个结点，其中A是根节点，左子树TL由{B，D，E}构成，右子树TR由{C，F，G}构成；而左子树TL中B是根结点，左子树是{D}，右子树是{E}。


右子树TR中，C是根结点，左子树为空，右子树为{F，G}；以此类推。由上述可以看出在二叉树中用到了递归的概念。即用二叉树来定义二叉树。
二叉树的性质
1、一颗非空二叉树的第i层上最多有2^（i-1）个结点（i>=1）。
2、一颗深度为k的二叉树中，最多有2^k-1个结点。
3、对于一颗非空二叉树，如果叶结点数为n0，度数为2的结点数为n2，则有n0=n2+1。
4、具有n个结点的完全二叉树的深度为 |lbn|+1。
5、对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中所有结点从1开始编号，则对于任意序号结点来说，有：
①如果i>1，则序号i的结点的双亲结点序号为i/2；如果i=1，则此时结点为根结点，无双亲结点。②如果2in，则序号为i的结点无左孩子。③如果2i+1n,则序号为i的结点无右孩子。

4. 二叉树的定义

 　　二叉树是树形结构的一个重要类型 许多实际问题抽象出来的数据结构往往是二叉树的形式 即使是一般的树也能简单地转换为二叉树 而且二叉树的存储结构及其算法都较为简单 因此二叉树显得特别重要 
   二叉树的定义 
    二叉树的递归定义 　　二叉树(BinaryTree)是n(n≥ )个结点的有限集 它或者是空集(n= ) 或者由一个根结点及两棵互不相交的 分别称作这个根的左子树和右子树的二叉树组成 
    ．二叉树的五种基本形态 　　　二叉树可以是空集 根可以有空的左子树或右子树 或者左 右子树皆为空 　　二叉树的五种基本形态如下图所示 　   ．二叉树不是树的特例  （ ）二叉树与无序树不同 　　　二叉树中 每个结点最多只能有两棵子树 并且有左右之分 　　二叉树并非是树的特殊情形 它们是两种不同的数据结构 
  lishixinzhi/Article/program/sjjg/201311/23572 
   
   

5. 二叉树的基本概念？

楼主你好，因技术有限，所以在网上找了一些相关的资料，希望可以帮助到你。树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
二*树的特点：（1）非空二*树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
二*树的基本性质：
（1）在二*树的第k层上，最多有2k-1(k≥1)个结点；
（2）深度为m的二*树最多有2m-1个结点；
（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
（4）具有n个结点的二*树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；
（5）具有n个结点的完全二*树的深度为[log2n]+1；
（6）设完全二*树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，….n给结点进行编号（k=1,2….n），有以下结论：
①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT(k/2)；
②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（也无右子结点）；
③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
满二*树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二*树有2m-1个结点。
完全二*树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
二*树存储结构采用链式存储结构，对于满二*树与完全二*树可以按层序进行顺序存储。
二*树的遍历：
（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；
（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。
相关请访问 http://jinyichun1566.blog.163.com

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. 树和二叉树

 树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并且具有层次关系的结构。
   树：是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 个头指针用顺序表存储，数组元素存储：
   孩子链表表示法的类型定义，如下：
   在  孩子链表表示法  的基础上，在用一维数组顺序存储树中的各结点，数组元素存储：
   双亲孩子表示法的类型定义，如下：

8. 二叉树的基本概念

结点的度：结点拥有的子树的数目
  
 叶子结点：度为0的结点
  
 分支结点：度不为0的结点
  
 树的度：树中结点的最大的度
  
 层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1
  
 树的高度：树中结点的最大层次
  
 森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。
  
 二、二叉树
  
 二叉树的定义
  
 二叉树是每个结点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
  
 2、二叉树的性质
  
 性质1：二叉树第i层上的结点数目最多为2i-1(i>=1)
  
 性质2：深度为k的二叉树至多有2k-1个结点（k>=1）
  
 性质3：包含n个结点的二叉树的高度至少为(log2n)+1
  
 性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
  
 3、性质4的证明
  
 性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
  
 证明：因为二叉树中所有结点的度数均不大于2，不妨设n0表示度为0的结点个数，n1表示度为1的结点个数，n2表示度为2的结点个数。三类结点加起来为总结点个数，于是便可得到：n=n0+n1+n2 (1)
  
 由度之间的关系可得第二个等式：n=n0*0+n1*1+n2*2+1即n=n1+2n2+1 (2)
  
 将（1）（2）组合在一起可得到n0=n2+1
  
 三、满二叉树、完全二叉树和二叉查找树
  
 1、满二叉树
  
 
  
  
 定义：高度为h，并且由2h-1个结点组成的二叉树，称为满二叉树
  
 2、完全二叉树
  
 定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。
  
 特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。
  
 面试题：如果一个完全二叉树的结点总数为768个，求叶子结点的个数。
  
 由二叉树的性质知：n0=n2+1，将之带入768=n0+n1+n2中得：768=n1+2n2+1，因为完全二叉树度为1的结点个数要么为0，要么为1，那么就把n1=0或者1都代入公式中，很容易发现n1=1才符合条件。所以算出来n2=383，所以叶子结点个数n0=n2+1=384。
  
 总结规律：如果一棵完全二叉树的结点总数为n，那么叶子结点等于n/2（当n为偶数时）或者(n+1)/2（当n为奇数时）
  
 3、二叉查找树
  
 定义：二叉查找树又被称为二叉搜索树。设x为二叉查找树中的一个结点，x结点包含关键字key，结点x的key值计为key[x]。如果y是x的左子树中的一个结点，则key[y]=key[x]
  
 二叉查找树中：
  
  
 
  
  
 （1）若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  
 （2）任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
  
 （3）任意结点的左、右子树也分别为二叉查找树。
  
 （4）没有键值相等的结点