1. 首页
  2. IT资讯

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

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
不为完全二叉树

关于完全二叉树的特性:
1、具有n个结点的完全二叉树的深度为 [log2 n]+1 
   符号[]为不大于log2 n的最大整数
2、如果i=1,则结点i是二叉树的根,无双亲,如果i>1,
   这其双亲parent(i)结点为[i/2]
3、如果2i>n则结点i无左孩子,否则左孩子是节点2i
4、如果2i+1>n则结点无右孩子,否则其右孩子是节点2i+1

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7728585/viewspace-2125889/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183861.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code