当前位置:   article > 正文

java树杈_数据结构-线性表与二叉树(JAVA实现)

java树杈_数据结构-线性表与二叉树(JAVA实现)

数据结构:

集合:

1).确定性(集合中的元素必须是确定的)

2).互异性(集合中的元素互不相同。例如:集合A={1,a},则a不能等于1)

3).无序性(集合中的元素没有先后之分),如集合{3,4,5}和{3,5,4}算作同一个集合。

线性结构:

线性表,栈,队列,双队列,数组,串。

线性表:

线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。

一、线性结构:

如果一个数据元素序列满足:

(1)除第一个和最后一个数据元素外,每个数据元素只有一个前驱数据元素和一个后继数据元素;

(2)第一个数据元素没有前驱数据元素;

(3)最后一个数据元素没有后继数据元素。

则称这样的数据结构为线性结构。

前驱元素:以an为例,an-1为前驱元素

后继元素:以a0为例,a0+1为后继元素

操作:

1.求元素个数

2.插入

3.删除

4.查找

5.判断是否为空

1)顺序表:

计算机有两种基本的存储结构(物理存储结构):顺序结构、离散结构。使用顺序结构实现的线性表称为顺序表。

栈内存的存储是顺序结构,堆内存的存储是离散结构。

所以我们平时说的栈空间是连续的就是这个意思.

顺序表的例子:

package structure;

/**

* 线性表操作接口

*/

public interface List {

/**

* @return 返回值为顺序表的元素个数

*/

int size();

/**

* 性表下标插入元素

* @param index 顺序表下标

* @param Obj 顺序表数组

* @return

*/

void insert(int index,Object Obj)throws Exception;

/**

* 通过数组下标删除元素

* @param index 数组下标

*/

void delete(int index)throws Exception;

/**

* 通过数组下标获得元素值

* @param index 数组下标

* @return

*/

Object select(int index)throws Exception;

/**

*

* 判断是否为空

* @param obj 顺序表数组

* @return true 空 false 不为空

*/

boolean isEmpty();

}

package structure;

/**

*

顺序表

*/

public class SequenceList implements List {

//默认长度为100

public final int defaultSize=100;

//最大长度

public int maxsize;

//当前长度

public int size;

//数组

Object[] arrayList;

/**

初始化方法

size为传进来的期望数组长度

*/

public void init(int size){

maxsize=size;//将期望数组长度赋值给最大数组长度

this.size=0;//当前数组长度为0

arrayList =new Object[maxsize];/ma过传递进来的最大长度进行初始化,构建数组.

}

//无参构造,当没有指定的时候,就用默认数组长度代替最大数组长度.

实现:

public SequenceList(){

init(defaultSize);//通过默认长度进行数组构建

}

public SequenceList(int size){

init(size);//通过指定长度进行数组构建

}

/**

* @return 返回值为顺序表的元素个数

*/

@Override

public int size() {

return size; //直接返回当前数组长度.

}

/**

* 判断是否为空

*

* @param obj 顺序表数组

* @return true 空 false 不为空

*/

@Override

public boolean isEmpty() {

return size==0;//当,当前数组长度为0时, 返回空, 否则返回失败.

}

/**

* 线性表下标插入元素

*

* @param index 顺序表个数

* @param Obj 顺序表数组

* @return

*/

@Override

public void insert(int index, Object obj) throws Exception {

if(isEmpty()){

//为空

throw new Exception("顺序表为空无法插入");

}

if(maxsize==index){

throw new Exception("顺序表已满,无法插入");

}

if(index<0||index>size){

throw new Exception("参数错误,不在范围之内");

}

//上边为错误检测,下边开始进行真正的插入操作

//线性表在中间插入数据,要将后续所有元素的数据往后移动,所以非常消耗资源.

for(int i=size-1;i>=index;i--){

arrayList[i+1]=arrayList[i];

//这里借助线性表的特性,先定义好全部空间,从当前的最后一个元素向后移动,省去了中间变量赋值的环节,从后向前进行移动.

//直至移动完需要插入的元素下标

}

arrayList[index]=obj;//此时index下标内数值为无用数值,可以进行数据的更新.

size++;//更新后,增加了一个元素 自然需要增加一个长度单位.

}

/**

* 通过数组下标删除元素

*

* @param index 数组下标

*/

@Override

public void delete(int index)throws Exception {

if(isEmpty()){

//为空

throw new Exception("顺序表为空无法删除");

}

if(index<0||index>size-1){

throw new Exception("参数错误,不在范围之内");

}

for(int i=index; i<=size-1;i++){

arrayList[i]=arrayList[i+1];

}

size--;

}

/**

* 通过数组下标获得元素值

*

* @param index 数组下标

* @return

*/

@Override

public Object select(int index)throws Exception {

if(isEmpty()){

//为空

throw new Exception("顺序表为空无法删除");

}

if(index<0||index>size){

throw new Exception("参数错误,不在范围之内");

}

return arrayList[index];

}

}

关于算法的复杂度这方面:

现在了解还不够深刻,我参考的原文章下面有,待自己理解透彻后会补齐.

栈:

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

摘自百度百科

存储特性:先进后出,

入栈:将元素放入栈内.

想象栈是竖着曼妥思糖(纸筒装),你只有先吃掉或者拿掉上边的,才能吃掉下边的口味.

原理是一样的.

队列:

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

存储特性:只允许在前端删除,只允许在后端插入.

队列插入操作:入队列

队列的删除操作:出队列

队列这个名字很形象,很好的诠释了这个数据结构的形象,在排队购买东西的时候,只有第一个人能进行购买操作,而后续来买东西的人,要排在队尾,和这个数据结构的插入特性一模一样.

树形结构:

树形结构是一层次的嵌套结构。 一个树形结构的外层和内层有相似的结构, 所以这种结构多可以递归的表示。经典数据结构中的各种树状图是一种典型的树形结构:一颗树可以简单的表示为根, 左子树, 右子树。 左子树和右子树又有自己的子树。

我们在此只讨论数据结构中的二叉树.

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

c75c10385343fbf2be06d804bc7eca8065388fea.jpg

每一个数字代表一个节点:

拿1,2,3三个节点来举例.

父节点:1是2和3的父节点

子节点:2和3是1的子节点

左子树:2是1的左子树

右子树:3是1的右子树

兄弟节点:2和3为兄弟节点

堂兄节点:4,6这样在同一层上面的为堂兄节点.

深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0;

高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0;

定义摘自维基百科

二叉树的类型:

满二叉树:

满二叉树就是每一个父节点下的子节点都挂满了,不存在残缺的情况.

举例:我们将初始节点的深度K设为0.子节点个数就应该是2的K+1次方-1,此时满足这个条件就是满二叉树.

359b033b5bb5c9ea5b353f93d539b6003bf3b3ff.jpg

完全二叉树:

每层结点都完全填满,在最后一层上如果不是满的,则只缺少右边的若干结点。

3801213fb80e7bec26a434f7242eb9389b506bad.jpg

平衡二叉树:

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉树的遍历:

我们按先序,中序,后序三种方法来进行演示.

先序:

访问顺序:首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树

中序:

访问顺序:首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树.

后序:

访问顺序:首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根

树图:

88f1d9f624055afe6591f862b317dbc4.png

在这个博客找到了一颗歪七扭八的树,用来当例子不错, 就粘过来了.

下面开始上代码:

由于java里面没有指针,就拿对象来代替了,本质上是一样了,都是指向引用对象地址.

节点结构:

//树结构

public class Node {

public Node lchild;//左节点

public Node rchild;//右节点

public int data;//节点所存数据

public Node(int data,Node lchild, Node rchild) {

this.lchild = lchild;

this.rchild = rchild;

this.data = data;

}

}

遍历方法:

这里方法我将和案例结合分发,全部用递归,因为看起来简洁,简单,遍历顺序都是从左到右,区别是访问节点的时机不同,访问根的时候,就是访问节点的时机.

测试代码会放在最后, 先解析每种遍历方式.

先序遍历:

// 先序:

// 访问顺序:首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树

//这里顺序就是根左右

public void dlrTraversal(Node root){

System.out.println(root.data);

if(root.lchild!=null){

dlrTraversal(root.lchild);

}

if(root.rchild!=null){

dlrTraversal(root.rchild);

}

}

先序遍历输出结果:631254978

88f1d9f624055afe6591f862b317dbc4.png

先序遍历是访问结点均是第一次经过结点时进行的.

根据函数,先打印A,然后进入B节点 打印B, 然后继续循环打印到D,左遍历结束开始遍历D的右子树, 循环这个过程,最后打印出来就是631254978.

中序遍历:

// 中序:

//

// 访问顺序:首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树

// 这里顺序以左,根,右为例.

public void ldrTraversal(Node root){

//先访问左子树到底,然后访问根,然后访问右子树.

if(root.lchild!=null){

ldrTraversal(root.lchild);

}

System.out.print(root.data);//打印左子树

if(root.rchild!=null){

ldrTraversal(root.rchild);

}

}

打印结果:123456789

88f1d9f624055afe6591f862b317dbc4.png

遍历顺序不变,打印时,在该节点无左树的时候打印根,然后遍历右节点.

举例:1节点时候,无左子树,访问根并打印. 遍历右子树,右子树2这个节点无左子树,访问根节点.以此类推,又知执行顺序从左到右.

故结果为:123456789

后序遍历:

// 后序:

//

// 访问顺序:首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根

public void lrdTraversal(Node root){

if(root.lchild!=null){

lrdTraversal(root.lchild);

}

if(root.rchild!=null){

lrdTraversal(root.rchild);

}

System.out.print(root.data);//打印根树

}

打印结果:214538796

88f1d9f624055afe6591f862b317dbc4.png

遍历顺序不变,打印时,在遍历完左右节点后,再进行节点的资源访问.

举例:走向顺序为 左遍历 6-3-1 左空 遍历右 1-2 2节点左右均空,访问本节点, 打印2.

结果返回后证明下边节点(此时是1的右子树)已经遍历访问结束,进行本节点打印 以此类推.

最终结果为:214538796

层序遍历:

层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

我们要进行同层访问,就要知道怎么索引到相应位置,这时候我们需要一个连接工具.

这个工具就是:我们需要树的深度, 通过树的深度才可以进行遍历:

下面上代码:

树的深度计算:

public int deep(Node root){

if(root==null){

return 0;//先判断是否是空树

}

int l =deep(root.lchild);//递归计算左边深度

int r =deep(root.rchild);//递归计算右边深度

if(l>r){

return l+1;//左边比较深的时候左边+1

}else{

return r+1;//右边比较深的时候右边+1

}

}

当递归执行完毕之后,左右两边树的深度也计算完成了,最后返回的就是树的最大深度.

树深度的利用(最后调用的方法):

public void levelTrav(Node root){

if(root==null){

return ;

}

int deep = deep(root);//计算深度

for(int i=1;i<=deep;i++){

levelTrav(root,i);//通过循环调用递归索引方法访问节点完成方法.

}

}

88f1d9f624055afe6591f862b317dbc4.png

通过深度的索引:

public void levelTrav(Node root,int deep){

if(root==null || deep<1){

return;

}

if(deep==1){

System.out.println(root.data);//当深度为1的时候打印当前节点,同时作为递归最后的限制条件和出口.

return;

}

levelTrav(root.lchild,deep-1);//传入节点的左子树,同时深度减一,图中也就是向左子树进行移动.

levelTrav(root.rchild,deep-1);//传入节点的左子树,同时深度减一,图中也就是向右子树进行移动.

}

打印输出结果为:639157248

执行思路举例:

通过调用递归层方法的那层方法可知,由根节点开始,一次向下,主要容易产生困惑的点应该是最后索引这块的利用.

当第一次传入进来时: 深度为1,打印根节点,return弹出.

第二次传入时:深度为2,传入左节点,同时深度参数-1, 此时到达B也就是3的位置,参数为1,打印本节点,并且return,开始执行右子树方法,逻辑相同.

第三次传入时:深度为3,此时传入左节点到达B,深度为2, 不符合跳出条线,再调用自己,传入左节点到达D,深度为1,符合条件,打印当前节点,return跳出,右边方法以此类推.

tips:把深度想象成在森林里面防止迷路的线, 通过这根线可以准确的索引到目的地.

深度为线,循环方法每一次指定线的长度,最后递归方法决定我们寻找目的地的顺序和思路.

总结:

个人觉得理解这个递归的二叉树的小技巧:

1.记住遍历顺序是从左到右.

2.什么时候访问到了最深的子节点,下面再无节点这个条件.

无论是左子树还是右子树都是一样的,他们的本质都是一个节点,当左子树没有指向时,这个节点的左树杈就空了, 右子树同理.

3.分清遍历顺序和访问顺序的不同.

遍历顺序一直没有变,变的是数据的访问顺序,无论是先序遍历,中序遍历,还是后序遍历,遍历思想是相同的,只是对对象的访问时机不同.

相同图片插入次数比较多,是为了方便大家对比观看,请见谅.

数据结构这方面还比较稚嫩,有错误请及时指出,会听取意见尽快改正.

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/427283
推荐阅读
相关标签
  

闽ICP备14008679号