数据结构 2  字符串 数组、二叉树以及二叉树的遍历

数据结构 2 字符串 数组、二叉树以及二叉树的遍历

上一节的学习中,我们已经结合JAVA 本身,将线性表所包含的顺序表、链表、栈、队列等数据结构通通学习了一番,并且将这些数据结构的一些基本操作。比如

  • add()
  • remove()
  • pop()

等等方法都进行了列举,通过这些,我们将对线性表有了一个直接的认识。这节将学习有关字符串、广义表等内容。

字符串

怎么理解字符串呢,想必大家都知道。我们在学习JAVA 8大基本类型的时候就有学习到字符串,但是JAVA 里面的字符串是一个对象 它是一个引用类型,并且初始化后,是一个不可变对象

String str = "hello";

很简单,我们通过一句代码,就可以将一个字符串常量化出来,为什么说常量化呢,这里我们没有采用new 的方式,所以这个变量其实是保存在了常量池里面。而不是堆里面。

从严格意义来说,字符串其实也是符合 线性结构 的,因为我们都知道,字符串都是由基本类型的字符 char 连接起来组成的,他们存在一对一的关系。只不过这个线性表里面存的全部都是字符类型罢了。

private final char value[];

public String() {
    this.value = "".value;
}

通过直接new 的方式,我们可以发现,构造函数里面其实是用一个字符数组来进行储存字符串的,我们这里的数组其实是一个静态数组,它不像List 一样,可以自由的变化长度,初始化了。它就确定死了,多长就多长。

字符串的储存方式

  • 普通数组定长储存(String)
  • 堆分配内存:动态数组储存(StringBuffer)
  • 链表储存
    public StringBuffer(String str) {
        super(str.length() + 16);
        append(str);
    }
------------------
    char[] value;

    AbstractStringBuilder(int capacity) {
        value = new char[capacity];
    }

    public AbstractStringBuilder append(String str) {
        if (str == null)
            return appendNull();
        int len = str.length();
        ensureCapacityInternal(count + len);
        str.getChars(0, len, value, count);
        count += len;
        return this;
    }

ensureCapacityInternal 就是进行扩容的操作。这里的Stringbuffer 就是在堆上面进行的操作。可以像线性表一样。进行扩容操作。

BF 算法

BF算法是一种最普通的算法,在指定的字符串中匹配子串,匹配到则返回子串开始的下标。这个算法在String 当中最具有代表性的就是indexOf(String str) 这个方法了。

static int indexOf(char[] source, int sourceOffset, int sourceCount,
            char[] target, int targetOffset, int targetCount,
            int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }

        char first = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

IndexOf(str) 相比于BF(暴力)还是有很多优化的地方,比如首先会判断首字符是否相同,若首字符都不相同,那直接不用说了。跳过了一些重复的地方。

image.png

image.png

n 表示子串的长度 m表示源字符串的长度

这个算法最优的时候,若直接在首位碰到,则时间复杂度 O(n)

最不幸的要是最后一位才可以碰到,则必须要循环 m*n 次 则时间复杂度 O(M*N)

数组

数组我在之前就介绍过,一种最基本的存储结构。在线性表的几种分类中。顺序表底层就是使用数组来实现的。

从本质上说,数组作为一种储存结构,而不是一种基本类型,可以理解为容纳基本类型的一个容器。

常见的一维数组,其实是很简单的,
image

指定一个一维数组,指定大小后,它的大小是不可再变的。并且数组元素的类型全部是统一的。

结构树

数据结构的树存储结构中。常用语存储一对多的数据,树结构当中,常用的还是二叉树、以及红黑树等,我这里一一介绍。

二叉树

二叉树是结构树里面最有名也是使用最多的树结构数据结构,检查一个树是否满足二叉树,从两个方面下手

  1. 每个节点下最多挂两个子节点 只能是0、1、2
  2. 树的本身是有序或者无序

如何来确定这个树是否是一个有序树还是无序树呢?

  • 按照一定的规则将节点左右分布,那就是有序树,反之则是无序树

image

二叉树规律

按照前人的总结,我们可以得出以下结论。

  • 一个深度为K 的二叉树,最多包含节点数 2的k次方-1
  • 二叉树指定n 层级所包含的节点数为 2的n-1次方

如果将二叉树在细分的话,又可以分为满二叉树与完全二叉树。

满二叉树

一听这个名字,就可以理解到。它是满(饱和)的,所以,来用画图表示一下
image.png

如果二叉树除了叶子节点以外,所有的节点的度都是2(有两个子元素),那么它就是满二叉树

完全二叉树

如果二叉树除去叶子节点是一个满二叉树,并且叶子节点从左向右依次排列。那么这就是一个完全二叉树。
image.png

但是,这样排列的却不能成为是完全二叉树。
image.png

完全二叉树性质

完全二叉树不但具有普通二叉树的性质,并且还有自己的一些独特性质。例如:

  • 具有n个节点的完全二叉树的深度是 ⌊log2n⌋+1。

二叉树的存储方式

对于满二叉树以及完全二叉树,完全可以采用数组的方式来存储,因为数组就是用来存储对于一对一线性规律的。所以完全合适
image.png

image.png

对于没有元素的位置,使用^ 空处位置。要是遇到刁钻一些的二叉树,例如下面这个,那直接很浪费空间。
image.png
这里面的灰色代表元素缺失,这样存储到数组里面的话,是很浪费内存空间的。
image.png

链式二叉树

当然,我们既然不能用数组存储,那就使用指针存储。我们知道二叉树的定义里已经规定好,儿子节点不能超过两个,并且本身还需要是一个有序树
image.png

每一个节点需要包含两个指针,用于指向左节点和右节点即可。中间则包含本节点的数据即可。这样相比于数组,我们之前也学习过链表、虽然数据不再是连续的,但是可以随意的增加节点、不会造成内存空间的浪费。

二叉树遍历

一个二叉树的遍历,是为了访问其所有的节点。有这样几种方式

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

前序遍历

通俗的说就是从二叉树的根节点出发,先访问当前节点的左节点,一直向下。直到当前节点没有左节点,再遍历右节点。
image.png

我们按照当前图所示,简单讲解一下:

  1. 从A根节点入手,打印A
  2. 访问A节点的左节点 打印B
  3. 访问当前节点的左节点,打印D
  4. D没有左右节点,本次遍历完成,访问B节点右分支 打印E
  5. E节点没有左右分支,遍历本节点结束。
  6. 遍历A节点右分支,打印C
  7. C没有左右节点,A节点遍历完成。退出循环。

以上的打印顺序应该是:ABDEC

中序遍历

中序遍历,最大的特点就是:第二次到达节点输出内容,也是从左到右的顺序,从根节点出发。

还是按照上面那张图:

  1. 从A出发,找到B
  2. 在B找到D
  3. D节点没有左右节点,打印D
  4. 第二次回到B 打印B
  5. 访问B节点右节点E
  6. E没有左右节点,第二次回到E 打印E
  7. B完成,回到A,打印A
  8. 访问A右节点C,没有左右节点直接打印C

经过以上打印访问,顺序为:DBEAC

后序遍历

后序遍历,在原有中序遍历上稍微有些不同,当第三次到达节点时,才会输出,还是按照根节点入手,从左到右的方式。

  1. A节点入手,到达B
  2. B节点左节点,到达D
  3. D节点没有左右节点,直接打印D
  4. 回到B节点,第二次到达,到E节点
  5. E节点没有左右节点,直接打印E
  6. 回到B,第三次到达,打印B
  7. 回到A 第二次到达,到达C
  8. 直接打印C,回到A 第三次到达,打印A

最后的顺序应该是:DEBCA

层序遍历

之前已经说过了有关层次的相关概念。层序遍历,主要思路是:通过借助队列,从树的根节点开始,左右节点节点入队,每次队列中一个节点出队,直到所有的节点都出队。出队的先后顺序就是遍历的结果。
image.png

按照这幅图来说明一下:

  1. 首先根节点1入队。
  2. 根节点1出队,同时将1的两个子节点2,3放入队列
  3. 队列头2出队,将2节点的两个子节点4,5放入队列
  4. 队列头3出队,同时将3的两个子节点6,7放入队列
  5. 不断循环,直到队列为空。则遍历完成。

小结

通过本节,应该了解到树这个重要的概念。以及树当中最常见的二叉树的遍历以及使用。并且了解字符串、数组等基本概念

参考

http://c.biancheng.net/view/3392.html
https://www.jianshu.com/p/a47d6ed886c8

# 二叉树 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×