文档章节

J2SE_4_数据结构与算法(2)之树与二叉树

朱门中人
 朱门中人
发布于 2016/04/27 11:20
字数 1580
阅读 12
收藏 0

       上篇博文主要介绍的是数据结构的线性结构,我们这篇博文介绍非线性结构—树与二叉树,我先介绍树的一些基本概念,树的遍历,再介绍二叉树相关概念和特性,以及二叉树的遍历,最后再树与二叉树的对比,总结。

       树为了描述现实世界的层次结构,树结构中一个数据元素可以有两个或两个以上的直接后继元素。

  

树的基本概念:

  

           树的概念是学习树的关键所在,掌握了树的基本概念,学会树与二叉树,so easy。我通过一棵树来了解树的基本概念,如下图

                                                                      

1、结点的度

      结点的度是子结点的个数。例如:结点1有三个字结点2,3,4,所以结点1的度为3。

2、树的度

      树的度等于所有结点度中度最高的值。例如:上图中结点度最高为3,所以树的度为3。

3、叶子结点

      叶子结点是度为0的结点即没有子结点的结点。例如:上图中3,5,6,7,9,10。

4、分支结点

      分支结点是除了叶子结点,树中的其他所有结点。例如:上面树的分支结点为1,2,4,8。

5、内部结点

      内部结点是除了根结点以及叶子结点或在分支结点的基础之上在去掉根结点。例如:上面树的内部结点为2,4,8。

6、父结点、子结点、兄弟结点

     父节点、子结点和兄弟结点是相对而言的。例如:结点1是结点2,3,4的父节点,结点2,3,4也是结点1的子结点,结点2,3,4又是兄弟结点。

7、层次

     图中我们已经表出来了,根为第一层,根的孩子为第二层,依此类推,若某结点在第i层,则其孩子结点在第i+1层。

 

树的遍历

 树的遍历特别简单,我们还是以上面的树为例:

                                                          

1、前序遍历

      基本思想:前序遍历就是先访问根结点,再访问叶子结点。

      图中树的前序遍历为:1,2,5,6,7,3,4,8,9,10。

2、后序遍历

基本思想:本后序遍历就是先访问子结点,再访问根结点。

      图中树的后序遍历为:5,6,7,2,3,9,10,8,4,1。

3、层次遍历

     基本思想:从第一层开始,依此遍历每层,直到结束。

     图中树的层次遍历为:1,2,3,4,5,6,7,8,9,10。

 

二叉树的一些相关概念和特性

                           

           学习二叉树的特性几乎可以帮助我们解决所有的二叉树问题,在学习二叉树特性一定要通过上面给出的二叉树进行实践,实践出真理,同时,印象也会更深刻

 

一般二叉树性质(基本定义,不是一种特殊的树,这是另一种概念):

  1. 非空二叉树的k层上,至多有2k个节点(k>=0)
  2. 高度为k的二叉树中,最多有2k+1-1个节点(k>=0)
  3. 对于任何一棵非空的二叉树,如果叶节点个数为n0,度数为2的节点个数为n2,则有: n0 = n2 + 1满二叉树:根+分支节点+1,完全/非完全:根(或没有)+分支节点+1

完全二叉树性质:

     简单判断:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点

  1. 具有n个节点的完全二叉树的高度k为[log2n] 注:LOG2(8)=3相当于2的3次方等于8
  2. 对于具有n个节点的完全二叉树,如果按照从上(根节点)到下(叶节点)和从左到右的顺序对二叉树中的所有节点从0开始到n-1进行编号,则对于任意的下标为k的节点,有:
  • 如果k=0,则它是根节点,它没有父节点;如果k>0,则它的父节点的下标为[(k-1)/2];
  • 如果2k+1 <= n-1,则下标为k的节点的左子结点的下标为2k+1;否则,下标为k的节点没有左子结点.
  • 如果2k+2 <= n-1,则下标为k的节点的右子节点的下标为2k+2;否则,下标为k的节点没有右子节点。

满二叉树性质(特殊的完全二叉树):

      在满二叉树中,叶节点的个数比分支节点的个数多1和一般二叉树最后一样

 

二叉树遍历

                                                                            

1、前序遍历(与树的前序遍历一样)

      基本思想:先访问根结点,再先序遍历左子树,最后再先序遍历右子树即根—左—右

      图中前序遍历结果是:1,2,4,5,7,8,3,6。

2、中序遍历

      基本思想:先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树即左—根—右

      图中中序遍历结果是:4,2,7,8,5,1,3,6。(注意此处7算根,8算右子树

3、后序遍历(和树的后序遍历一样)

      基本思想:先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点即左—右—根

      图中后序遍历结果是:4,8,7,5,2,6,3,1。

4、层次遍历(与树的层次遍历一样)

      基本思想:从第一层开始,依此遍历每层,直到结束。

      图中层次遍历结果是:1,2,3,4,5,6,7,8。

 

树与二叉树区别

 

1、树可以有多个子结点,二叉树最多只能两个结点。

2、树中的子结点是无序的,二叉树是分左子结点和右子结点。

3、二叉树不是特殊树,而是独立的数据结构(重要)

 

总结

          这篇博文都是树的基本内容,这些基本内容可以帮助你更加深刻的理解树的其他内容,只要你能努力,世界充满爱。

本文转载自:http://blog.csdn.net/jiuqiyuliang/article/details/23961305

朱门中人
粉丝 3
博文 47
码字总数 310
作品 0
南京
程序员
私信 提问
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
2018/05/08
0
0
Java学习资料-Java常用算法-二叉树算法

二叉树算法的数据结构: 二叉树结点Node实现与c中的区别是,c中采用的是结构体,而java中是用类来实现,而在c++的教材中,类是一种自定义数据结构。 二叉树的leftchild和rightchild在c中是利...

晓阳
2015/01/28
722
0
(11)《数据结构与算法》之赫夫曼树

在我们开始介绍赫夫曼树之前,我们先带入一个情景。你想发送一个文件给你朋友,但是文件太大,所以你决定将文件压缩,变小再发送。你有没有考虑文件是怎么压缩呢?作为程序员,没有考虑过这里...

行走在代码边缘
06/26
0
0
数据结构知识学习与面试 一点课堂(多岸学院)

Queue 什么是队列 队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。 队列的种类 单队列(单队列就是常见的队列,...

程伟鑫
09/11
22
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

vue 2打包注意点

使用npm run build打包之后往往直接本地运行,路径类似这样:http://127.0.0.1:5500/xa/dist/index.html 或者http://127.0.0.1:5500/dist/index.html。然后页面打开是空白的,打开控制台查看...

牧云橙
24分钟前
4
0
归并排序

1.原理图 2.代码 public static void merge(int []a,int left,int mid,int right){ int []tmp=new int[a.length];//辅助数组 int p1=left,p2=mid+1,k=left;//p1、p2是检测......

wen123
28分钟前
4
0
css实现透明的两种方法

一、opacity:0~1 值越高,透明度越低: div{opacity:0.5 } 选择器匹配到的节点们,包括节点们的孩子节点,都会实现%50透明,另 0.5 可直接写成 .5 二、rgba(0~255,0~255,0~255,0~1) r...

Bing309
31分钟前
4
0
Tomcat 配置访问路径

此处只是部署完成后idea打开的默认路径,并非项目部署路径, 此处才是项目实际部署路径,可以有多个项目部署路径,idea可以配置默认打开一个

Aeroever
34分钟前
4
0
将ApiBoot Logging采集的日志上报到Admin

通过ApiBoot Logging可以将每一条请求的详细信息获取到,在分布式部署方式中,一个请求可能会经过多个服务,如果是每个服务都独立保存请求日志信息,我们没有办法做到统一的控制,而且还会存...

恒宇少年
35分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部