文档章节

二叉树

石飞飞
 石飞飞
发布于 2017/09/08 19:48
字数 850
阅读 32
收藏 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
朝阳
程序员
私信 提问

暂无文章

漏洞防御与修复工作

漏洞管理工作是企业安全建设必不可少的一环,在风险管理工作中,漏洞管理能够防患于未然,企业对漏洞管理有着广泛的基础建设和实践经验。但随着攻防技术的发展,传统漏洞管理的安全技术和管理...

linuxprobe16
14分钟前
0
0
MicroPython技术及应用前景

1 Micropython技术是什么? MicroPython极精简高效的实现了Python3语言。它包含Python标准库的一小部分,能在单片机和受限环境中运行。 1.1 MicroPython发展 由剑桥大学的理论物理学家乔治....

bodasisiter
20分钟前
0
0
跟我学Spring Cloud(Finchley版)-13-通用方式使用Hystrix

本节详细讲解使用Hystrix的通用方式。 简介 Hystrix是由Netflix开源的一个延迟和容错库,用于隔离访问远程系统、服务或者第三方库,防止级联失败,从而提升系统的可用性与容错性。Hystrix主要...

周立_ITMuch
29分钟前
0
0
🛠️Hanjst/汉吉斯特更新加JavaScript运行时优化等

这是 Hanjst/汉吉斯特 发布以来的首个主要升级更新版本。这次的主要升级更新的内容包括移除HTML Comments注释行, 优化在 Hanjst include模板文件时的JavaScript运行时环境。 Hanjst 在设计和...

wadelau
今天
2
0
OSChina 周六乱弹 —— 舔狗是没有好下场的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @我没有抓狂 :#今天听什么# #今天听这个# 分享 Nirvana 的歌曲《Smells Like Teen Spi...》 《Smells Like Teen Spi...》- Nirvana 手机党少...

小小编辑
今天
463
13

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部