• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

树的总结

开发技术 开发技术 7天前 6次浏览

树的特点:

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

2.每一个非根结点有且只有一个父结点;

3.没有父结点的结点称为根结点;

树的种类:

1.二叉树

  树的任意节点至多包含两棵子树;

  二叉树包含:完全二叉树,满二叉树,线索二叉树,平衡二叉树,二叉排序树,哈夫曼树;

 (1)完全二叉树:

  对于一颗二叉树,最多只有最下面两层的节点度数可以小于二,且最下面一层的叶子节点全在该树的左位置上,则其为完全二叉树;

 

树的总结

  (2)满二叉树:

  叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点。

  树的总结

  (3)线索二叉树:

    在二叉树的结点上加上线索的二叉树称为线索二叉树,对二叉树以某种遍历方式(如先序、中序、后序或层次等)进行遍历

    使其变为线索二叉树的过程称 为对二叉树进行线索化。

 (4)二叉排序树:

    每个节点的值都不相同;

    若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
    若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
    任意节点的左、右子树也分别为二叉排序树。
    

  (5)平衡二叉树:

    它的左右两个子树的高度差的绝对值不超过一,并且左右两个子树都是一棵平衡二叉树,而且平衡二叉树必定是二叉搜索树。

  (6)哈夫曼树:

   给定N个权值作为N个叶子节点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。

   哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

 2.有(无)序树:

  树的任意节点的子节点有(没有)顺序关系。

 3.B_树:

  一棵m阶B树是一棵平衡的m路搜索树。它满足下列性质:
  1.根结点至少有两个子女;

  2.每个非根节点所包含的孩子个数 j 满足:m/2 <= j<= m ;

  3.每个非根节点所包含的关键字个数 j 满足:m/2 – 1 <= j <=m – 1;树的总结

  4.B+树:

   1.每个分支节点最多有m个子树;

   2.根节点没有子树,或至少有两个子树;

   3.除根结点外,其他每个分支点至少有m/2个子树;

   4.有n个子树的节点有n个关键词

树的总结  
总结:

树的总结

 

  

 

 

 


程序员灯塔
转载请注明原文链接:树的总结
喜欢 (0)