文档章节

二叉树

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

© 著作权归作者所有

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

暂无文章

java的反射机制理解

一、概念说明 java的反射机制,是在运行状态下,可以动态获取任意一个类的属性和方法;可以动态调用一个对象任意方法; 二、反射相关类 java.lang.Class; //类 java.lang.re...

盼望明天
7分钟前
0
0
nginx反向代理-多端口映射

代码解释 1.1 http:www.baidu.test.com默认是80,访问“/”利用反向代理,然后访问本地8083; 1.2 8083代表本地的前端工程访问地址,前端需要访问后台数据,”/”,继续代理到后台地址9803; ...

lilugirl
9分钟前
0
0
Jfinal使用log4j2打印日志

1,添加maven配置 <properties><log4j2.version>2.11.0</log4j2.version><slf4j.version>1.7.25</slf4j.version></properties> <!--slf4j及log4j2日志 --><dependency> ......

iborder
10分钟前
0
0
如何在Rancher 2.0上快速部署Datadog

Datadog是一种流行的托管监控解决方案,用于聚合和分析分布式系统的指标和事件。从基础架构集成到协作仪表板,Datadog为用户提供了一个简洁的单一窗格视图,用户可以快速查看对其最重要的信息...

RancherLabs
13分钟前
0
0
Java示例演示Functor 和monad

This article was initially an appendix in our Reactive Programming with RxJavabook. However introduction to monads, albeit very much related to reactive programming, didn't suit......

Quan全
31分钟前
0
0
微信官方jssdk Demo

1.html部分 <!DOCTYPE html><!-- saved from url=(0028){sh:$selfUrl} --><html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <meta charset="utf-8"......

koloor
34分钟前
1
0
数据库命名规范

https://www.cnblogs.com/pangguoming/p/7126512.html 摘要:当前研发工作中经常出现因数据库表、数据库表字段格式不规则而影响开发进度的问题,在后续开发使用原来数据库表时,也会因为数据...

塔塔米
34分钟前
0
0
java https 请求工具类-通用

package com.ra.common.util; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintW......

轻量级赤影
35分钟前
0
0
MFC界面套包BCG Pro Edition for MFC正式发布v27.3|附下载

BCGControlBar Professional Edition for MFC是MFC的一个扩展库,您可以用来构建类似于Microsoft Office 2000/XP/2003/2007/2010/2013 和 Microsoft Visual Studio-like(打印、用户定制工具......

Miss_Hello_World
35分钟前
0
0
Spring Cloud云服务 - HongHu架构common-service 项目构建过程

上一篇我们介绍了《整合spring cloud云服务架构 - HongHu云架构common-service代码结构分析》,本节我们将对common-service整个项目进行剖析,将整个构建的流程给记录下来,让更多的关注者来...

itcloud
36分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部