二叉树
二叉树
石飞飞 发表于3个月前
二叉树
  • 发表于 3个月前
  • 阅读 18
  • 收藏 0
  • 点赞 0
  • 评论 0

华为云·免费上云实践>>>   

摘要: 主要了解二叉树的性质、存储结构以及遍历

【1】二叉树的定义

    二叉树是n(n>-1)个结点的有限集合,该集合或者为空(称空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。如下图所示就是一棵二叉树:

    1. 二叉树的特点:

  • 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点;
  • 左子树和右子树是有顺序的,次序不能变;即使树中某个结点只有一棵子树,也要区分左子树和右子树;

    2. 二叉树的型态:

  • 空二叉树;
  • 只有一个根结点;
  • 根结点只有左子树;
  • 根结点只有右子树;
  • 根结点既有左子树又有右子树;
  • 如果有三个结点的二叉树有几种型态,如下图所示:

    3. 特殊的二叉树:

  • 斜树:所有结点只有左子树的二叉树叫左斜树,所有结点只有右子树的二叉树叫右斜树;
  • 满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称之为满二叉树;如下图所示:
  • 从图中可以看出二叉树的特点:
    • 非叶子结点的度一定是2;
    • 在同样深度(树的结点最大层次就是树的深度)的二叉树中,满二叉树的结点数最多,叶子数最多;
  • 完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点;如下图所示:
  • 完全二叉树的特点:
    • 同样结点数的二叉树,完全二叉树的深度最小;

【2】二叉树性质

  • 在二叉树的第i层上最多有2^(i-1)个结点(i>0);
  • 深度为k的二叉树最多有 (2^k)-1个结点(k>0);
  • 对于任何一棵二叉树,如果叶子结点数是x,度为2的结点数是y,则x=y+1;
  • 具有n个结点的完全二叉树的深度为 log2(n)+1 ;推理逻辑:

【3】二叉树的存储结构:

    二叉链表法:二叉树每个结点最多有两个孩子,所以它设计一个数据域和两个指针域即可;

/**
 * 二叉树:二叉链表法
 */
public class BinaryNode<T> {

    T data;

    /*左孩子指针域*/
    BinaryNode<T> left;

    /*右孩子指针域*/
    BinaryNode<T> right;
}

    如下图所示:

   

 【4】二叉树的遍历

  • 前序遍历:若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树;如图所示:ABDGHCEIF
  • 中序遍历:若二叉树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后访问根结点,最后中序遍历右子树;如下图所示:GDHBAEICF
  • 后序遍历:若树为空,则空操作返回,否则从左到右先叶子结点的方式遍历访问左右子树,最后访问根结点;如下图所示:GHDBIEFCA

 

 

推荐博客文章:http://blog.csdn.net/javazejian/article/details/53727333

共有 人打赏支持
粉丝 0
博文 58
码字总数 36709
×
石飞飞
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: