不再惧怕!二叉树结构相关算法总结 | 原力计划

2016-05-26

作者 | BoCong-Deng
来源 | CSDN 博客,责编 | 夕颜
出品 | CSDN(ID:CSDNnews)

写在前面


树结构对于程序员来说应该不陌生,特别是二叉树,基本只要接触算法这一类的都一定会碰到的,所以我打算通过一篇文章,对二叉树结构的相关算法进行总结汇总,思路和代码实现相结合,让你不在惧怕二叉树。


预备


下面的思路讲解中,我会给出一个类伪代码的思路,然后进行相关说明,也就是一种思路框架,有了思路框架,以后碰到问题就直接交给框架完成。本文主要说一下二叉搜索树(Binary Search Tree,简称 BST),BST是一种很常用的的二叉树。它的定义是:一个二叉树中,任意节点的值要大于等于左子树所有节点的值,且要小于等于右边子树的所有节点的值。如下就是一个符合定义的 BST:



后面如果遇到特殊的思路结构,如多叉树,我会特别说明。首先我们先给出二叉树的节点定义(这个定义应该不陌生吧,有刷算法题都会碰到)。


1public class TreeNode {
2      int val;
3      TreeNode left;
4      TreeNode right;
5      TreeNode(int x) { val = x; }
6}


递归


不过这里要说明一点的是,在伪代码中的“进行想要的操作”的位置,不一定就在我放置的位置,具体位置还需要我们根据不同的实际需求进行判断。不过因为前中后序的遍历,递归进入的时机应该需要和我的一样。


先序遍历


遍历根节点,如果根节点为空,返回;否则,遍历根节点,然后先序遍历左子树,再先序遍历右子树。


1public void preorderTraverse(TreeNode root){
2    System.out.print(node.val+" ");
3    preorderTraverse(root.left);
4    preorderTraverse(root.right);
5}


中序遍历


路过根节点,如果根节点为空,返回;否则,中序遍历左子树,然后遍历根节点,再中序遍历右子树。


1public void inorderTraverse(TreeNode root){
2    inorderTraverse(root.left);
3    System.out.print(node.val+" ");
4    inorderTraverse(root.right);
5}


后序遍历


路过根节点,如果根节点为空,返回;否则,后序遍历左子树,再后序遍历右子树,最后遍历根节点。


1public void postorderTraverse(TreeNode root){
2    postorderTraverse(root.left);
3    postorderTraverse(root.right);
4    System.out.print(node.val+" ");
5}


迭代(非递归)


我们使用迭代的思想,其实就是利用循环和栈来模拟递归的操作,上面递归的操作,其实就是一个不断将自己以及左右子节点进行压栈和出栈的过程,如果理解了上面的算法下面的算法就好理解了


前序遍历


 1public List<Integer> preorderTraversal(TreeNode root) {
2    List<Integer> list = new ArrayList<>();
3    if(root==null){
4        return list;
5    }
6    Stack<TreeNode> stack = new Stack<>();
7    stack.push(root);
8    while(!stack.isEmpty()){
9        TreeNode res = stack.pop();
10        if(res.right != null)
11            stack.push(res.right);
12        if(res.left != null)
13            stack.push(res.left);
14        list.add(res.val);
15
16    }
17    return list;
18}


中序遍历


 1public List<Integer> inorderTraversal(TreeNode root) {
2    List<Integer> list = new ArrayList<>();
3    if(root==null){
4        return list;
5    }
6    Stack<TreeNode> stack = new Stack<>();
7    TreeNode curr = root;
8    while(curr != null || !(stack.isEmpty())){
9        if(curr!= null){
10            stack.push(curr);
11            curr = curr.left;
12        }else{
13            curr = stack.pop();
14            list.add(curr.val);
15            curr = curr.right;
16        }
17    }
18    return list;
19}


后序遍历


我们可以很简单的实现另一种遍历:”根->右->左“遍历。虽然这种遍历没有名字,但是他是后序遍历的反序。所以我们可以利用两个栈,利用栈的LIFO特点,来实现后续遍历。


 1public List<Integer> preorderTraversal(TreeNode root) {
2    List<Integer> list = new ArrayList<>();
3    if(root==null){
4        return list;
5    }
6    Stack<TreeNode> stack = new Stack<>();
7    stack.push(root);
8    while(!stack.isEmpty()){
9        TreeNode res = stack.pop();
10        if(res.left != null)
11            stack.push(res.left);
12        if(res.right != null)
13            stack.push(res.right);
14        list.add(res.val);
15
16    }
17    list.reserve();
18    return list;
19}


深度优先搜索(DFS)


其实,二叉树的先序遍历,中序遍历,后序遍历,都是深度优先搜索,深搜是一种思想,并不具体指代实现方式,你可以使用递归,也可以使用栈来实现,所以上面提到的都是深度优先搜索的实现方式,毕竟“深度优先”嘛。

那在这里我就是提几个实际的应用的例子,加深一下印象。


*二叉树的最大深度


1public int maxDepth(TreeNode root) {
2    if(root==null){
3        return 0;
4    }
5    int left = maxDepth(root.left);
6    int right = maxDepth(root.right);
7    return Math.max(left,right)+1;
8}


*二叉树的镜像


 1public void Mirror(TreeNode root) {
2    if(root!=null){
3        if(root.left!=null || root.right!= null){
4            TreeNode temp =root.left;
5            root.left=root.right;
6            root.right=temp;
7        }
8        Mirror(root.left);
9        Mirror(root.right);
10    }
11
12}


*对称二叉树


 1boolean isSymmetrical(TreeNode pRoot){
2    if(pRoot == null)
3        return true;
4    return real(pRoot.left,pRoot.right);
5}
6public boolean real(TreeNode root1,TreeNode root2){
7    if(root1 == null && root2 == null){
8        return true;
9    }
10    if(root1 ==null || root2 == null){
11        return false;
12    }
13    if(root1.val != root2.val){
14        return false;
15    }
16    return real(root1.left,root2.right)&&real(root1.right,root2.left);
17}


*路径总和


 1public class Solution {
2    private ArrayList<Integer> list = new ArrayList<Integer>();
3    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
4    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
5        if(root == null)
6            return listAll;
7        list.add(root.val);
8        target -= root.val;
9        if(target == 0 && root.left==null && root.right == null){
10            listAll.add(new ArrayList<Integer>(list));
11        }
12        FindPath(root.left,target);
13        FindPath(root.right,target);
14        list.remove(list.size()-1);
15       return listAll;
16    }
17}


*重建二叉树


 1 public TreeNode reConstructBinaryTree(int [] pre,int [] in{
2    return reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
3}
4public TreeNode reConstructBinaryTree(int [] pre,int startpre,int endpre,int [] in,int startin,int endin){
5    if(startpre > endpre || startin > endin){
6        return null;
7    }
8    TreeNode root = new TreeNode(pre[startpre]);
9    for(int i =startin;i<=endin;i++){
10        if(in[i] == pre[startpre]){
11            root.left = reConstructBinaryTree(pre,startpre+1,startpre+i-startin,in,startin,i-1);
12            root.right = reConstructBinaryTree(pre,startpre+i-startin+1,endpre,in,i+1,endin);
13        }
14    }
15    return root;
16}


*二叉搜索树的最近公共祖先


 1class Solution {
2    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
3        if(root == null || root == p || root == q){
4            return root;
5        }
6        TreeNode left = lowestCommonAncestor(root.left,p,q);
7        TreeNode right = lowestCommonAncestor(root.right,p,q);
8        if(left!=null && right!=null){
9            return root;
10        }
11        return left!=null?left:right;
12    }
13}


*二叉树的序列化和反序列化



 1序列化:
2public String serialize(TreeNode root{
3    if (root == null) {
4        return null;
5    }
6    // 利用二叉树的层次遍历方式进行序列化
7    StringBuilder res = new StringBuilder();
8    LinkedList<TreeNode> queue = new LinkedList<>();
9    queue.add(root);
10    while (!queue.isEmpty()) {
11        TreeNode node = queue.remove();
12        if (node != null) {
13            res.append(node.val).append(",");
14            queue.add(node.left);
15            queue.add(node.right);
16        } else {
17            res.append("null,");
18        }
19    }
20    return res.toString();
21}
22反序列化:
23public TreeNode deserialize(String data{
24    if (data == null || data.length() == 0) {
25        return null;
26    }
27    String[] dataArr = data.split(",");
28    // 层次遍历逆向还原二叉树
29    int index = 0;
30    TreeNode root = toNode(dataArr[index]);
31    LinkedList<TreeNode> queue = new LinkedList<>();
32    queue.add(root);
33    while (index < dataArr.length - 2 && !queue.isEmpty()) {
34        TreeNode cur = queue.remove();
35        // 添加左子节点
36        TreeNode leftNode = toNode(dataArr[++index]);
37        cur.left = leftNode;
38        // 队列中的节点用于为其赋值孩子节点,若该节点本身为 null,
39        // 没有孩子节点,便不再添加到队列中,下同理
40        if (leftNode != null) {
41            queue.add(leftNode);
42        }
43        // 添加右子节点
44        TreeNode rightNode = toNode(dataArr[++index]);
45        cur.right = rightNode;
46        if (rightNode != null) {
47            queue.add(rightNode);
48        }
49    }
50    return root;
51}
52
53private TreeNode toNode(String val{
54    if (!"null".equals(val)) {
55        return new TreeNode(Integer.parseInt(val));
56    } else {
57        return null;
58    }
59}


广度优先搜索(BFS)


  • 首先将根节点放入队列中。

  • 从队列中取出第一个节点,并检验它是否为目标。

  • 如果找到目标,则结束搜索并回传结果。

  • 否则将它所有尚未检验过的直接子节点加入队列中。

  • 若队列为空,表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。

  • 重复步骤2。


 1public List<List<Integer>> levelOrder(TreeNode root) {
2    List<List<Integer>> res = new ArrayList<List<Integer>>();
3    List<TreeNode> quene = new ArrayList<TreeNode>();
4    if(root == null){
5        return res;
6    }
7    quene.add(root);
8    while(quene.size()!=0){
9        int count = quene.size();
10        List<Integer> list = new ArrayList<Integer>();
11        while(count>0){
12            TreeNode temp =quene.remove(0);                   
13            list.add(temp.val);
14            if(temp.left!=null){
15                quene.add(temp.left);
16            }
17            if(temp.right!=null){
18                quene.add(temp.right);
19            } 
20            count--;
21        }
22        res.add(list);
23    }
24    return res;
25}


莫里斯遍历(Morris)


通常我们对于二叉树进行遍历时,使用递归遍历或是基于栈来遍历,这两种方法都拥有最差为O(n)的空间复杂度(递归方法会在递归调用上浪费更多的时间),以及O(n)的时间复杂度。对于时间复杂度来说,由于需要遍历每个元素一次,所以O(n)已是最优情况。如此只能对空间进行优化。Morris遍历如何做到的呢?首先我们需要分析递归和基于栈的遍历它们为什么有O(n)的空间占用。以下图这个简单的二叉树遍历为例:



例如进行中序遍历(LDR),从1开始:


  • 1有左孩子2,将1放入栈中,移动到节点2;

  • 2有左孩子4,将2放入栈中,移动到节点4;

  • 4左孩子为空,输出节点4,此时节点4右孩子也为空,弹栈回到节点2;

  • 输出节点2,节点2有右孩子5,移动到节点5;

  • 5左孩子为空,输出节点5,此时节点5右孩子也为空,弹栈回到节点1;


从上面分析可以得知,传统遍历利用空间存储未实现全部操作的父节点,比如对于1节点,一开始进行L操作,没有进行D、R操作所以需要存储起来。为解决这一问题,Morris算法用到了”线索二叉树”的概念,利用叶节点的左右空指针指向某种遍历顺序的前驱节点或后继节点。Morris算法中序遍历流程:


  • 设置节点1为Current节点;

  • Current节点不为空,且有左孩子,于是找到节点1左子树中的最右侧节点,即节点5,使其右孩子指针指向自己,即link1;

  • Current节点移动到左孩子节点2,并删除父节点的左指针,使其指向为null,即删除erase1;

  • 节点2不为空,且有左孩子,于是找到节点2左子树中最右侧节点,即节点4,使其右孩子指针指向自己,即link2;

  • Current节点移动到左孩子节点4,并删除父节点的左指针,使其指向为null,即删除erase2;

  • 节点4左孩子为空,输出节点4,移动到右孩子节点2;

  • 节点2无左孩子(指针指向null),输出节点2,移动到右孩子节点5;

  • 节点5无左孩子,输出节点5,移动到右孩子节点1;

  • 节点2无左孩子(指针指向null),输出节点1,移动到右孩子节点3;


代码实现


 1void Morris_inorderTraversal(TreeNode root{
2    TreeNode curr = root;
3    TreeNode pre;
4    while (curr != null) {   
5        if (curr.left == null) {    // 左孩子为空
6            System.out.print(curr.val+" ");
7            curr = curr.right; 
8        }
9        else {   // 左孩子不为空
10            // 找左子树中的最右节点
11            pre = curr.left; 
12            while (pre.right != null) {  
13                pre = pre.right;
14            }
15            // 删除左孩子,防止循环
16            pre.right = curr; 
17            TreeNode temp = curr; 
18            curr = curr.left; 
19            temp.left = null;
20        }
21    }
22}


AVL树


AVL 树是一种平衡二叉树,平衡二叉树递归定义如下:


  • 左右子树的高度差小于等于 1。

  • 其每一个子树均为平衡二叉树。


为了保证二叉树的平衡, AVL 树引入了所谓监督机制,就是在树的某一部分的不平衡度超过一个阈值后触发相应的平衡操作。保证树的平衡度在可以接受的范围内。既然引入了监督机制,我们必然需要一个监督指标,以此来判断是否需要进行平衡操作。这个监督指标被称为“平衡因子(Balance Factor)”。定义如下:


  • 平衡因子:某个结点的左子树的高度减去右子树的高度得到的差值。

基于平衡因子,我们就可以这样定义 AVL 树。


  • AVL 树:所有结点的平衡因子的绝对值都不超过 1 的二叉树。

为了计算平衡因子,我们自然需要在节点中引入高度这一属性。在这里,我们把节点的高度定义为其左右子树的高度的最大值。因此,引入了高度属性的 AVL 树的节点定义如下:


1public class TreeNode {
2      int val;
3      int height;
4      TreeNode left;
5      TreeNode right;
6      TreeNode(int x) { val = x; }
7}


这里的节点和上面的不同的地方在于,我们多加了一个高度,用来记录每个节点的高度,如何得到每个节点的高度很简单,前面讲的算法中任何一种思路都可以实现,我这里就不赘述了,不过这里要多说一点的是,与之对应地,我们在进行如下操作时需要更新受影响的所有节点的高度:


  • 在插入结点时, 沿插入的路径更新结点的高度值

  • 在删除结点时(delete),沿删除的路径更新结点的高度值


我们重新定义了节点之后,有了高度属性,计算平衡因子的操作就得以很简单的实现,也就是某个节点的平衡因子=左节点高度-右节点高度。

当平衡因子的绝对值大于 1 时,就会触发树的修正,或者说是再平衡操作。


树的平衡化操作


二叉树的平衡化有两大基础操作:左旋和右旋。左旋,即是逆时针旋转;右旋,即是顺时针旋转。这种旋转在整个平衡化过程中可能进行一次或多次,这两种操作都是从失去平衡的最小子树根结点开始的(即离插入结点最近且平衡因子超过1的祖结点)。其中,右旋操作示意图如下:



所谓右旋操作,就是把上图中的 B 节点和 C 节点进行所谓“父子交换”。在仅有这三个节点时候,是十分简单的。但是当 B 节点处存在右孩子时,事情就变得有点复杂了。我们通常的操作是:抛弃右孩子,将之和旋转后的节点 C 相连,成为节点 C 的左孩子。这样,对应的代码如下。


 1TreeNode treeRotateRight(TreeNode root) {
2    TreeNode left = root.left;
3
4    root.left = left.right; // 将将要被抛弃的节点连接为旋转后的 root 的左孩子
5    left.right = root; // 调换父子关系
6
7    left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;
8    right.height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;
9
10    return left;
11}


而左旋操作示意图如下:



左旋操作和右旋操作十分类似,唯一不同的就是需要将左右互换下。我们可以认为这两种操作是对称的。代码如下:


 1TreeNode treeRotateLeft(TreeNode root) {
2    TreeNode right = root.ight;
3
4    root.right = right.left;
5    right.left = root;
6
7    left.height = Math.max(treeHeight(left.left), treeHeight(left.right))+1;
8    right->height = Math.max(treeHeight(right.left), treeHeight(right.right))+1;
9
10    return right;
11}


需要平衡的四种情况


  • LL 型



所谓 LL 型就是上图左边那种情况,即因为在根节点的左孩子的左子树添加了新节点,导致根节点的平衡因子变为 +2,二叉树失去平衡。对于这种情况,对节点 n 右旋一次即可。


  • RR 型



RR 型的情况和 LL 型完全对称。只需要对节点 n 进行一次左旋即可修正。


  • LR 型



LR 就是将新的节点插入到了 n 的左孩子的右子树上导致的不平衡的情况。这时我们需要的是先对 i 进行一次左旋再对 n 进行一次右旋。


  • RL 型


RL 就是将新的节点插入到了 n 的右孩子的左子树上导致的不平衡的情况。这时我们需要的是先对 i 进行一次右旋再对 n 进行一次左旋。


这四种情况的判断很简单。我们根据破坏树的平衡性(平衡因子的绝对值大于 1)的节点以及其子节点的平衡因子来判断平衡化类型。


平衡化操作的实现如下:


 1int treeGetBalanceFactor(TreeNode root) {
2    if(root == NULL)
3        return 0;
4    else
5        return x.left.height - x.right.height;
6}
7
8TreeNode treeRebalance(TreeNode root) {
9    int factor = treeGetBalanceFactor(root);
10    if(factor > 1 && treeGetBalanceFactor(root.left) > 0// LL
11        return treeRotateRight(root);
12    else if(factor > 1 && treeGetBalanceFactor(root.left) <= 0) { //LR
13        root.left = treeRotateLeft(root.left);
14        return treeRotateRight(temp);
15    } else if(factor < -1 && treeGetBalanceFactor(root.right) <= 0// RR
16        return treeRotateLeft(root);
17    else if((factor < -1 && treeGetBalanceFactor(root.right) > 0) { // RL
18        root.right = treeRotateRight(root.right);
19        return treeRotateLeft(root);
20    } else { // Nothing happened.
21        return root;
22    }
23}


这里推荐一个AVL树动态化的网站 https://www.cs.usfca.edu/~galles/visualization/AVLtree.html,可以通过动态可视化的方式理解AVL。


原文链接:

https://blog.csdn.net/DBC_121/article/details/104584060
【End】

推荐阅读 


你点的每一个在看,我认真当成了喜欢

相关文章

544,剑指 Offer-平衡二叉树

2021-09-22
问题描述输入一棵二叉树的根节点,判断该树是不是平衡二叉树.如果某二叉树中任意节点的左右子树的高度相差不超过1,那么它就...

红黑树、自平衡二叉树、AVL树、B树的比较

2021-09-22
1. 红黑树和自平衡二叉(查找)树区别1.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下...

python——有序表生成平衡二叉树

2021-09-22
print("生成的平衡二叉树为:", tree) print("树的顶点:", entry(tree)) print("树的左子树:", left_branch(tree))...

程序员面试之必考题(三):平衡二叉树的基本概念

2021-09-22
平衡二叉树是二叉树的一种应用,在介绍平衡二叉树之前,首先来看一看什么是二叉排序树. 二叉排序树二叉排序树(BST)或者是一...

不怕面试被问了!二叉树算法大盘点 | 原力计划

2021-09-22
树是一种平衡二叉树,平衡二叉树递归定义如下:左右子树的高度差小于等于 1.其每一个子树均为平衡二叉树.为了保证二叉树的平...

有图有真相!平衡二叉树AVL实现

2021-09-22
平衡二叉树(AVL),是一个二叉排序树,同时任意节点左右两个子树的高度差(或平衡因子,简称BF)的绝对值不超过1,并且左右...

【数据结构】平衡二叉树(AVL树)

2021-09-22
平衡二叉树(AVL树):它或者是一棵空树;或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树...

如何使用 JavaScript 实现二叉树,二叉平衡树和红黑树

2021-09-22
包含二叉树,二叉查找树,平衡二叉查找树(AVL树,红黑树),均已es6语法实现.查阅前默认你已经具备树相关的的基本概念,如...

Go 数据结构和算法篇(十八):平衡二叉树

2021-09-22
平衡二叉树要求每个节点的左子树和右子树的高度差至多等于 1,这个高度差的值叫做平衡因子 BF,也就是说 BF 的值不能大于1,否...

leetcode | 110.平衡二叉树

2021-09-22
本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 . 示例输入:root = [3,9,20,...

随机推荐

ThinkPHP框架讲解视频教程

2020-09-08
PHP进阶之面向对象相关视频教程 37进阶:PHP进阶之CMS内容管理系统(上) 38进阶:PHP进阶之CMS内容管理系统(中) 39进...

小米回应林斌退休传闻;哈工大等高校被禁止使用 MATLAB;统信软件 UOS20 SP1 系统升级| 极客头条

2020-09-01
在安卓软件商店搜索则显示“该应用内部优化中,暂不提供下载”.2019年12月30日,新版人人App登陆各大应用市场,回归社交市...

程序员眼里的PHP、Java、Python、C、C++ 是什么样儿的!

2020-08-17
我们来看看程序员眼里的武器们都是什么样的!知乎网友:... PHP:Python:Go:Haskell:Lisp:最后是 C++:知乎网友:朱冲喵...

PHP 排名最后?最赚钱的开发语言竟然是……

2020-06-15
每年 O'Reilly 都会发布其年度开发者的调查结果.这项调查涵盖了来自世界110个国家的近7000名程序员.42% 开发者薪资超过 10万...

图文与源码解说PHP如何解决高并发问题

2020-04-30
请看清楚这段话好吗:有需要的可以关注“PHP自学中心”,回复对应的关键词,获取链接与提取码.感谢大家的支持与信任web前端...

C语言 | 静态队列为什么必须是循环队列

2016-05-25

【必看】你的录取通知书何时到?怎么查?

2016-02-13
http://www.jlste.com.cn/内蒙古招生考试信息中心 http://www.nm.zsks.cn/青海省考试管理中心 http://www.qhzk.com/山西省招生考试管理...

5分钟搞定 Java Comparable接口

2015-10-31
我们要聊一聊Java Comparable接口.Comparable接口时用来干什么的呢?我们应该如何对事物进行比较和排序?这问题听上去有点莫...

【首次免费】下载价值16880元JAVA转型大数据开发全套教程(视频+源码)

2015-10-23
编程语言(Java、python、R、Go语言...)每种语言有自己擅长的点,所以不管是Java还是Python等编程语言对于大数据来说只是一个...

C、C++、Java、JavaScript、PHP、Python分别用来开发什么?

2015-09-08
C和C++C/C++ 理论上说可以做任何开发, 只要有合适的硬件驱动和 API,特点是效率高,基本上是编译语言里面效率最高的.除非你...