文档介绍：通俗易懂的讲解:二叉树是什么本篇文章主要分几个部分,为大家通俗易懂的讲解:二叉树是什么。听到二叉树这个词的时候,是不是想到的就是某一个树呢?这里所讲的树可不是外面长在土地里的树,而是在计算机编程里的树! 一、二叉树的简介在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2n+1。深度为k的完全二叉树,至少有2^(k-1)个节点,至多有2^k-1个节点。二、树的基本概念简介<1>树的定义专业定义:(1)有且只有一个称为根的结点(2)有若干不相交的子树,这些子树本身也是一颗树。通俗讲解: (1)树由结点和边组成(2)树中除根节点外,每一个节点都有一个父结点,但是可以用多个子节点。(3)根结点没有父结点<2>树中的专业术语节点:父节点子节点(老子和儿子)堂兄弟度:结点拥有子树的个数叶子节点:没有子节点的节点边:一个节点到另一个节点的距离树的深度:节点的层数,根节点默认为第一层。有序:树的左右位置不能改变。<3>树的分类一般树:任意一个结点的子节点的个数不受限制,则称为一般树。(子节点可以有多个),如下图: 二叉树(重点):任意一个节点的子节点的个数最多有两个,且子节点的个数不能更改。森林:树去掉根结点就称之为森林。提问:在下图中: <1>A,B,H,I的度分别是多少? A:3B:2H:1I: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)右孩子存储: