Java教程

数据结构与算法(九)

本文主要是介绍数据结构与算法(九),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

树结构基础部分

二叉树

为什么需要该数据结构

数组存储方式的分析
  • 优点:

    • 通过 下标 方式访问元素,速度快
    • 对于 有序数组,还可以使用二分查找提高检索速度
  • 缺点:如果要检索具体某个值或插入值(按一定顺序)会整体移动,效率较低,如下的示意图

链表存储方式的分析

优点:在一定程度上对数组存储方式有优化

例如:插入一个数值节点,只需要将插入节点,链接到链表中即可,同理,删除效率也很好

  • 缺点:检索效率较低

    需要从头结点开始遍历查找。

简单说:

  • 数组访问快,增删慢
  • 链表增删快,访问慢

那么就出现了 这种数据结构

树存储数据方式分析

提供数据 存储读取 效率。

例如:利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也可以保证数据的插入删除修改 的速度

如图所示:

  • 插入时,小的数在 左节点、大的数在 右节点
  • 查找时:根据插入事的特性,基本上就类似折半查找了,每次都过滤一半的节点
  • 删除时:只需要移动相邻的节点的引用

树的常用术语

  • 节点:每一个圆圈表示一个节点,也称节点对象

  • 根节点:最上面,最顶部的那个节点,也就是一棵树的入口

  • 父节点:有子节点的节点

  • 子节点

  • 叶子节点:没有子节点的节点

  • 节点的权:可以简单的理解为节点值

    有时候也用 路径 来表示

  • 路径:从 root 节点找到该节点的路线

  • 子树:有子节点的父子两层就可以称为是一个子树

  • 树的高度:最大层数

  • 森林:多颗子树构成森林

二叉树的概念

  • 树有很多种,每个节点 最多只能有两个子节点 的一种形式称为 二叉树

  • 二叉树的子节点分为 左节点右节点

  • 如果该二叉树的所有 叶子节点 都在 最后一层,并且 节点总数 = 2^n-1 (n 为层数),则我们称为 满二叉树

  • 如果该二叉树的所有叶子节点都在最 后一层或倒数第二层,而且 最后一层的叶子节点在左边连续倒数第二层的叶子节点在右边连续,我们称为 完全二叉树

二叉树的遍历说明

有三种:

  • 前序遍历:先输出父节点,再遍历左子树(递归)和右子树(递归)
  • 中序遍历:先遍历左子树(递归),再输出父节点,再遍历右子树(递归)
  • 后序遍历:先遍历左子树(递归),再遍历右子树(递归),最后输出父节点

前、中、后序主要区别是输出父节点的时间来区分

二叉树遍历思路分析

  • 前序遍历:

    1. 先输出当前节点(初始节点是 root 节点)
    2. 如果左子节点不为空,则递归继续前序遍历
    3. 如果右子节点不为空,则递归继续前序遍历

    上图的输出顺序为:1、2、3、4

  • 中序遍历:

    1. 如果当前节点的左子节点不为空,则递归中序遍历
    2. 输出当前节点
    3. 如果当前节点的右子节点不为空,则递归中序

    上图的输出顺序为:2、1、4、3

  • 后序遍历:

    1. 如果左子节点不为空,则递归继续前序遍历
    2. 如果右子节点不为空,则递归继续前序遍历
    3. 输出当前节点

    上图的输出顺序为:2、4、3、1

遍历代码实现

//定义节点
class HeroNode{
    private int no;//当前节点编号
    private String name;//当前节点名字
    private HeroNode left;//当前节点左子树
    private HeroNode right;//当前节点右子树

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
    //前序遍历
    public void preOrder(){
        //先输出当前节点
        System.out.println(this);
        //递归遍历左子节点
        if(this.left != null){
            this.left.preOrder();
        }
        //递归遍历右子节点
        if(this.right != null){
            this.right.preOrder();
        }
    }

    //中序遍历
    public void infixOrder(){
        //先输出左子树
        if(this.left != null){
            this.left.infixOrder();
        }
        //输出当前节点
        System.out.println(this);
        //输出右子树
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    //后序遍历
    public void postOrder(){
        //先输出左子树
        if(this.left != null){
            this.left.postOrder();
        }
        //输出右子树
        if(this.right != null){
            this.right.postOrder();
        }
        //输出当前节点
        System.out.println(this);
    }
}
//创建二叉树
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序遍历
    public void preOrder(){
        if(this.root != null){
            this.root.preOrder();
        }else{
            System.out.println("当前二叉树为空");
        }
    }
    //中序遍历
    public void infixOrder(){
        if(this.root != null){
            this.root.infixOrder();
        }else{
            System.out.println("当前二叉树为空");
        }
    }
    //后序遍历
    public void postOrder(){
        if(this.root != null){
            this.root.postOrder();
        }else{
            System.out.println("当前二叉树为空");
        }
    }
}

//创建二叉树
BinaryTree binaryTree = new BinaryTree();

//手动创建二叉树
HeroNode root = new HeroNode(1,"宋江");
HeroNode hero1 = new HeroNode(2,"吴用");
HeroNode hero2 = new HeroNode(3,"卢俊义");
HeroNode hero3 = new HeroNode(4,"林冲");
root.setLeft(hero1);
root.setRight(hero2);
hero2.setRight(hero3);
binaryTree.setRoot(root);

//遍历二叉树
System.out.println("前序遍历");
binaryTree.preOrder();
//中序遍历
System.out.println("中序遍历");
binaryTree.infixOrder();
//后序遍历
System.out.println("后序遍历");
binaryTree.postOrder();

二叉树查找

要求:

  1. 编写前、中、后序查找方法
  2. 并分别使用三种查找方式,查找 id=5 的节点
  3. 并分析各种查找方式,分别比较了多少次

由于二叉树的查找是遍历查找,所以就简单了,前面遍历规则已经写过了,改写成查找即可

//在节点中增加查找方法
//前序查找
public HeroNode preOrderSearch(int no){
    if(this.no == no){
        return this;
    }
    HeroNode resNode = null;
    if(this.left != null){
        resNode = this.left.preOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }

    if(this.right != null){
        resNode = this.right.preOrderSearch(no);
    }

    return resNode;
}

//中序查找
public HeroNode infixOrderSearch(int no){
    HeroNode resNode = null;
    if(this.left != null){
        resNode = this.left.infixOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }
    if(this.no == no){
        return this;
    }
    if(this.right != null){
        resNode = this.right.infixOrderSearch(no);
    }
    return resNode;
}

//后序查找
public HeroNode postOrderSearch(int no){
    HeroNode resNode = null;
    if(this.left != null){
        resNode = this.left.postOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }

    if(this.right != null){
        resNode = this.right.postOrderSearch(no);
    }
    if(resNode != null){
        return resNode;
    }
    if(this.no == no){
        return this;
    }
    return null;
}
//在二叉树中增加查找方法
//前序查找
public HeroNode preOrderSearch(int no){
    HeroNode resNode = null;
    if(this.root != null){
        resNode = this.root.preOrderSearch(no);
    }else{
        System.out.println("当前二叉树为空");
    }
    return resNode;
}

//中序
public HeroNode infixOrderSearch(int no){
    HeroNode resNode = null;
    if(this.root != null){
        resNode = this.root.infixOrderSearch(no);
    }else{
        System.out.println("当前二叉树为空");
    }
    return resNode;
}
//后序
public HeroNode postOrderSearch(int no){
    HeroNode resNode = null;
    if(this.root != null){
        resNode = this.root.postOrderSearch(no);
    }else{
        System.out.println("当前二叉树为空");
    }
    return resNode;
}

可以看出:

  • 找到的次数和 查找的顺序 有关,而查找顺序就是哪一序有关
  • 找不到的次数则是相当于都遍历完成,所以是相等的次数

二叉树删除

要求:

  1. 如果删除的节点是 叶子节点,则删除该节点
  2. 如果删除的节点是非叶子节点,则删除该子树

测试:删除 5 号叶子节点和 3 号子树。

说明:目前的二叉树不是规则的,如果不删除子树,则需要考虑哪一个节点会被上提作为父节点。这个后续讲解排序二叉树时再来实现。先实现简单的

思路分析:

  • 由于我们的二叉树是单向的

  • 所以我们判定一个节点是否可以删除,是判断它的 子节点,是否可删除,否则则没法回到父节点删除了,因为要判断被删除的节点满足前面的两点要求

    1. 当前节点的 左子节点 不为空,并且左子节点就是要删除的节点,则 left = null,并且返回(结束递归删除)
    2. 当前节点的 右子节点 不为空,并且右子节点就是要删除的节点,则 right = null,并且返回(结束递归删除)

    如果前面都没有删除,则继续递归删除。上面的要求是 2 点,实际上是,找到符合条件的节点则直接删除(因为不考虑是否有子树)

    如果树只有一个 root 节点,则将 root 节点置空

//节点中增加删除方法
public void delete(int no){
    if(this.left != null){
        if(this.left.no == no){
            this.left = null;
            return;
        }
    }

    if(this.right != null){
        if(this.right.no == no){
            this.right = null;
            return;
        }
    }

    //向左递归
    if(this.left != null){
        this.left.delete(no);
    }

    //向右递归
    if(this.right != null){
        this.right.delete(no);
    }
}
//二叉树中增加删除方法
public void delete(int no){
    if(this.root != null){
        if(this.root.getNo() == no){
            this.root = null;
            return;
        }else{
            this.root.delete(no);
        }
    }else{
        System.out.println("当前二叉树为空");
    }
}

顺序存储二叉树

基本概念

从数据存储来看,数组存储 方式和 的存储方式可以 相互转换。即使数组可以转换成树,树也可以转换成数组。如下示意图

上图阅读说明:

  • 圆圈顶部的数字对应了数组中的索引
  • 圆圈内部的值对应的数数组元素的值

现在有两个要求:

  1. 上图的二叉树的节点,要求以数组的方式来存储 arr=[1,2,3,4,5,6,7]
  2. 要求在遍历数组 arr 时,仍然可以以 前序、中序、后序的方式遍历

特点

想要 实现上面的两个要求,需要知道顺序存储二叉树的特点:

  1. 顺序二叉树 通常只考虑 完全二叉树
  2. 第 n 个元素的 左子节点2*n+1
  3. 第 n 个元素的 右子节点2*n+2
  4. 第 n 个元素的 父节点(n-1)/2

注:n 表示二叉树中的第几个元素(按 0 开始编号)

比如:

  • 元素 2 的左子节点为:2 * 1 + 1 = 3,对比上图去查看,的确是 3
  • 元素 2 的右子节点为:2 * 1 + 2 = 4,也 就是元素 5
  • 元素 3 的左子节点为:2 * 2 + 1 = 5,也就是元素 6
  • 元素 3 的父节点为: (2-1)/2= 1/2 = 0,也就是根节点 1

三种遍历方式

//顺序存储二叉树
class ArrayBinaryTree{
    private int[] array;

    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }
    //前序遍历输出顺序存储二叉树
    public void preOrder(int index){
        if(array == null || array.length == 0){
            System.out.println("数组为空,不能遍历完全二叉树");
        }
        //先输出当前元素
        System.out.println(array[index]);
        //再递归输出左子元素
        if((index*2+1) < array.length){
            preOrder((index*2 + 1));
        }
        //再递归输出右子元素
        if((index*2+2) < array.length){
            preOrder((index*2 +2));
        }
    }
    public void preOrder(){
        preOrder(0);
    }
    //中序遍历输出顺序存储二叉树
    public void infixOrder(int index){
        if(array == null || array.length == 0){
            System.out.println("数组为空,不能遍历完全二叉树");
        }
        if((index*2 +1) < array.length){
            infixOrder((index*2 + 1));
        }
        System.out.println(array[index]);
        if((index*2 + 2) < array.length){
            infixOrder((index*2+2));
        }
    }
    public void infixOrder(){
        infixOrder(0);
    }

    //后序遍历顺序存储二叉树
    public void postOrder(int index){
        if(array == null || array.length == 0){
            System.out.println("数组为空,不能遍历完全二叉树");
        }
        if((index*2 + 1) < array.length){
            postOrder((index*2+1));
        }
        if((index*2 + 2) < array.length){
            postOrder((index*2+2));
        }
        System.out.println(array[index]);
    }
    public void postOrder(){
        postOrder(0);
    }
}

线索化二叉树

引出线索化二叉树

看如下问题:将数列 {1,3,6,8,10,14} 构成一颗二叉树

可以看到上图的二叉树为一颗 完全二叉树。对他进行分析,可以发现如下的一些问题:

  1. 当对上面的二叉树进行中序遍历时,数列为 8,3,10,1,14,6
  2. 但是 6,8,10,14 这几个节点的左右指针,并没有完全用上

如果希望充分利用各个节点的左右指针,让各个节点可以 指向自己的前后节点,这个时候就可以使用 线索化二叉树

介绍

n 个节点的二叉树链表中含有 n + 1 个空指针域,他的推导公式为 2n-(n-1) = n + 1

利用二叉链表中的空指针域,存放指向该节点在 某种遍历次序 *下的 **前驱** 和 **后继** 节点的指针,这种附加的指针称为*「线索」

  • 前驱:一个节点的前一个节点
  • 后继:一个节点的后一个节点

如下图,在中序遍历中,下图的中序遍历为 8,3,10,1,14,6,那么 8 的后继节点就为 3,3 的后继节点是 10

这种加上了线索的二叉树链表称为 线索链表(节点存储了下一个节点,组成了链表,并且一般的二叉树本来就是用链表实现的),相应的二叉树称为 线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为:前、中、后序线索二叉树。

思路分析

将上图的二叉树,进行 中序线索二叉树,中序遍历的数列为 8,3,10,1,14,6

那么以上图为例,线索化二叉树后的样子如下图

  • 的后继节点为 3
  • 3 由于 左右节点都有元素,不能线索化
  • 10 的前驱节点为 3,后继节点为 1
  • 1 不能线索化
  • 14 的前驱节点为 1,后继节点为 6
  • 6 有左节点,不能线索化

注意:当线索化二叉树后,那么一个 Node 节点的 left 和 right 属性,就有如下情况:

  1. left 指向的是 左子树,也可能是指向 前驱节点

    例如:节点 1 left 节点指向的是左子树,节点 10 的 left 指向的就是前驱节点

  2. right 指向的是 右子树,也可能是指向 后继节点

    例如:节点 3 的 right 指向的是右子树,节点 10 的 right 指向的是后继节点

代码实现

//创建节点
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;
    //左右子树的类型,如果是左右子树就是0,如果是前驱或者后继节点就是1
    private int leftType;
    private int rightType;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
//创建线索化二叉树
class ThreadBinaryTree{
    private HeroNode root;//表示跟节点
    private HeroNode pre;//表示前驱节点

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    public void threadedNodes(){
        threadedNodes(root);
    }
    //中序线索化遍历
    public void threadedList(){
        if(root == null){
            System.out.println("线索化二叉树为空");
            return;
        }
        HeroNode node = root;
        while(node != null){
            //找到第一个有前驱节点的元素
            while(node.getLeftType() != 1){
                node = node.getLeft();
            }
            //输出第一个元素
            System.out.println(node);
            //当有后继节点的情况会进入
            while(node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            //当一个节点没有后继节点的时候直接获取右子树
            node = node.getRight();
        }
    }

    //中序线索化
    public void threadedNodes(HeroNode node){
        if(node == null){
            return;
        }
        //先线索化左子树
        threadedNodes(node.getLeft());
        //再线索化当前节点
        /*
        * 1.设置前驱节点,
        * 2.设置后继节点
        * */
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //线索化后继节点,需要遍历到下一个节点的时候,通过下一个节点设置
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //将前驱节点后移
        pre = node;
        //线索化右子树
        threadedNodes(node.getRight());

    }
}

前序线索化和遍历

//前序线索化
public void preThreadedNodes(HeroNode node){
    if(node == null){
        return;
    }
    //先序列化自己
    if(pre != null && node.getLeft() == null){
        node.setLeft(pre);
        node.setLeftType(1);
    }

    if(pre != null && pre.getRight() == null){
        pre.setRight(node);
        pre.setRightType(1);
    }

    pre = node;
    //再序列化递归左子树
    if(node.getLeftType() == 0){
        preThreadedNodes(node.getLeft());
    }
    //再递归序列化右子树
    if(node.getRightType() == 0){
        preThreadedNodes(node.getRight());
    }
}
//前序序列化遍历
public void preThreadedList(){
    if(root == null){
        System.out.println("线索化二叉树为空");
        return;
    }
    HeroNode node = root;
    while(node != null){
        System.out.println(node);
        while(node.getLeftType() == 0){
            node = node.getLeft();
            System.out.println(node);
        }
        while (node.getRightType() == 1) {
            node = node.getRight();
            System.out.println(node);
        }
        node = node.getRight();
    }
}
这篇关于数据结构与算法(九)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!