二叉树(数据结构系列9)
目录
前言:
1.树的概念
2.树相关的性质的概念
3.二叉树的概念
4.二叉树的性质
5.二叉树的存储
6.二叉树的基本操作
7.二叉树的遍历方式
7.1前序遍历
7.2中序遍历
7.3后序遍历
7.4层序遍历
8.二叉树的基本操作
8.1获取树中结点的个数
8.2获取叶子结点的个数
8.3获取第k层结点的个数
8.4获取二叉树的高度
8.5检测值为value的元素是否存在
8.6判断一颗二叉树是不是完全二叉树
结束语:
前言:
这节博客中小编与大家主要分享二叉树的相关内容,和大家一起来学习一下二叉树的性质和二叉树的主要用法,以及一些二叉树的习题,话不多说,快来一起学习吧!!!
1.树的概念
树是一种非线性的数据结构,他由n(n >= 0)个有限结点组成一个具有层次关系的集合,把它叫做树是因为它看起来像是一颗倒挂的树,也就是说他是根朝上,而叶朝下的。它具有以下特点:
- 有一个特殊的结点,称为根节点,根节点没有前驱结点。
- 除根节点外,其余结点被分成M(M > 0)个互不相交的集合T1、T2、.......、Tm,其中每一个集合Ti(1 <= i <= m)又是一颗与树类似的子树。每棵子树的根节点有且只有一个前驱,可以有0个或者多个后继。
- 树是递归定义的。
注意:树形结构中,子树之间是不能有交集,否则就不是树形结构了。
所以怎样的树才算树呢?
满足下面的这些条件才算是树:
- 子树之间是不相交的。
- 除了根节点外,每个结点有且仅有一个父节点。
- 一颗N个结点的树有N-1条边。
2.树相关的性质的概念
下面我们来明确一些树里面的重要的基本概念。
- 结点的度:一个结点含有子树的个数称为该结点的度。
- 树的度:一颗树中,所有结点度最大值称为该树的度。
- 叶子结点或终端结点:度为0的结点称为叶结点。
- 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其结点的父结点。
- 孩子结点或子结点:一个结点含有的子树的根节点称为该结点的子结点。
- 根结点:一颗树中,没有双亲结点的结点。
- 结点的层次:从根开始定义起,根为第一层,根的子结点为第二层,以此类推。
- 树的高度或深度:树中结点的最大层次。
- 非终端结点或分支结点:度不为0的结点。
- 兄弟结点:具有相同父结点的结点互称为兄弟结点。
- 堂兄弟结点:双亲在同一层的结点互为堂兄弟结点。
- 结点的祖先:从根到该结点所经分支上的所有结点。
- 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。
- 森林:由m(m >= 0)颗互不相交的树组成的集合称为森林。
以下面的这个二叉树为例,我们来熟悉一下上面我所提到的这些概念吧!
结点的度:A结点的度为6,B结点的度为0,D结点的度为1, E结点的度为2,F结点的度为3。
树的度:其中树中最大的度是A结点的度6,故树的度就为6。
叶子结点或终端结点:上述树中的叶子结点有B、C、H、I、P、Q、K、L、M、N。
双亲结点或父结点:在上面的这个树中我们可以看到A就是B、C、D、E、F、G的父结点。
孩子结点或子结点:在上面的这个树中BCDEFG就是A的孩子结点,H是D的孩子结点。
根结点:A就是这课树的根节点。
结点的层次:如下图所示。
树的高度或深度:有上可知最大深度是4,所以该树的深度就是4。
非终端结点或分支结点:由上图可知其中A、D、E、F、G....都是度不为0的结点,故他们都是非终端结点或分支结点。
兄弟结点:其中B、C、D、E、F、G都有同一个父结点,所以他们都是兄弟结点。
堂兄弟结点:如H、I就是堂兄弟结点。
结点的祖先:例如P的结点的祖先就是A,E,J。
子孙:比如所有结点都是A的子孙结点。
森林:其中一颗树组成的也叫森林,或者是下面的这种情况。
3.二叉树的概念
上面我们讲解了什么是树,树的一些基本的性质,下面我们就来看我们就这次的重点内容,二叉树,那么什么是二叉树呢?一颗二叉树是结点的一个有限集合,该集合:
- 或者为空。
- 或者是由一个根结点加上两颗别称为左子树和右子树的二叉树组成。
如下图所示:
从上图中我们可以看出来:
- 二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树。
在我们学习的过程中我们会接触到两种特殊的二叉树,满二叉树和完全二叉树,那么这两种树有什么奇特之处呢?下面我们来一一介绍一下。
满二叉树:顾名思义就是这课二叉树上的每一个结点都是满的,也就是说一颗二叉树,如果每层的结点数都达到最大值,则这课二叉树就是满二叉树,我们也可以通过数学表达式的方式来了理解它,就是如果二叉树的层数为K,且结点总数是2^k - 1,则他就是满二叉树。如下图所示。
完全二叉树: 完全二叉树是一种效率很高的数据结构,完全二叉树是由满二叉树引出来的二叉树,对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从0-n-1的结点一一对应时称之为完全二叉树,要注意的是满二叉树是一种特殊的完全二叉树。
如下图所示:
4.二叉树的性质
二叉树和树一样也有很多重要的性质让我们来一起来看一下吧!
1.若规定根节点的层数为1,则一颗非空二叉树的第i层上最多有2^(i - 1)个结点。(i > 0)
2.若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是2^k - 1(k >= 0)。
3.对任何一颗二叉树,如果其叶节点个数为n0,度为2的非叶结点个数为n2,则有n0 = n2 + 1。
4.对于具有n个结点的完全二叉树的深度k为log2(n + 1)上取整。
5.对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有结点从0开始编号,则对于序号为i的结点有:
- 若i > 0,双亲序号:(i - 1)/ 2 = 0, i为根节点编号,无双亲结点。
- 若2*i + 1 < n,左孩子序号:2* i + 1,否则无左孩子。
- 若2*i + 2 < n,右孩子序号:2*i + 2,否则无右孩子。
下面我们通过这些性质来做一些习题吧。
1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( B )
A 不存在这样的二叉树
B 200
C 198
D 199
解析:由于我们上述性质中有一条结论是度为0的结点比度为2的结点数多1个,即n0 = n2 + 1。故当我们知道其中有199个度为2的结点数的时候,我们就可以直接得出度为0的结点个数有200个,也就是该二叉树中的叶子结点的个数。故答案为B。
2.在具有 2n 个结点的完全二叉树中,叶子结点个数为( A )
A n
B n+1
C n-1
D n/2
解析:由于二叉树中结点的个数N = n0 + n1 + n2。且在完全二叉树中,如果结点的个数是偶数的话n1 = 1,是奇数的话n1 = 0。故对于上述题而言结点总数是2n显然结点的个数是偶数个,固有2n = n0 + 1 + n2。有由于n0 = n2 + 1。所以两式联立可得n0就是n。故答案为A。
3.一个具有767个节点的完全二叉树,其叶子节点个数为( B )
A 383
B 384
C 385
D 386
解析:该题与上一题相似,总结点数是一个奇数,那么767 = n0 + 0 + n2,由于n0 = n2 + 1,所以解得n0 = 384,故答案为B。
4.一棵完全二叉树的节点数为531个,那么这棵树的高度为( B )
A 11
B 10
C 8
D 12
解析:由于 n = 2^k - 1,,可以计算得出总结点数,故层数的计算就是k = log2(n + 1),由于2^9 = 512, 2^10 = 1024,故向上取整k = 10。故答案为B。
5.二叉树的存储
二叉树的存储结构分为:顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过一个一个的结点引用起来的,常见的表示方式有二叉和三叉表示方式,具体如下述代码所示:
//孩子表示法
class Node1{
int val;//数据域
Node1 left;//左孩子的引用
Node1 right;//右孩子的引用
}
//孩子双亲表示法
class Node2{
int val;//数据域
Node2 left;//左孩子
Node2 right;//右孩子
Node2 parent;//当前结点的根结点
}
在后续的讲解过程中我们主要是以孩子表示法来进行创建二叉树的。
6.二叉树的基本操作
下面我们就通过代码来创建出以下的一颗二叉树吧。
代码如下所示:
public class MyBinaryTree {
public static class TreeNode{
public TreeNode left;//左孩子结点
public TreeNode right;//右孩子结点
public char val;//数据域
public TreeNode(char val) {
this.val = val;
}
}
private TreeNode root;//根结点
//创建一颗二叉树(以枚举的方式)
public void createBinaryTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
TreeNode I = new TreeNode('I');
//将创建出来的结点进行关联
root = A;
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
D.left = H;
D.right = I;
}
}
7.二叉树的遍历方式
二叉树中总共有三种遍历方式前序遍历、中序遍历、后序遍历和层序遍历,其中我们主要学习的就是前三个遍历方式,对于其中的前中后来说都是针对于遍历根的顺序来定义的,下面我们就来分别具体看一下。
7.1前序遍历
前序遍历的意思就是先遍历根,再遍历左孩子结点最后遍历右孩子结点,我们通常叫做根-左-右。
对于下面的这颗树来说我们如果是前序遍历的话就是:A-B-D-H-I-E-C-F-G。
那么我们又是怎么通过代码来实现前序遍历的呢?根据我们前面的二叉树概念来看我们一般都是通过递归来实现这些遍历的,那么接下来我们就来一起来通过代码来感受一下吧。
代码如下所示:
public class MyBinaryTree {
public static class TreeNode{
public TreeNode left;//左孩子结点
public TreeNode right;//右孩子结点
public char val;//数据域
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode root;//根结点
//创建一颗二叉树(以枚举的方式)
public TreeNode createBinaryTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
TreeNode I = new TreeNode('I');
//将创建出来的结点进行关联
root = A;
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
D.left = H;
D.right = I;
return root;
}
//前序遍历(递归实现)
public void preOrder(TreeNode root) {
//如果根结点是空的话,就说明这课树是空树
if (root == null) {
return;
}
System.out.print(root.val + " ");//打印根结点的值
preOrder(root.left);//向左递归
preOrder(root.right);//向右递归
}
}
结果如下所示:
下面我们来通过画图来深入了解一下前序遍历递归的过程。
7.2中序遍历
基于前序遍历来看那么中序遍历我们就好理解了,就是先遍历左孩子结点再遍历根结点最后再遍历右孩子结点,也就是左-根-右。
对于下面的二叉树来说,它的中序遍历就是:H-D-I-B-E-A-F-C-G。
具体的代码实现如下所示:
public class MyBinaryTree {
public static class TreeNode{
public TreeNode left;//左孩子结点
public TreeNode right;//右孩子结点
public char val;//数据域
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode root;//根结点
//创建一颗二叉树(以枚举的方式)
public TreeNode createBinaryTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
TreeNode I = new TreeNode('I');
//将创建出来的结点进行关联
root = A;
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
D.left = H;
D.right = I;
return root;
}
//中序遍历(递归实现)
public void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
}
结果如下所示:
7.3后序遍历
基于前序遍历来看那么中序遍历我们就好理解了,就是先遍历左孩子结点再遍历右孩子结点最后再遍历根结点,也就是左-右-根。
对于下面的二叉树来说,它的中序遍历就是:H-I-D-E-B-F-G-C-A。
代码如下所示:
public class MyBinaryTree {
public static class TreeNode{
public TreeNode left;//左孩子结点
public TreeNode right;//右孩子结点
public char val;//数据域
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode root;//根结点
//创建一颗二叉树(以枚举的方式)
public TreeNode createBinaryTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
TreeNode I = new TreeNode('I');
//将创建出来的结点进行关联
root = A;
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
D.left = H;
D.right = I;
return root;
}
//后序遍历(递归实现)
public void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
}
结果如下所示:
7.4层序遍历
层序遍历就是自上而下,自左到右逐层依次遍历。
那么对于下面的这课二叉树来说它的层序遍历结果就是:A-B-C-D-E-F-G-H-I。
那么对于层序遍历来说我们是如何通过代码来实现的呢?一般我们都是借助队列来实现的。
当遍历一个结点的时候就将其入队,如果队列不为空就将其队首元素出队并且打印,再将其左右孩子结点依次入队,循环直到队列为空时结束。
代码如下所示:
import java.util.LinkedList;
import java.util.Queue;
public class MyBinaryTree {
public static class TreeNode{
public TreeNode left;//左孩子结点
public TreeNode right;//右孩子结点
public char val;//数据域
public TreeNode(char val) {
this.val = val;
}
}
public TreeNode root;//根结点
//创建一颗二叉树(以枚举的方式)
public TreeNode createBinaryTree() {
TreeNode A = new TreeNode('A');
TreeNode B = new TreeNode('B');
TreeNode C = new TreeNode('C');
TreeNode D = new TreeNode('D');
TreeNode E = new TreeNode('E');
TreeNode F = new TreeNode('F');
TreeNode G = new TreeNode('G');
TreeNode H = new TreeNode('H');
TreeNode I = new TreeNode('I');
//将创建出来的结点进行关联
root = A;
A.left = B;
A.right = C;
B.left = D;
B.right = E;
C.left = F;
C.right = G;
D.left = H;
D.right = I;
return root;
}
//层序遍历(借助队列来完成)
public void levelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
System.out.print(cur.val + " ");
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
}
}
}
结果如下所示:
8.二叉树的基本操作
8.1获取树中结点的个数
我们可以采取子问题的方式来解决它。
其实我们所要求的树的结点的个数就等于左子树的结点的个数 + 右子树结点的个数 + 1。
核心代码如下所示:
//获取树中结点的个数
//思路:子问题思路 左树的结点树 + 右树的结点树 + 1
public int size(TreeNode root) {
if (root == null) {
return 0;
}
int leftSize = size(root.left);
int rightSize = size(root.right);
return leftSize + rightSize + 1;
}
结果如下所示:
我们也可以通过遍历的方式来达到目的。
核心代码如下所示:
//获取树结点的个数
//遍历方式实现
public static int sizeNode;
public void size2(TreeNode root) {
if (root == null) {
return;
}
sizeNode++;
size2(root.left);
size2(root.right);
}
结果与上同。
8.2获取叶子结点的个数
同获取结点个数一样,我们也是通过子问题的思路来解决的。
核心代码如下所示:
//获取叶子结点的个数
//思路:子问题 叶子结点的个数 = 左子树的叶子结点的个数 + 右子树叶子结点的个数
public int getLeafNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int leftLeafCount = getLeafNodeCount(root.left);
int rightLeafCount = getLeafNodeCount(root.right);
return leftLeafCount + rightLeafCount;
}
结果如下所示:
同样我们也可以以遍历的方式来进行。
核心代码如下所示:
//以遍历的方式来解决
public static int leafCount;
public void getLeafNodeCount2(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
leafCount++;
}
getLeafNodeCount2(root.left);
getLeafNodeCount2(root.right);
}
结果同上。
8.3获取第k层结点的个数
一样也是用子问题的思路来进行解决。
核心代码如下所示:
//获取第K层结点的个数
//思路:子问题 第K层结点的个数 = 左子树第K - 1层结点的个数 + 右子树第K - 1层结点的个数。
public int getLevelNode(TreeNode root, int k){
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
int leftSize = getLevelNode(root.left, k - 1);
int rightSize = getLevelNode(root.right, k - 1);
return leftSize + rightSize;
}
结果如下所示:
8.4获取二叉树的高度
也是子问题思路,采用左右树的最大值+1就可以达到我们要的目的了。
核心代码如下:
//获取二叉树的高度
//子问题思路,左右树的高度的最大值加1
public int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
结果如下:
8.5检测值为value的元素是否存在
也是子问题思路,具体看核心代码。
核心代码如下所示:
//检测值为value的元素是否存在
public boolean find(TreeNode root, char value) {
if (root == null) {
return false;
}
if (root.val == value) {
return true;
}
boolean leftFind = find(root.left, value);
if (leftFind) {
return true;
}
boolean rightFind = find(root.right,value);
if (rightFind) {
return true;
}
return false;
}
结果如下所示:
8.6判断一颗二叉树是不是完全二叉树
思想:我们是通过借助队列来完成的,当队列不为空的时候,并且如果弹出的队首元素不为null,那么我们就将队首元素的左右孩子结点继续入队,如果弹出的队首元素遇到了null,那么我们就停止入队操作,去判断一下队列中现在剩余的元素是不是都是null,如果是那就是完全二叉树,如果不是的话就不是一颗完全二叉树。
核心代码如下所示:
//判断该树是不是一颗完全二叉树
//借助队列来完成
public boolean isCompleteTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
if (root == null) {
return false;
}
queue.offer(root);
//将二叉树的结点依次进入队列中,再依次弹出队列,如果弹出队列时遇到null时就停止,然后就去判断队列中剩余的是不是都是null
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
if (top != null) {
queue.offer(top.left);
queue.offer(top.right);
}else {
break;
}
}
//判断队列中剩余的是否都是null,如果是那么就是完全二叉树,否则的话就不是完全二叉树。
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null) {
return false;
}
}
return true;
}
结果如下所示:
结束语:
这节小编就与大家分享到这里啦!下一节中小编将会与大家分享一下二叉树的一些具体习题,大家及得查收哦!!!以便于我们更好的对知识点的掌握和理解,大家继续跟紧小编的步伐一起往下走吧!!!希望对大家有所帮助,想要学习的同学记得关注小编和小编一起学习吧!如果文章中有任何错误也欢迎各位大佬及时为小编指点迷津(在此小编先谢过各位大佬啦!)