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)。二叉树常被用于实现二叉查找树和二叉堆。

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

拿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,此时满足这个条件就是满二叉树.

完全二叉树:

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

平衡二叉树:

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

二叉树的遍历:

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

先序:

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

中序:

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

后序:

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

树图:

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

下面开始上代码:

由于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

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

根据函数,先打印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

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

举例: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

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

举例:走向顺序为 左遍历 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);//通过循环调用递归索引方法访问节点完成方法.

}

}

通过深度的索引:

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.分清遍历顺序和访问顺序的不同.

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

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

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