树和链表

链表和树小结

链表和树都是数据结构的一种，它们的结构有类似的地方，节点中都由两个部分组成，一个时数据区域，一个指向其他节点的引用。

对于链表来说，它一般可以分为单链表，循环链表和双向链表。下面是单链表的具体java实现。

单链表中节点类有两个属性，一个是节点的数据内容，另一个是节点的引用。剩下的就是设置节点数据和引用之类的方法。

public class LinkNode{

private Object obj;//数据区域

private LinkNode next;//引用下一个节点

//构造方法，初始化

public LinkNode(Object data,LinkNode next){

this.obj=data;

this.next=next;

}

public Object getData(){

return obj;

}

public LinkNode getNext(){

return next;

}

public void setData(Object data){//设置节点数据

obj=data;

}

public void setNext(LinkNode next){//设置下一个节点

this.next=next;

}

}

有了节点类，我们就可以给这个构造一个链表了，下面是链表的一些方法：

//添加节点的方法

public void addNode(LinkNode NN){

if(root==null){

root=NN;

end=root;

}

else{

end.setNext(NN);//将没加NN之前的节点的引用指向NN

end=NN;//NN为尾节点

}

size++;

}

//在制定位置插入节点的方法

public void insertNode(LinkNode N,int index){

/*如果直接将index前的引用指向被插入的对象，那么原来index后的数据就会丢失，所以要先要将要插入的对象的引用指向index后面的数据，之

后再做第一步*/

LinkNode bb = null;

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

bb=root.getNext();//得到index前的节点

}

N.setNext(bb.getNext());

bb.setNext(N);

size++;

}

//删除制位置的节点

public void deleteNode(int index){

LinkNode bb=null;

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

bb=root.getNext();

}

bb.setNext(bb.getNext().getNext());

size--;

}

相对于链表来说，树只不过是节点中的引用更丰富罢了，一个节点中可以有多个引用指向不同的子节点。而二叉树就是节点最多有两个子树且有左右之分的树。

对于二叉树中的值，我们可以通过前，中，后以及层次遍历取得节点中的值，比如我们构造了一个java二叉树来存储这个算术式：2*10-8/(2+2)。

先构建树：

public class TreeNode <E>{

private TreeNode <E> Parent;

private TreeNode<E> LChild;

private TreeNode<E> RChild;//右孩子

private E e;//节点中的数据对象

public TreeNode(E e){

this.e=e;

}

//设置父节点，左右孩子节点

public TreeNode setParent(TreeNode<E> Parent){

this.Parent=Parent;

return Parent;

}

public TreeNode setLChild(TreeNode<E> LChild){

this.LChild=LChild;

return LChild;

}

public TreeNode setRChild(TreeNode<E> RChild){

this.RChild=RChild;

return RChild;

}

public E getE(){

return e;

}

}

有时候我们可以很简单的这样建树

public class Node <E>{

private E e;

private Node LChild;

private Node RChild;

//这里LChild和RChild直接为节点的属性.

public Node(E e){

this.e=e;

}

}

为了能够中序遍历打出这个算术式，我们按照特定的方式添加节点，那么，对于得到的树，我们如何中序遍历呢？没错，就是递归。

public void traverse（TreeNode node）{

if(e！=null){

traverse（node.getLChild()）；

Str+=(E)node.getE();

Traverse (node.getRChild());

}

else

{ return ;

}

}

以上就是对于树的一些简单介绍，只要认清树和链表节点的组成以及节点与节点之间相互的联系，就能很好的掌握他们。

<!--EndFragment-->