数据结构——树（中）

1、二叉树的定义

​ 二叉树是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

2、二叉树的特殊类型

1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树

（福利推荐：阿里云、腾讯云、华为云服务器最新限时优惠活动，云服务器1核2G仅88元/年、2核4G仅698元/3年，点击这里立即抢购>>>）

2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树

完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1

3、二叉树相关术语

1、结点：包含一个数据元素及若干指向子树分支的信息

2、结点的度：一个结点拥有子树的数目称为结点的度

3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点

4、分支结点：也称为非终端结点，度不为零的结点称为非终端结点

5、树的度：树中所有结点的度的最大值

6、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层

7、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度

8、有序树：如果树中各棵子树的次序是有先后次序，则称该树为有序树

9、无序树：如果树中各棵子树的次序没有先后次序，则称该树为无序树

10、森林：由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成

4、二叉树的性质

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点

性质2：深度为h的二叉树中至多含有2h-1个节点

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

• 当i=1时，该节点为根，它无双亲节点
• 当i>1时，该节点的双亲节点的编号为i/2
• 若2i≤n，则有编号为2i的左节点，否则没有左节点
• 若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点

5、二叉树的存储结构

1、顺序储存

其储存方式的图示为

这里的树为完全二叉树，如果结构不是完全二叉树，可以通过补齐的方式，使其变成完全二叉树

这样的储存方式，读取速度快，但是空间利用率不高

2、链式存储

其单个元素的表示方式为

整体的结构为

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)