-
通俗易懂的讲解：二叉树是什么
本篇文章主要分几个部分，为大家通俗易懂的讲解：二叉树是
什么。听到二叉树这个词的时候，是不
是想到的就是某一个树呢
?
这里所讲的树可不是外面长在土地里的树，而是在计算机编程里的树
< br>!
一、二叉树的简介
在计算机科学中，二叉树是每个节点最多有两个子树的树结构
。通常子树被称作“左子树”(left
subtree)
和“右子树”(right
subtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至
多只有二棵子树
(
不存在度大于
2
的结点
)
，二叉树的子树有左右之分，
次序不能颠倒。二叉树的第
i
层至
多有
2^{i-1}
个结点
;
深度为
k
的二叉树至多有
2
^k-1
个结点
;
对任何一棵二叉树<
/p>
T
，如果其终端结点数为
n_0
，
度为
2
的结点数为<
/p>
n_2
，
则
n_
0=n_2+1
。
一棵深度为
k
，
且有
2^k-1
个
节点的二叉树，
称为满二叉树。
这种树的特点是每一层上的节点
数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满
的，并且最后一
层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有
n
个节
点的完全二叉树的深度为
log2n+
1
。
深度为
k
的完全二叉树，
至少有
2^(k-1)
个节点，
至多有
2^k-1
个节点。<
/p>
二、树的基本概念简介
<1>
树的定义
专业定义：
(1)
有且只有一个称为根的结点
(2)
有若干不相交的子树，这些子
树本身也是一颗树。
通俗讲解：
(1)
树由结点和边组成
(2)
树
中除根节点外，每一个节点都有一个父结点，但是
可以用多个子节点。
(3)
根结点没有父结点
<2>
树中的专业术语
节点
：
父节点
子节点
(
老子和儿子
< br>)
堂兄弟
度：
结点拥有子树的个数
叶子节点：没有子节点的节点
边
:
一个节点到另一个节点的距离
树的深度：节点的层数，
根节点默认为第一层。
有序
：树的左右位置不能改变。
<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
在树
中的第几层
?
< br>F
在第
3
层。
< br>
M
在第
4
层
<4>
树的深度是多少
?
4
三、二叉树的特性讲解
<1>
二叉树的性质讲解
如下图是一颗二叉树，它有一些特性：
思考：第一层最多有多少个
?
1
个
第二层最多有多少个
? 2
个
第三层最多有多少个
? 4 ?
规律：第
i
层结点最后有
2
的
n -
1
次方个。
性质
1:
二
叉树的第
i
层上的结点最多有
2
的
i -
1
次方个节点。
思考：深度为
1
的二叉树
(
遍历第一层
)
一共有多少个节点
?
1
个
<
/p>
深度为
2
的二叉树
(
遍历到第二层
)
一共有多少个节点
? 3
个
深度为
3
的
二叉树
(
遍历到第三层
)
一共有多少个节点
? 7
个
规律：深度为
k
的而出书，最多有
2
的
k
次方
-
1
个节点。
性质
2
：深
度为
k
的二叉树最多有
2
的
k
次方
-1
个结点。
性质
3
：在任意一棵二叉树中，树叶的数目比度数
为
2
的结点的数目多
1.
(
推导过程入下图所示：
)
<2>
二叉树的分类
满二叉树：在一颗二叉树中，如果
所有的分支节点都存在左子树和右子树，并且所有的叶子节点都在
同一层上，这样的二叉
树，我们称之为满二叉树。
<
/p>
满二叉树的特点：
<1>
叶子节点只会出
现在最下面一层。
<2>
非叶子节点的节点，拥有子树的个数一定为
2
.
<3>
在同样深度的二叉树中，满二叉树的节点个数最多。
完全二叉树：对一颗具有
n
个结点的二叉树按层进行编号，如果编号为
i
(1 <= i <= n)
的结点
与同样深度的满二叉树节点编号为
i
的结点
在二叉树中的位置完全相同
，则这颗树，我们称之为完全二叉树。
如下图所示。
提问：下面这些树，是完全二叉树吗
?
不是
<
/p>
总结：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
四、二叉树的存储
(1)
顺序存储
[
完全二叉树
]
(
顺序存储的话，若不是完全二叉树
存储没有意义。
)
假设下面有一颗树，我们如何把它存到数组中呢
?
思路：先把转换成完全二叉树，然后再编号。
这样存储就看似没有什么问题。我
们可以按照编号把数据存储到数组中，我们按照编号
(1,2,3,4,5)
的顺序存储就可以了啊
!
这个时候，我就要问了，
假说说，我们的
m
的编号，你怎么知道我们的
< br>3
好位置是
在下面，
而不是在我
们的
m
编号的位置呢
?
我们的连续存储无法识别。
(
这种方法，
我们无法推断树的结构
)
。
因此，我们顺序存储规定：
无论是何种树，我们都会转换成完全二叉树。然后一层一层的
从左给我们的二叉树进行编号，然后存
储在数组中。及如下图。
那么我们以上的存储有什么规律呢
?
假设某个节点为
i
< br>的话，我们来观察一下。
是不是所有的左孩子都是偶数，所有的右孩子都是奇数啊
!
完全二叉树的特点：
对于编号为
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.
然后写一个创建二叉树的函数<
/p>
create_binarytree()
函数。调用
malloc_bond
函数创建节点，然后判断结点有没有左孩子和右孩子。
2 *num<= n
，左孩子存在
(num
为我们的结点
编号，
n
为我们的结点个数
)
再次，调用
create_binarytree()
创建该编号的孩子。
2 *num + 1
<=n,
右孩子存储。
再次，调用
create_bina
rytree()
创建该编号的孩子，最后返回根节点。
好了，
到
这里就完了。
以上内容是不是非常的通俗易懂呢
?
现在你知道二叉树是什么了吧，后面还有更
多的有意思的知识点。学习中，如
果需要学习资料参考以及需要培训，都可以到华清远见的官网转一转，
有很多干货值得学
习
!
-
-
-
-
-
-
-
-
-
上一篇：什么是服务器HA技术
下一篇：加拿大自由行签证资料-2