定义:Tree是n(n>=0)个结点的有限集

若n=0,称为空树

若n>0,则它满足如下两个条件:

  • 有且仅有一个特定的称为根(Root)的结点
  • 其余结点可以分为m(m>=0)个相互不相交的有限集T1,T2,T3......Tm,其中每一个集合本身又是一棵树,并称为根的子树(SubTree)

树定义是一个嵌套的定义

树的表示形式:

image-20210731225127233

树的相关概念:

结点的度:结点拥有的子树数

树的度:树内各结点的度的最大值

树的深度:树中结点的最大层次(有多少层)

树结构和线性结构的对比

image-20210731230218464

二叉树

注意:二叉树不是树的一种特殊情况。

image-20210731231030274

二叉树定义:由空集或由一个根结点以及两棵互不相交的左右子树组成。

特点:

  1. 每个结点最多有两个孩子
  2. 子树有左右之分,次序不能颠倒
  3. 二叉树可以是空集合,根可以有空的左子树或空的右子树。

二叉树的性质

image-20210801122452546

image-20210801122559199

image-20210801122738698

两种特殊的二叉树

image-20210801123107658

image-20210801123224179

image-20210801123858794

image-20210801123919533

image-20210801124125130

二叉树的存储结构

顺序存储

按照满二叉树的结点层次编号,依次存放二叉树中的数据元素。

image-20210801124505829

image-20210801124753062

二叉树的链式存储结构

image-20210801124904260

image-20210801125018320

image-20210801125041308

二叉树的遍历

定义:是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次仅被访问一次

二叉树的遍历方式(左-右)

二叉树的遍历方式有很多,如果我们限制了从左到右的习惯方式,那么主要就分为四种

1. 先序遍历

先要判断是否为空树,如果是,则直接返回空操作。

否则进行如下操作:

访问结点

然后遍历子树

最后遍历子树

(根-左-右)

image-20210801175817841

2. 中序遍历

先要判断是否为空树,如果是,则直接返回空操作。

否则进行如下操作:

从根结点开始(注意并不是先访问根节点)

遍历根结点的左子树

然后再访问根结点

最后遍历右子树

(左-根-右)

image-20210801175848731

3. 后序遍历

先要判断是否为空树,如果是,则直接返回空操作。

否则进行如下操作:

先左,后右,最后根

image-20210801175937879

4. 层次遍历

先要判断是否为空树,如果是,则直接返回空操作。

否则进行如下操作:

从树的第一层,即根结点开始访问

按照从上到下逐层遍历

同一层中则按照从左到右逐个访问结点

构造二叉树

知道先序序列和中序序列可以构造二叉树,如图所示。

image-20210801180655947

知道后序序列和中序序列,可以构造二叉树,如图所示。

image-20210801181348470

二叉树的算法实现

构造一棵二叉树

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

先序遍历

递归算法实现

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }

    //递归算法
    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

迭代算法实现

public class Solution2 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); //存放结果
        Stack<TreeNode> stack = new Stack<>(); //存放节点

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.add(root);
                root = root.left;
            }
            root = stack.pop().right;
        }

        return res;
    }
}

中序遍历

递归算法实现

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        return list;
    }

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

迭代算法实现

public class Solution2 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //创建一个栈
        Stack<TreeNode> stack = new Stack<>();
        //当前指向的节点root和栈都为空时,才结束遍历
        while (root != null || !stack.isEmpty()) {
            //当当前节点为空时,出栈,否则入栈
            while (root != null) { //把左边子树都遍历完成,把左子树中的每个根节点入栈保护起来
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            //出栈的节点的值就是当前要访问的值
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

后序遍历

递归算法实现

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    //递归法
    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

迭代算法实现

class Solution2 {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); //存放结果集
        Stack<TreeNode> stack = new Stack<>(); //暂存节点
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                //先按照根右左顺序遍历,然后进行反转,就变成左右根顺序了
                res.add(root.val); //把当前指向的节点的值放到集合中
                stack.push(root); //把右子节点都入栈,先入栈的后弹出
                root = root.right; //改变指向
            }
            //经过上面的while循环,root已经指向树的最右边的叶子节点
            TreeNode cur = stack.pop(); //出栈叶子节点的双亲节点
            root = cur.left; //双亲节点的左子节点
        }
        //因为是根据 根-右-左 顺序来遍历的,所以需要反转结果集
        Collections.reverse(res);
        return res;
    }
}

层次遍历

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root); //添加根节点
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int curLevelNum  = queue.size(); //当前层的节点个数
            for (int i = 0; i < curLevelNum ; i++) { //遍历当前层
                TreeNode curNode = queue.removeFirst(); //移除队首节点
                list.add(curNode.val); //把队首节点的值添加到临时集合list中
                if (curNode.left != null) { //移除队首节点时,同时把左右节点都入队
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

输出的结果

image-20210808235232729

如果要输出[1, 2, 3, 4, 5]的形式,需要把for循环去掉

扩展

N叉树的层次遍历

public class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}
public class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<Node> queue = new LinkedList<>(); //定义一个双端队列
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>(); //保存每层中节点的值
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                temp.add(node.val);
                for (int j = 0; j < node.children.size(); j++) {
                    if (node.children.get(j) != null) {
                        queue.offer(node.children.get(j));
                    }
                }
            }
            res.add(temp);
        }
        return res;
    }
}

二叉树的锯齿形层序遍历

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int index = 1; //层次
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) { //遍历当前层中的节点
                //为什么不用remove方法,因为当队列为空时,remove方法会报异常,poll方法会返回null
                TreeNode node = queue.poll();
                temp.add(node.val); //把当前节点值保存起来
                //如果左节点不为空,则放到队列中,充当下次遍历的节点
                if (node.left != null) {
                    //为什么不用add方法,因为当队列满时,add方法会报异常,offer方法会返回false
                    queue.offer(node.left);
                }
                //如果右节点不为空,则放到队列中,充当下次遍历的节点
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            //判读是单数层还是双数层,单数层遍历方向为从左到右顺序
            if ((index & 1) == 1) {
                res.add(temp);
            } else {
                Collections.reverse(temp); //双数层时,需要反转
                res.add(temp);
            }
            index++;
        }
        return res;
    }
}

Huffman树

定义

给定n个权值作为n个叶子结点

构造一棵二叉树,如果树的带权路径长度达到最小,则这棵树被称作哈夫曼树。

权(weight): 将树中结点赋给一个有着某种含义的数值,(具体的意义根据树使用的场合确定)则这个数值称为该结点的权。

结点的带权路径长度:从根结点到该结点之间的路径长度与结点上权的乘积。

树的带权路径长度:从树根到每一个结点的路径长度之和

image-20210802142807340

构造哈夫曼树的算法

  1. 构造森林全是根

    image-20210802143106859

  2. 选用两小造新树

    image-20210802143128587

  3. 删除两小添新人

    image-20210802143153765

  4. 重复2,3剩单根

总结

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树,共产生n-1个新结点

所以哈夫曼树的总的结点数是n+n-1=2n-1个结点。

哈夫曼树的结点度为0或度为2,没有度为1的结点。

权值越大离根越近,权值越小离根越远。

Huffman编码

image-20210808224331872

image-20210808224355385

线索二叉树

image-20210808225343790

image-20210808225431317

image-20210808225716113

image-20210808225820948

image-20210808225907794

image-20210808230218393

image-20210808230547536

树与森林

树一定是森林,但森林不一定是树

image-20210807231224395

树的表示方法

双亲表示法

定义结构数组存放树的结点,每个结点含两个域。

数据域:存放结点本身信息。

双亲域:指示本结点的双亲结点在数组中的位置。

特点:找双亲容易,找孩子难。

image-20210807232622335

孩子链表

image-20210807232708964

带双亲的孩子链表

image-20210807233946122

孩子兄弟表示法

image-20210807234915047

image-20210807234938848

树与二叉树的转换

树转二叉树

image-20210807235334081

image-20210807235348390

image-20210807235408478

二叉树转树

image-20210807235437946

森林与二叉树的转换

森林转二叉树

image-20210808012819031

image-20210807235750134

二叉树转森林

image-20210807235814335

image-20210807235835473

树与森林的遍历

树的遍历

有三种遍历方式:

  1. 先根遍历:若树非空,则先访问根结点,然后依次先遍历各棵子树。
  2. 后根遍历:若树非空,则先依次后根遍历各棵子树,然后访问根结点。
  3. 层次遍历:若树非空,则自上向下自左向右访问树中的每个结点。

image-20210808001008483

森林的遍历

image-20210808001121319

image-20210808001142518

Q.E.D.


热爱生活,热爱程序