数据结构与算法分析---树Java实现


树的定义(递归方式)

树的实现

class TreeNode{
    Object element;
    TreeNode firstChild;
    TreeNode nextSibling;
}

在这里插入图片描述

树的遍历

在这里插入图片描述

先序遍历(preorder travelsal)

设我们想要列出目录中所有文件的名字。输出格式将是:深度为 did_i 的文件将被 did_i 次跳格(tab)缩进后打印其名。伪码如下:

  private void listAll(int depth) {
        printName(depth);
        if (isDirectory) {
            for each file c in this directory( for each child)
            c.listAll(depth + 1);
        }
    }
    public void listAll() {
        listAll(0);
    }

这种策略叫做先序遍历(preorder travelsal)
展示如下:

在这里插入图片描述

后序遍历(postorder travelsal

计算一个目录大小的伪码历程

public int size() {
        int totalSize = sizeOfThisFile();
        if (isDirectory())
            for each file c in this directory( for each child)
                totalSize += c.size();

        return totalSize;
    }

在这里插入图片描述

二叉树


二叉树的实现

public class BinaryNode {
    Object element;   //the data in the node
    BinaryNode left;   //Left child
    BinaryNode right;  //right child
}

例子:表达式树

@(a+b*c)+((d*e+f)*g)的表达式树

二叉树的主要用处之一是在编译器的设计领域

查找树ADT——二叉查找树

二叉查找树的性质是,对于树中的每个节点X,它的左子树中所有项的值小于X中的项,而它的右子树中所有项大于X中的项。

insert 方法

在二叉查找树中 insert 方法必定会插在叶子节点上,利用递归的方式,将节点x插入到适当的子树中,代码如下:

  private BinaryNode<E> insert(E x, BinaryNode<E> t) {
        if (t == null) {
            return new BinaryNode<>(x, null, null);
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0)
            t.left = insert(x, t.left);
        else if (compareResult > 0)
            t.right = insert(x, t.right);
        else ;//Duplicate;do nothing
        return t;
    }

remove 方法

最困难的操作是 remove(删除)。

  • 如果是叶子节点,那么立即删除
  • 如果节点有一个儿子,该节点直接替换为这个儿子 t = (t.left != null) ? t.left : t.right;
  • 如果节点有二个儿子。一般的删除策咯是用其右子树的最小的数据(用findMin函数找到)代替该节点的数据并递归地删除那个最小数据的节点。

具有一个儿子的节点4删除前后情况

删除具有两个儿子的节点2前后的情况

private BinaryNode<E> remove(E x, BinaryNode<E> t) {
        if (t == null)
            return t;
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0)
            t.left = remove(x, t.left);
        else if (compareResult > 0)
            t.right = remove(x, t.right);
        else if (t.left != null && t.right != null) {
            t.element = findMin(t.right).element;
            t.right = remove(t.element, t.right);  //核心代码
        } else
            t = (t.left != null) ? t.left : t.right;
        return t;
    }

上述的删除工作效率并不高,因为它沿该树进行两趟收索以查找和删除右子树中的最小的节点,很明显右子树的删除可以写一个特殊的 removeMin 方法改变这种效率。
如果删除的次数不多,通常使用的策咯是 懒惰删除(lazy deletion):当一个元素要被删除时,它仍留在树中,而只是被标记为删除。这特别是在有重复项时很常用,因为此时记录出现频率数的域可以减1.如果树中的实际节点树和“被删除”的节点数相同,那么树的深度预计只上升一个小的常数,因此,存在一个与懒惰删除相关的非常小的时间损耗。再有,如果被删除的项是重新插入的,那么分配一个新单元的开销就避免了。

二叉树github

AVL树

单旋转

@单旋转|center

下面 假设从初始的空AVL树开始插入关键字 3、2和1,然后依序插入4~7。在插入1时第一个问题出现,AVL性质在根处被破坏。我们在根与其左儿子之间实行单旋转修正这个问题。
center
图中虚线连接的两个节点,它们是旋转的主体。下面我们插入关键字4的节点,这没有问题,但插入5会破坏在节点3处的AVL性质,通过单旋转将其改正。
center
下面插入6,因为左边子树的高度为0而右子树的高度为2,因此在根处2和4之间实施一次单旋转
Alt text
旋转结果使得2是4的一个儿子,而4原来的左子树变成节点2的新的右子树。下面插入一个关键字7,它导致另外的旋转。
Alt text

private AvlNode<E> rotateWithLeftChild(AvlNode<E> k2) {
        AvlNode<E> lChild = k2.left;
        k2.left = lChild.right;
        lChild.right = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        lChild.height = Math.max(height(lChild.left), k2.height) + 1;
        return lChild;
    }
    private AvlNode<E> rotateWithRightChild(AvlNode<E> k2) {
        AvlNode<E> rChild = k2.right;
        k2.right = rChild.left;
        rChild.left = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        rChild.height = Math.max(height(rChild.right), k2.height) + 1;
        return rChild;
}

双旋转

单旋转对于某些情形并没有减低他的深度。这时需要双旋转。
继续前面的例子基础上以倒序插入关键字10~16,接着插入8,9。插入16简单
,并没有破坏性质,但插入15后会引起节点7处的高度不平衡。需要通过右-左旋转解决。
Alt text
下面插入14,也需要一个双旋转。此时需要右-左旋转。
Alt text
下面插入 13,那么会在根处产生一个不平衡。由于13不在4和7之间,因此一次单旋转就能完成修正工作。
Alt text
插入12、11都需要单旋转结果如下
Alt text
最后插入9演示双旋转的对称情形。
Alt text

 private AvlNode<E> doubleWithLeftChild(AvlNode<E> k3) {
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }

    private AvlNode<E> doubleWithRightChild(AvlNode<E> k1) {
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }

平衡树操作

平衡的操作很简单,首先判断节点是否失去平衡(左子树与右子树的高度查大于*ALLOW_IMBLANCE = 1 * ,并判断其需要进行旋转的类型进行相应的旋转操作,最后不要忘记重新计算树的高度。操作很清晰

private AvlNode<E> balance(AvlNode<E> t) {
        if (t == null) return t;
        if (height(t.left) - height(t.right) > ALLOWED_IMBLANCE)
            if (height(t.left.left) >= height(t.left.right))
                t = rotateWithLeftChild(t);
            else
                t = doubleWithLeftChild(t);
        else if (height(t.right) - height(t.left) > ALLOWED_IMBLANCE)
            if (height(t.right.right) >= height(t.right.left))
                t = rotateWithRightChild(t);
            else
                t = doubleWithRightChild(t);
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        return t;
    }

插入操作

插入操作都是插入到节点,最主要的是插入后的调节平衡,需要从下向上进行调节平衡操作。

private AvlNode<E> insert(E x, AvlNode<E> t) {
        if (t==null)
            return new AvlNode<>(x,null,null);
        int compareResult=x.compareTo(t.element);
        if (compareResult>0)
            t=insert(x,t.right);
        else if (compareResult<0)
            t=insert(x,t.left);
        else ;
        return balance(t);
}

删除操作

删除操作最为复杂,首先找到要删除的节点,判断是否含有左右子树,若含有左右子树,通常取右子树的最小的节点接替本节点,需要调用findMin()函数,如下:

  private AvlNode<E> findMin(AvlNode<E> t) {
        if (t == null) {
            return t;
        }
        while (t.left != null) t = t.left;
        return t;
    }

当含有左子树,将右子树作为本节点。否则将左子树作为本节点(包括左右节点都不存在)。
t=(t.left!=null)?t.left:t.right;

remove()全部代码:

private AvlNode<E> remove(E x, AvlNode<E> t) {
        if (t==null)return t;
        int compareResult=x.compareTo(t.element);
        if (compareResult>0)
            t=remove(x,t.right);
        else if (compareResult<0)
            t=remove(x,t.left);
        else if (t.left!=null&&t.right!=null){
            t.element=findMin(t.right).element;
            t.right=remove(t.element,t.right);
        }else
            t=(t.left!=null)?t.left:t.right;
        return balance(t);
    }

AVL树的github代码

版权声明:本文为qq_37976565原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_37976565/article/details/88651618

智能推荐

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

猜你喜欢

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...

[国家集训队]小Z的袜子(莫队)

[国家集训队]小Z的袜子 题目描述 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这NN只袜子从1到NN编号,然后从编号LL到RR(LL 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同...