全部答案

2018-05-15 04:36:26

•   二叉树的概念  
  二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。  
  1、二叉树的递归定义和基本形态  
  二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：  
  ⑴有一个特定的结点称为根；  
  ⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；  
  由上述定义可以看出，二叉树和树是两个不同的概念  
  ⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；  
  ⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。
    我们称二叉树中结点的左后件为左儿子，右后件为右儿子。  
  2、二叉树的两个特殊形态  
  ⑴满二叉树： 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。可以验证具有n个叶结点的满二叉树共有2n-1个结点。
      
  ⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树  
  3、二叉树的三个主要性质  
  性质1：在二叉树的第i（≥1）层上，最多有2i-1个 结点  
  证明：我们采用数学归纳法证明：当i=1时只有一个根结点，即2i-1=20=1，结论成立。
    假设第k(i=k)层上最多有2k-1个结点，考虑i=k 1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点，因此在第k 1层上最多有2．2k-1=2(k 1)-1=2i，结论成立。综上所述，性质1成立。  
  性质2：在深度为k(k≥1)的二叉树中最多有2k-1个 结点。
      
  证明：由性质1，在二叉树第i层上最多有2i-1个结点，显然，第1层¨第k层的最多结点数为 个结点。证毕。  
  性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。  
  证明：设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0 n1 n2 （1）  
  由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。
    设 b为二叉树的前件个数，n=b 1（2）  
  所有这些前件同时又为度为1和度为2的结点的后件。因此又有b=n1 2n2 (3)  
  我们将（3）代入（2）得出n=n1 2n2 1 (4)  
  比较（1）和（4），得出n0=n2 1,即叶子数比度为2的结点数多1  
  4、普通有序树转换成二叉树  
  普通树为有序树T，将其转化成二叉树T’的规则如下：  
  ⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；  
  ⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；  
  ⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；  
  由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。
      
  5、二叉树的存储结构  
  将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括  
  ⑴一个数据域（data）；  
  ⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。
      
  满二叉树和完全二叉树一般采用顺序存储结构  
  对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。
    由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：  
  ⑴值域： data  
  ⑵左指针域： lch  
  ⑶右指针域： rch  
  这种链表也称为二叉链表。
    二叉链表头指针bt指向二叉树的根结点  
  6、二叉树的遍历  
  二叉树遍历的定义：按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。  
  二叉树遍历的顺序：如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。
    若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。  
  前序遍历的规则如下：  
  若二叉树为空，则退出。
    否则  
  ⑴访问处理根结点；  
  ⑵前序遍历左子树；  
  ⑶前序遍历右子树；  
  特点：由左而右逐条访问由根出发的树支 （回溯法的基础）  
  中序遍历的规则：  
  若二叉树为空，则退出；否则  
  ⑴中序遍历左子树；  
  ⑵访问处理根结点；  
  ⑶中序遍历右子树；  
  后序遍历的规则如下：  
  若二叉树为空，则退出；否则  
  ⑴后序遍历左子树；  
  ⑵后序遍历右子树；  
  ⑶访问处理根结点；  
  特点：可统计任一个结点为根的子树的情况（例如子树的权和，最优策略的选择（博弈数））。

  全部
  

  你***

  2018-05-15 04:36:26

  3 3 评论

  分享
  提交评论