文档章节

二叉树

石飞飞
 石飞飞
发布于 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
朝阳
程序员

暂无文章

sqlserver 2008 r2 直接下载地址(百度云)

之前下载的sqlserver2008发现不能附加,就卸载了,重新找到了sqlserver2008R2的百度云资源 卸载sqlserver2008还是有点麻烦,不过就是需要删除注册表中的信息 自己来回卸载了3次终于重装sqlse...

dillonxiao
33分钟前
1
0
[Java]JVM调优总结 -Xms -Xmx -Xmn -Xss

JVM调优总结 -Xms -Xmx -Xmn -Xss 博客分类: Java General JVM应用服务器电信CMS算法 堆大小设置 JVM 中最大堆大小有三方面限制:相关操作系统的数据模型(32-bt还是64-bit)限制;系统的可...

morpheusWB
44分钟前
1
0
C++ std::function 和 std::bind

C++11提供了std::function和std::bind两个工具,用于引用可调用对象。这些可调用对象包括 普通函数,Lambda表达式,类的静态成员函数,非静态成员函数以及仿函数等。引用可调用对象,可以用于...

yepanl
今天
2
0
python:可迭代对象的索引

关于 python的range的用法: 注意是[ 开始,结束)的半开区间,不包括结束 http://www.runoob.com/python/python-func-range.html import collectionsfrom collections import Iterable字符串......

Oh_really
今天
3
0
docker-compose ,docker-stack

1.例子 version: "3"services: php: image: registry.cn-hangzhou.aliyuncs.com/lxepoo/apache-php5 ports: - "38080:80" networks: - my_php_mysql volum......

chenbaojun
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部