树的定义

  1. 树是一个包含n(n>0)个结点的有穷集合K,且在K中定义了一个关系N,N满足以下条件:
    1. 有且仅有一个结点K0,他对于关系N来说没有前驱,称K0为树的根结点,简称为根(root)
    2. 除K0外,K中的每个结点,对于关系N来说有且仅有一个前驱
    3. K中各结点,对关系N来说可以有m个后继(m>=0)

树的特点

  1. 每个结点有零个或多个子结点

  2. 没有父节点的结点称为根节点

  3. 每一个非根结点有且只有一个父节点

  4. 除了根结点外,每个子结点可以分为多个不相交的子树

名词解释

  1. 双亲

     一个有子树的结点称为子树根的双亲
    
  2. 孩子

     子树的根称为双亲结点的孩子
    
  3. 兄弟

     有相同双亲的结点互为兄弟
    
  4. 后裔

     一个结点的所有子树上的任何结点都是该结点的后裔
    
  5. 祖先

     从根结点到某个结点的路径上的所有结点都是该结点的祖先
    
  6. 结点的度

     结点拥有子树的数目
    
  7. 叶子结点

     结点的度为0的结点
    
  8. 分支结点

     结点的度不为0的结点
    
  9. 树的度

     树中结点的最大的度
    
  10. 层次

     根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1
    
  11. 树的高度

     树中结点的最大层次
    
  12. 森林

     0个或多个不相交的树组成,对森林加上一个根,森林即成为树,删去根,树即成为森林
    

二叉树

  1. 二叉树

     二叉树是每个结点最多有两个子树的树结构,它有五种基本形态
         1. 空二叉树
         2. 根和空左右子树
         3. 根和左子树
         4. 根和右子树
         5. 根和左右子树
    
  2. 二叉树性质

    1. 二叉树第n层上的结点数最多为2^(n-1)个(n>=1)

    2. 深度为n的二叉树至多有(2^n)-1个结点(n>=1)

    3. 包含n个结点的二叉树的高度至少为(log2n)+1

    4. 在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0 = n2 + 1

  3. 证明性质4

    1. 二叉树中所有节点的个数n等于度为0的节点个数n0 加度为1的节点个数n1 加度为2的节点个数n2 n = n0 + n1 + n2

    2. 二叉树中所有节点的个数n等于度为0的节点个数n0乘以1 加度为1的节点个数n1乘以1 加度为2的节点个数n2乘以2 加上根节点 n = n0 0 + n1 1 + n2 * 2 + 1

    3. 由前两式可得n0 = n2 + 1

  4. 满二叉树

    1. 高度为n且节点数为(2^n)-1的二叉树称为满二叉树
  5. 完全二叉树

    1. 一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下层的叶结点集中在靠左的若干位置上,这样的二叉树称为完全二叉树

    2. 叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树

  6. 二叉查找树

    1. 二叉查找树又被称为二叉搜索树。设x为二叉查找树中的一个结点,x结点包含关键字key,结点x的key值计为key[x],如果y是x的左子树中的一个结点,则key[y]<=key[x];如果y是x的右子树的一个结点,则key[y]>=key[x]
  7. 二叉查找树特点

    1. 若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值

    2. 任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值

    3. 任意结点的左、右子树也分别为二叉查找树

    4. 没有键值相等的结点

  8. 二叉树遍历

    1. 假设二叉树为

       A—C—F
       |
       B—E
       |
       D
      
    2. 前序遍历(根左右)

       ABDECF
      
    3. 中序遍历(左根右)

       DBEACF
      
    4. 后序遍历(左右根)

       DEBFCA
      
@耿志环 2012-∞ 冀ICP备17033181号, powered by Gitbook修订: 2018-08-21 15:42:53

results matching ""

    No results matching ""