数据结构:树和二叉树定义和术语-演道网

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

【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm

根据二叉树的前序数组和中序序遍历数组生成二叉树 http://www.linuxidc.com/Linux/2016-09/135514.htm

后序遍历求解判断一颗二叉树是否为平衡二叉树 http://www.linuxidc.com/Linux/2016-08/134054.htm

判断二叉树是否为完全二叉树 http://www.linuxidc.com/Linux/2016-08/134050.htm

求二叉树中两个节点的最远距离 http://www.linuxidc.com/Linux/2016-08/134049.htm

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注