共计 4000 个字符,预计需要花费 10 分钟才能阅读完成。
先大略说一下二叉树的根本内容。
1. 二叉树
什么是二叉树?
二叉树是一种树形构造,每个结点最多两棵子树,而且子树有左右之分,秩序不能颠倒。左右子树也是一棵二叉树。
1.1 二叉树的存储
二叉树能够用数组和链表存储。
1)顺序存储
应用一组地址间断的存储单元顺次自上而下,自左而右的顺序存储二叉树上的结点。简略来说,就是用数组存储,存二叉树的程序是从上到下,从左到右。
顺序存储形式适宜齐全二叉树或满二叉树。因为数组的长度是固定的,而这种二叉树的空节点少,不会节约很多数组的地址空间。
// java 定义形式
int[] array = new int[3];
array[0] = 1;
array[2] = 3;
// 或者是
int[] array = {1, 0, 3}; // 0 示意该处节点为空
2)链式存储
因为个别二叉树会有很多节点为空,如果应用顺序存储会导致很多空间节约掉。所以个别的二叉树应用链式存储比拟多。大多状况下,用到的也是链式存储,比方常常应用到的遍历。
链式存储是应用链表节点来存储二叉树中的每个节点。所有须要先定义链表的结点。
// java 定义形式
class TreeNode {
int val;
TreeNode left, right;
// 构造函数
}
1.2 二叉树的遍历
二叉树的遍历办法:前序遍历、中序遍历、后序遍历,应该没有人不晓得。以下的代码是应用 java 实现
1)前序遍历
void preOrder(TreeNode root) {
// 终止条件
if (root == null) return;
getValue(root); // 拜访该结点,做一些计算等
preOrder(root.left); // 遍历左结点点
preOrder(root.right); // 遍历右结点
}
2)中序遍历
void preOrder(TreeNode root) {
// 终止条件
if (root == null) return;
preOrder(root.left); // 遍历左结点点
getValue(root); // 拜访该结点,做一些计算等
preOrder(root.right); // 遍历右结点
}
3)后序遍历
void preOrder(TreeNode root) {
// 终止条件
if (root == null) return;
preOrder(root.left); // 遍历左结点点
preOrder(root.right); // 遍历右结点
getValue(root); // 拜访该结点,做一些计算等
}
4)例子
这三种遍历办法的代码并不难,平时做题的时候也没有很大的问题。然而有一次在极度缓和下,我发现做题时居然分不清过后用的是哪种遍历,是前序还是中序还是回溯来着??是该用哪种写代码呢??
以求树中的最大值、最小值为例。有这样一棵树,通过遍历的形式求出二叉树中的最大值、最小值。
<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119223731.jpg” alt=”1-1″ style=”zoom: 80%;” />
那么,在遍历中,须要记录以后结点的最大值和最小值,上面的图中,[最大值, 最小值]
记录的是以后的最大值和最小值。
前序遍历
走到结点 1
(遍历结点),记录下以后的最大值和最小值 [1, 1]
(拜访结点),而后遍历左子树,遍历完左子树再右子树。图中圆圈中记录的是结点的拜访程序,前序的遍历程序和拜访程序雷同。
<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119234925.jpg” alt=”1″ />
中序遍历
以结点 1
为例,走到结点 1
(遍历结点),不记录。当把左子树的节点拜访完之后,而后拜访结点 1
,也就是记录结点 1
此时的最大值最小值 [5, 1]
。而后再拜访结点 1
的右子树。
所以,第一个记录最大值和最小值的结点是结点 4
,也就是第一个拜访的结点是结点 4
。第二个记录最大值和最小值的结点是结点 2
,也就是第二个拜访的结点是结点 2
。
图中圆圈中记录的是结点的拜访程序,中序的遍历程序和拜访程序不同。
后序遍历
以结点 1
为例,走到结点 1
(遍历结点),不记录。当把左子树的节点拜访完之后,而后再拜访结点 1
的右子树。最初拜访结点 1
,也就是记录结点 1
此时的最大值最小值 [6, 1]
。
所以,第一个记录最大值和最小值的结点是结点 4
,也就是第一个拜访的结点是结点 4
。第二个记录最大值和最小值的结点是结点 5
,也就是第二个拜访的结点是结点 5
。
图中圆圈中记录的是结点的拜访程序,后序的遍历程序和拜访程序不同。
遍历程序的问题就到这里了。上面的代码是求二叉树中的最大值和最小值,代码应用 java 实现。
int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
public void getMaxDifference(TreeNode root) {if (root == null) return;
if (root.val > max) max = root.val;
if (root.val < min) min = root.val;
getMaxDifference(root.left);
getMaxDifference(root.right);
}
4)档次遍历
档次遍历是通过队列实现的,以下的代码是应用 java 实现
// 遍历二叉树,其余什么也没做
void level(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();
if (root != null) queue.offer(root); // 退出根节点
while (!queue.isEmpty()) {
// 弹出队首节点
TreeNode cur = queue.poll();
// 退出左右节点
if(cur.left != null) queue.offer(cur.left);
if(cur.right != null) queue.offer(cur.right);
}
}
2. 树
二叉树是树,但树不肯定是二叉树。所以,二叉树和树的关系就很显著:二叉树能够应用树的货色,树不能应用二叉树的货色。
为什么这里会说到树呢?
因为在一次面试中遇到一道题,是应用数组存储二叉树,数组中的值是它的父节点的下标。嗯嗯,如果把二叉树和树割裂开记忆学习,思维会局限在那一小块。不只是二叉树和树,其余的常识也应该分割在一起,也能够分割在一起。
2.1 树的存储形式
树的存储形式有很多中,即可用顺序存储,也可用链式存储。然而不论哪种存储形式,都要可能惟一的反映 树中各节点之间的逻辑关系。这一点,对于二叉树来说也是一样。因为树中有几个子节点,是不确定的,所以不能像二叉树中那样,间接定义两个子节点 left
,right
,就能够示意整个树。
1)双亲表示法
记录的是以后节点的父结点。应用数组存储,存储的是以后节点的父节点在数组中的地位。
正式点的术语说就是,采纳一组间断空间来存储每个节点,同时每个节点减少一个变量(指针),用来记录该节点的双亲节点在数组中的地位。
这种构造,找到以后结点的父节点很容易,然而找到以后结点的孩子节点,须要遍历整个树,也就整个存储构造。
下面的树的存储构造,能够示意为以下(应用 java 实现)
// 定义结点
class TreeNode {
int val;
int parent;
// 构造函数
}
// 定义一棵树
TreeNode[] tree = new TreeNode[10];
如果一棵树中节点的值就是数组中的下标,那么还能够不存储 val
,示意如下(应用 java 形容)
int[] tree = new int[10];
举个例子,如果一个数组是 int[] tree = {1, -1, 1, 0}
,那么这棵树示意的就是,根节点是 1
,1
的两个子节点是 0
,2
,0
的一个子节点是 3
。
嗯嗯嗯,这个如同是二叉树??嗯,就是二叉树,用数组示意了一棵一般的二叉树(当然了,这种示意形式不能辨别左右子节点)。
2)孩子表示法
记录的是以后节点的所有子结点。
正式点的术语说就是,每个结点的孩子都用单链表连接起来,造成一个线性构造,
这种构造,找到以后结点的孩子节点很容易,然而找到以后结点的父节点,须要遍历整个树,也就整个存储构造。
<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119183800.png” alt=”image-20220119183757642″ style=”zoom:80%;” />
下面的树的存储构造,能够示意为以下(应用 java 实现)
// 定义结点
class TreeNode {
int val;
List<TreeNode> child;
// 构造函数
}
// 定义一棵树
TreeNode[] tree = new TreeNode[10];
如果一棵树中节点的值就是数组中的下标,那么还能够不存储 val
,示意如下(应用 java 形容)
List<Integer>[] tree = new List[10];
3)孩子兄弟表示法
记录的是以后节点的第一个子结点和下一个兄弟节点。孩子兄弟表示法又称二叉树链表法,也就是将二叉链表作为树的存储构造,一个子结点指向孩子结点,一个子结点指向兄弟节点。
<img src=”https://gitee.com/withered-wood/picture/raw/master/20220119214510.png” alt=”image-20220119214509319″ style=”zoom:80%;” />
下面的树的存储构造,能够示意为以下(应用 java 实现)
// 定义结点
class TreeNode {
int val;
TreeNode firstChild, nextsibling;
// 构造函数
}
// 定义一棵树
TreeNode[] tree = new TreeNode[10];
参考资料
王道数据结构书籍