当前位置:首页 > 嵌入式培训 > 嵌入式学习 > 讲师博文 >
二叉树基本概念讲解及创建
时间:2018-08-16作者:华清远见

一、简介

世界上的树有千万种,我们这里来学习我们数据结构中的树,它是我们现实生活中倒置的树。之前,我们学习的顺序表,链表,栈、和队列。可以说都是我们的线性结构,也就是我们所谓的一对一的结构,可是现实生活中,我们经常碰到是我们一对多的情况。今天,我们就来研究一下这种一对多的数据结构体-----“树”。那么,什么叫做树呢?

二、树的基本概念简介

<1>树的定义

专业定义:(1)有且只有一个称为根的结点

(2)有若干不相交的子树,这些子树本身也是一颗树。

通俗讲解:

(1)树由结点和边组成

(2)树中除根节点外,每一个节点都有一个父结点,但是 可以用多个子节点。

(3)根结点没有父结点

<2>树中的专业术语

节点 : 父节点 子节点(老子和儿子) 堂兄弟

度: 结点拥有子树的个数

叶子节点:没有子节点的节点

边 : 一个节点到另一个节点的距离

树的深度:节点的层数, 根节点默认为第一层。

有序 :树的左右位置不能改变。

<3>树的分类

一般树 : 任意一个结点的子节点的个数不受限制,则称为一般树。(子节点可以有多个),如下图:

二叉树(重点):任意一个节点的子节点的个数多有两个,且子节点的个数不能更改。

森林:树去掉根结点就称之为森林。

提问:在下图中:

<1>A,B,H,I的度分别是多少?

A:3 B : 2 H: 1 I: 0

<2>叶子节点有哪些?

K ,L,F,G,H,I,J

<3>结点F和I在树中的第几层?

F在第3层。

M在第4层

<4>树的深度是多少?

4

三、二叉树的特性讲解

<1>二叉树的性质讲解

如下图是一颗二叉树,它有一些特性:

思考:第一层多有多少个? 1个

第二层多有多少个? 2 个

第三层多有多少个? 4 ?

规律:第i层结点后有2的n - 1次方个。

性质1:二叉树的第i层上的结点多有2的i - 1次方个节点。

思考:深度为1的二叉树(遍历第一层)一共有多少个节点? 1个

深度为2的二叉树(遍历到第二层)一共有多少个节点? 3个

深度为3的二叉树(遍历到第三层)一共有多少个节点? 7个

规律:深度为k的而出书,多有2的k次方 - 1个节点。

性质2:深度为k的二叉树多有2的k次方-1个结点。

性质3:在任意一棵二叉树中,树叶的数目比度数为2的结点的数目多1.

(推导过程入下图所示:)

<2>二叉树的分类

满二叉树:在一颗二叉树中,如果所有的分支节点都存在左子树和右子树,并且所有的叶子节点都在同一层上,这样的二叉树,我们称之为满二叉树。

满二叉树的特点:<1>叶子节点只会出现在下面一层。

<2>非叶子节点的节点,拥有子树的个数一定为2.

<3>在同样深度的二叉树中,满二叉树的节点个数多。

完全二叉树:对一颗具有n个结点的二叉树按层进行编号,如果编号为i

(1 <= i <= n)的结点与同样深度的满二叉树节点编号为i的结点

在二叉树中的位置完全相同,则这颗树,我们称之为完全二叉树。

如下图所示。

提问:下面这些树,是完全二叉树吗? 不是

总结:满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

四、二叉树的存储

(1)顺序存储[完全二叉树]

(顺序存储的话,若不是完全二叉树存储没有意义。)

假设下面有一颗树,我们如何把它存到数组中呢?

思路:先把转换成完全二叉树,然后再编号。

这样存储就看似没有什么问题。我们可以按照编号把数据存储到数组中,我们按照编号(1,2,3,4,5)的顺序存储就可以了啊!这个时候,我就要问了,假说说,我们的m的编号,你怎么知道我们的3好位置是在下面,而不是在我们的m编号的位置呢?我们的连续存储无法识别。(这种方法,我们无法推断树的结构)。

因此,我们顺序存储规定:

无论是何种树,我们都会转换成完全二叉树。然后一层一层的从左给我们的二叉树进行编号,然后存储在数组中。及如下图。

那么我们以上的存储有什么规律呢?假设某个节点为i的话,我们来观察一下。

是不是所有的左孩子都是偶数,所有的右孩子都是奇数啊!

完全二叉树的特点:

对于编号为i(i>=1)的结点:

(1)左孩子存在:2 * i <= n(节点的个数),左孩子编号

(2)右孩子存储:2 * i + 1 <= n,右孩子编号 2 * i + 1

(2)链式存储[完全二叉树]

链式存储:定义结点保存左孩子和右孩子的地址。

思考:上述过程,我们的二叉树应该定义什么样的数据类型来保存结点呢?

<4>二叉树的遍历

(1)层次遍历:从上到下一层一层的遍历

(2)前序遍历:根 、左(左子树)、右(右子树)

(3)中序遍历:左(左子树) 、根 、右(右子树)

(4)后序遍历:左(左子树)、右(右子树)、根

规则:遇到根结点则输出,否则遍历。

层次遍历:ABCDEFGHI

先序遍历:ABDGHCEIF

中序遍历:GDHBAEICF

后序遍历:GHDBIEFCA

完全二叉树的递归创建思路:

1.首先,写一个创建单个节点的函数malloc_bnode,左孩子和右孩子都为空并且填充,我们需要的数据

2.然后写一个创建二叉树的函数create_binarytree()函数。调用malloc_bond

函数创建节点,然后判断结点有没有左孩子和右孩子。

2 *num <= n ,左孩子存在 (num为我们的结点编号,n为我们的结点个数)

再次,调用create_binarytree()创建该编号的孩子。

2 *num + 1 <=n,右孩子存储。

再次,调用create_binarytree()创建该编号的孩子,后返回根节点。







 

二叉树相关文章:

二叉树的一个典型应用-哈夫曼树一

二叉树的四种实现


发表评论

全国咨询电话:400-611-6270,双休日及节假日请致电值班手机:15010390966

在线咨询: 曹老师QQ(3337544669), 徐老师QQ(1462495461), 刘老师 QQ(3108687497)

企业培训洽谈专线:010-82600901,院校合作洽谈专线:010-82600350,在线咨询:QQ(248856300)

Copyright 2004-2018 华清远见教育集团 版权所有 ,京ICP备16055225号,京公海网安备11010802025203号