树的一些易混相关概念
1、 结点拥有的子树数称为结点的度(Degree)。树的度是树内各结点度的最大值。
2、树的深度(Depth)或高度是树中结点的最大层次数值。
3、祖先结点:从根结点到该结点所经分支上的所有结点。
4、子孙节点:某一结点的子女以及这些子女的子女。
二叉树
参考文:
二叉树的特点
- 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。
- 左子树和右子树是有顺序的,次序不能任意颠倒。
- 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。
二叉树五种基本形态
- 空二叉树
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树又有右子树
几种特殊的二叉树
斜树
又分为左斜树、右斜树。结点个数与二叉树深度相同
满二叉树
除叶子结点外的所有结点均有两个子结点。节点数达到最大值,所有叶子结点必须在同一层上。
完全二叉树
若设二叉树的深度为h,只看前1~(n-1)层则是满二叉树,第h层所有的结点都连续集中在最左边,这就是完全二叉树。
一个具有n个节点的完全二叉树,其叶子节点的个数为?
n1=0,n为奇数时:n0 = (n+1) / 2
n1=1,n为偶数时:n0 = n / 2
二叉树的性质
性质1:在二叉树的第i层上至多有2i-1个结点(i>=1)
性质2:深度为k的二叉树至多有2k-1个结点(k>=1)—–a1=1 公比为2的等比数列求和
性质3:对任何一棵二叉树T,如果其叶子数为n0,度为2的结点数为n2,则n0 = n2+1。
证明:一棵二叉树,除了终端结点(叶子结点),就是度为1或2的结点。假设n1度为1的结点数,则数T 的结点总数n=n0+n1+n2。我们再换个角度,看一下树T的连接线数,由于根结点只有分支出去,没有分支进入,所以连接线数为结点总数减去1。也就是n-1=n1+2n2,可推导出n0+n1+n2-1 = n1+2n2,继续推导可得n0 = n2+1。
性质4:具有n个结点的完全二叉树的深度为[log2(n+ 1) ] (向上取整)或者[log2n ]+1(向下取整) 。
性质5:如果对一颗有n个结点的完全二叉树(其深度为[log2n ] + 1)的结点按层序编号(从第1层到第[log2n ] + 1层,每层从左到右),对任一结点i(1<=i<=n)有:
- 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是结点[i/2]。
- 如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点i。
- 如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1。
- 结点i所在层次为[log2i ]+1(向下取整)
性质5其实就是顺序储存下父子结点编号关系
顺序结构实现二叉树
利用性质5可以对数组下标操作完成二叉树储存
二叉树的顺序存储结构缺点很明显:不能反应逻辑关系;对于特殊的二叉树(左斜树、右斜树),浪费存储空间。所以二叉树顺序存储结构一般只用于完全二叉树。
对于右斜树,顺序存储结构浪费存储空间:
^表示其中数据为空
链式结构实现二叉树
二叉链表:
三叉链表:
三叉链表在二叉链表的基础上添加一个返回指针指向父亲结点
含n个结点的二叉链表有n+1个空链指针域
含n个结点的三叉链表有n+2个空链指针域
关于遍历顺序
前序遍历顺序:规则是先是根结点,再前序遍历左子树,再前序遍历右子树
中序遍历顺序:规则是先中序遍历左子树,再是根结点,再是中序遍历右子树
后序遍历顺序:规则是先后序遍历左子树,再是后序遍历右子树,再是根结点
详细解释:
1、对于每个节点,访问顺序为遍历顺序
2、!对于每个节点,左子树的节点全部访问完,再能再根据遍历顺序访问右子树的节点。!!!!!!
根据这两条规则我们就能够确定其中任意一种遍历的顺序了。
代码实现
1 |
|
参考博文:
二叉树计数
N个结点二叉树有种
这个函数称为catalan函数
根据遍历顺序画出一棵二叉树
值得注意的是根据遍历顺序确定一棵二叉树必须要有一个中序在里面
总结与思考
通过创建树引发的对指针引用变量的思考:http://lyxf.live/posts/2541aeec/
- 1.关于求深度、节点数,我们使用递归思想,将问题化为一个小树枝,在设置恰当返回条件的前提下,不断向上返回,左右树不断扩大最终返回到树根
待补充
二叉树非递归遍历
线索二叉树
参考文章:
1、二叉树中没有利用的指针
n个节点二叉树有n+1个没有利用的指针
在N个节点的二叉树中,每个节点有2个指针,所以一共有2N个指针,除了根节点以外,每一个节点都有一个指针从它的父节点指向它,所以一共使用了N-1个指针,所以剩下2N-(N-1)也就是N+1个空指针;
2、利用空指针指向前驱后驱
原因:如果利用空指针直接记录前驱后驱结点,在遍历的时候会比递归速度要快还能减少建立递归程序的存储空间。
若结点的左子树为空,则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空,则该结点的右孩子指针指向其后继结点。
3、解决判断左右指针是为指向前后驱还是左右孩子
添加标志位ltag,rtag,并定义规则如下:
ltag为0时,指向左孩子,为1时指向前驱
rtag为0时,指向右孩子,为1时指向后继
5、实现方法
1、首先建立起二叉树
2、按某种次序遍历二叉树,在遍历过程中用线索取代空指针即可。
1 | //中序遍历进行中序线索化 |
把二叉树看成中序遍历序列,序列的第一个结点(最左下结点)的前驱为NULL,最后一个结点(最右下结点)的后继为NULL。通过设置pre的初始化为NULL和最后对pre(指向最后一个结点)的后继(右子树)设置为NULL来实现。
值得注意,我们在一次处理中是处理当前左结点和前驱的右节点,按照这样的顺序递归执行下去的,而不是对当前的左右结点处理
6、遍历
详见参考文章