你的位置:首页 > Java教程

[Java教程]java生成二叉树和遍历


在java中实现二叉树和链表的方法都是在类中定义该类的对象引用

比如

class Tree{  int data;  Tree left;  Tree right;}

这样的话当我们new一个Tree对象的时候,该对象就拥有了left和right两个对象,这样就起到了连接的

作用,在链表中就是连接了下一个,在树中就相当于边,这样就起到一个接一个的效果。总之,就是吧对象连接起来了。

下面是完整代码

package code;public class TwoTree{  public static void main(String[] args)  {    Tree root=new Tree(50);    int array[]={25,89,48,90,101,13,45,60};    for(int n=0;n<8;n++)    {      root.insert(root, array[n]);    }    Bianli bl=new Bianli(root);    bl.second(root);  }}class Tree{  int data;  Tree left;  Tree right;  //每一棵树  public Tree(int data)  {    this.data=data;    left=null;    right=null;  }  public void insert(Tree root,int data)  {    //如果比根大,如果右边为空,就放到根的右边,否则,则以此时根的右边为另一棵树的根,放到他的右边    //依次下去    if(data>root.data)    {      if(root.right==null)      {        root.right=new Tree(data);      }            else      {        this.insert(root.right, data);      }    }    //左边同理    else    {      if(root.left==null)        root.left=new Tree(data);      else        this.insert(root.left, data);    }      }  }class Bianli{  Tree root;  public Bianli(Tree root)  {    this.root=root;  }  //第一种遍历方法,前序遍历,根--左子树--右子树  public void first(Tree root)  {    if(root!=null)    {      System.out.println(root.data);      first(root.left);      first(root.right);    }      }  //第二种遍历方法。中序遍历 A字形遍历, 右边的从上到下,左边的从下到上  public void second(Tree root)  {    if(root!=null)    {      second(root.left);      System.out.println(root.data);      second(root.right);    }  }  
  //第三种后序遍历
  public void third(Tree root) { if(root!=null) { third(root.left); third(root.right); System.out.println(root.data); } }}

在代码中我们可以发现用了很多的递归,先拿生成树的递归说。

public void insert(Tree root,int data)  {    //如果比根大,如果右边为空,就放到根的右边,否则,则以此时根的右边为另一棵树的根,放到他的右边    //以此下去    if(data>root.data)    {      if(root.right==null)      {        root.right=new Tree(data);      }           else      {        this.insert(root.right, data);      }    }    //左边同理    else    {      if(root.left==null)        root.left=new Tree(data);      else        this.insert(root.left, data);    }      }

这里的递归是这样实现的,当我们根的有右边为空的话,那么就将添加的对象添加至右边

否则的话,就递归,即将根的右边的对象作为子树的一个根,依次这样下去。

我们可以这样理解,将大的一棵树看成是多课/\这样的一棵树(二叉树)。

----------------------------------------

二叉树的遍历,在代码中的三种遍历,我们发现都代码差不多,只不过输出的语句位置不同。这个需要

我们自己去体会,下面简单讲一下。

我们需要回到递归的本质

int num=0;public void DG(int n){  if(n==1)    return 1;      num=n*DG(n-1);   }

这是n的阶乘,最经典的递归的例子。

我们分析可以知道,递归就是一个方法调用自己,

比如上面代码中的DG 方法里面调用DG方法

我们需要一个条件是结束递归,然后再从后往前面计算,最后回到递归开始的地方。

同样上面二叉树的遍历也是一样,三种遍历的代码很像。

当我们满足结束的标志的时候,需要完成最后一次second(或者first 或者third)方法

(抽象理解 12345678这里我把递归形象化,完成1的操作需要完成2,完成2需要3···以此类推。那么倒回来,到8的时候结束递归,这时候需要完成8的所有操作,然后到7完成所有操作依次类推,最后回到开始递归的地方)

 

而三种遍历方法不同的就是,就是执行完该方法后的操做(即8(76···)的剩余的操作)。

有的是继续进行右边的遍历,有的是先打印,这就造成了打印的结果不同。

大一狗初学,有误请谅解!