数据结构:树和二叉树定义和术语

1、树的对象
 具有相同特性的数据元素的集合
2、关系
 如果没有对象叫做空树
 否则:
 在存在唯一的成为根的数据元素root
当元素个数大于1的时候,其他节点可以
 分为互不相交的树,成为根root的子树
        a
  b      c    d
 e f    g   
        i  j 
   
 b c d 叫做a为root节点的子树
e f 叫做以b为root节点的子树
 以此类推
3、相关术语
 结点:数据元素+若干指向子树的分支
      如上数据元素a+指向子树b c d的指针叫做结点
 结点的度:分支的个数 比如a的度就为3
树的度:所有结点的度的最大值
 叶子结点:度为0的结点
 分支结点:度大约0的结点,也就是叶子结点以外的
          特殊的就是root根结点
 从根到结点的路径:从根到结点所经历的分支和结点构成


 孩子结点:子树的根对于树的根叫做孩子结点
 双亲结点:树的根对于子树的根叫做双亲结点
 兄弟结点:有相同根的子树叫做兄弟结点
 祖先节点:从根到结点之间的全部节点叫做祖先节点
 子孙节点:一个根下的所有的节点叫做子孙节点


 结点的层次:角色根结点的层次为1,第L层的节点的子树
            根结点的层次是L+1层
树的深度:树中叶子节点所在的最大层次
 如上例子:第3层的i的层次为3+1=4层,整个树的深度为4


森林:是多棵互不相交的树的集合,从定义可以看出,如果一棵树去掉root根结点明显他
      就是一个森林,如果一个森林加上一个root结点那么就是一棵树


 有向树:
1、有确定的根
2、树根和子树根之间为有向关系


 一般讨论无序树,同一个层次之间无序


 和线性表的区别:
 第一个元素无前驱 根结点无前驱
 最后一个数据元素 多个叶子结点
 无后继          无后继
 其他数据元素    树中其他节点
 一个前驱,      一个前驱、多个后继
 一个后继


 由于树的不确定性和复杂性我们一般讨论二叉树
 二叉树
 定义:
 二叉树或为空树;或者由一个根结点加上
 两棵分别称为左子树和右子树的、互不相交的二叉树组成
 并且一个根结点有且只有两个子树为左子树和右子树


      A
  B            E
 C            F
  D            G
              H  K
左子树    右子树


 二叉树2种形态
1、空树
2、只有根结点的树
3、左子树非空右子树空
4、左子树空右子树非空
5、都不为空


 对于3和4不同二叉树必须明确是左子树为空还是右子树为空,虽然
 只有一个子树但是必须明确是左子树还是右子树


 重要特性:
1、在二叉树的第i层上最多有2^(i-1)个结点(i>=1)
 2、深度为h的树结点树最多为2^h-1 
 3、对于任何一棵二叉树,如果他含有n0个叶子节点,
  n2个度为2的节点,这必然存在关系n0=n2+1
注:二叉树有3种节点:n0代表度为0的节点
    n1代表度为1的节点
                    n2代表度为2的节点
                    n0+n1+n2=n 总的结点
                    b为分支数量
                    n=b+1=1+n1+2n2
                      及:1+n1+2n2=n0+n1+n2
                      及:n0=n2+1
满二叉树:深度为k的树含有2^k-1个结点,其实就是在一棵树中
          不包含度为1的节点的树,只有深度为k的层末尾节点
          才为叶子结点
 完全二叉树:如果给满二叉树编号,按照编号一一对应的一棵树
            及知道结点个数就知道树的结构,且如果无左孩子
            结点那么它就是叶子结点
 如:
        1
    2        3
  4  5    6  7
为满二叉树
        1
    2        3
  4  5    6 
为完全二叉树
        1
    2        3
      4    5
不为完全二叉树

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/df49e77cc23c0a2f149da34414719fca.html