DS期末复习二叉树

二叉树

DS期末复习之二叉树

二叉树类的定义

二叉树肯定有根节点，就像链表一样，必须有头结点。

class BinaryTree {
    Node root;

    public void setRoot(Node root) {
        this.root = root;
    }
}


//结点类
class Node {
    String name;
    Node left;
    Node right;

    public Node(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "name='" + name + '\'' +
                '}';
    }
}

二叉树的遍历

前序遍历

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List preorderTraversal(TreeNode root) {
        List res = new ArrayList();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        inorder(root.left, res);
        inorder(root.right, res);
    }
}

中序遍历

import java.util.ArrayList;
import java.util.List;

public class Main {
    public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

后序遍历

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List postorderTraversal(TreeNode root) {
        List res = new ArrayList();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        inorder(root.right, res);
        res.add(root.val);
    }

层序遍历

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public ArrayList PrintFromTopToBottom(TreeNode root) {
        ArrayList resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        Queue q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode nowNode = q.peek();
            q.poll();
            resultList.add(nowNode.val);
            if (nowNode.left != null) {
                q.add(nowNode.left);
            }
            if (nowNode.right != null) {
                q.add(nowNode.right);
            }
        }
 
        return resultList;
    }
}

最重要的应该就是层序遍历，用到了广度优先搜索，其实就是每次访问完一个结点，将其子节点都入队，当队列空的时候结束。

二叉树的一些题目

二叉树相似判断

最重要的是找出递归终止条件

public boolean Like(Node Aroot, Node Broot) {
    if (Aroot == null && Broot == null) {
        return true;
    }
    if (Aroot == null || Broot == null){
        return false;
    }
    return Like(Aroot.left,Broot.left) && Like(Aroot.right,Broot.right);
}

计算叶子结点个数

还是递归

public int getLeafSize(Node root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return 1;
    } else {
        return getLeafSize(root.left) + getLeafSize(root.right);
    }
}

二叉树的最大深度

递归。。。

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

二叉树的最小深度

递归。。。

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.min(minDepth(root.left), minDepth(root.right));
}

对称二叉树

第一步是终止条件，然后要想对称，必须值val相等，然后递归检查p树的左子树和q树的右子树，p树的右子树和q树的左子树。
```
public boolean check(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
```
二叉树的题目很多，而我觉得大部分都能用递归解决，时间紧，先做一些基础的应付考试，等期末结束后刷题的时候再深入学习二叉树。

哈夫曼树

哈夫曼树，也就是最优二叉树

哈夫曼树相关的几个名词

路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。

路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。

结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

? 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。

例如图 1 中所示的这颗树的带权路径长度为：

WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

? 图1 哈夫曼树

什么是哈夫曼树？

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。在图 1 中，因为结点 a 的权值最大，所以理应直接作为根结点的孩子结点。

构建哈夫曼树的过程

对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：

在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。

?
图 2 哈夫曼树的构建过程

图 2 中，（A）给定了四个结点a，b，c，d，权值分别为7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。

下面是构建的代码：

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 2, 9};
        Node root = createHuffmanTree(arr);
        //测试
        preOrder(root);
    }

    //创建哈夫曼树的方法
    public static Node createHuffmanTree(int[] arr) {
        //first step
        ArrayList nodes = new ArrayList<>();
        for (int a : arr) {
            nodes.add(new Node(a));
        }
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            System.out.println("nodes=" + nodes);

            //取出权值最小的两颗二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            //变成一颗新的二叉树
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            //删除刚才两个二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //把parent加入到nodes
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //前序遍历
    public static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("空树无法遍历");
        }
    }
}

//结点类
class Node implements Comparable {
    int value;
    Node left;
    Node right;

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value + " ";
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
}

跟着韩顺平老师学的时候敲的。主要就是结点类Node实现了Comparable接口，用来比较结点值大小。然后就是算法逻辑，在一个循环中完成哈夫曼树的创建，不算难，只要了解了哈夫曼树构建的原理。

刷题算法学习

DS期末复习二叉树

二叉树

二叉树类的定义

二叉树的遍历

二叉树的一些题目

哈夫曼树

哈夫曼树相关的几个名词

相关

【基础】排序算法学习笔记

2017 清北济南考前刷题Day 6 morning

面试随缘刷题--day7

C语言刷题笔记6

LeetCode刷题总结-数组篇（上）

C语言刷题笔记5

C语言刷题笔记4

基础算法学习---背包问题

基础算法学习---prim

基础算法学习---prim

基础算法学习---dijkstar算法

[整理]qbxt周末刷题班 Day2总结

标签

DS期末复习 二叉树

二叉树

二叉树类的定义

二叉树的遍历

二叉树的一些题目

哈夫曼树

哈夫曼树相关的几个名词

相关

DS期末复习二叉树