文档章节

二叉树

石飞飞
 石飞飞
发布于 2017/09/08 19:48
字数 850
阅读 31
收藏 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

© 著作权归作者所有

共有 人打赏支持
石飞飞
粉丝 2
博文 64
码字总数 39883
作品 0
朝阳
程序员
私信 提问

暂无文章

Pycharm上Django的使用 Day8

1.添加新条目 1>编写用于添加新条目的表单 在forms.py中创建一个与模型Entry相关联的表单 1处给字段'text'指定一个空标签 2处定义小部件widgets,widgets是一个HTML表单元素 2>定义new_entry...

不会TC的猫
15分钟前
2
0
MongoDB副本集

MongoDB介绍 早期版本使用master-slave,一主一从和MySQL类似,但slave在此架构中为只读,当主库宕机后,从库不能自动切换为主 目前已经淘汰master-slave模式,改为副本集,这种模式下有一个...

chencheng-linux
28分钟前
1
0
WebService 客户端记录

https://blog.csdn.net/qiuhan/article/details/49487009

呼呼南风
28分钟前
0
0
七牛云彭垚:智能平台的创新和发展

2018 年 11 月 14 日至 11 月 18 日,第二十届中国国际高新技术成果交易会(简称高交会)在深圳成功举办,七牛云作为国内领先的以数据智能和视觉智能为核心的企业级云计算服务商受邀参展。 ...

七牛云
35分钟前
0
0
Java内存模型原理,你真的理解透彻了吗?

内存模型产生背景 在介绍 Java 内存模型之前,我们先了解一下物理计算机中的并发问题,理解这些问题可以搞清楚内存模型产生的背景。 物理机遇到的并发问题与虚拟机中的情况有不少相似之处,物...

小刀爱编程
39分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部