树与二叉树

一、介绍

对于java中“树”这个概念，顾名思义就像是现实中存在的树一样,分为根、枝、叶三个部分，而在java中就分为根结点，枝结点，叶结点,你可以根据需要选择在各个节点里存储数据，二叉树对于数据的存储和查找都比较好。

二、使用

无论是哪一种树都是由很多结点组成的，每一个结点包含所需存储的数据，如果是枝结点还需存储自己的左右子节点，其实树节点也可以看成没有子节点的枝结点，建立一个树，首先需要定义一个结点类：下面就定义了一个简单的结点类

public class TreeNode {

    

    private int obj;

    private TreeNode left = null;

    private TreeNode right = null;

    private TreeNode root = null;

    

    public TreeNode(int obj){//存入数据元素

         this.obj = obj;

     }

｝

 

借用上边的结点，先实例化结点对象，然后把这些独立的结点对象，按照一定的规律一个一个的链接起来，当然根节点是固定的，这样接下来就可以开枝散叶了。

三、示例

下面是通过以上的方法，按照数据的大小构建了一棵二叉搜索树：

    

 /*

     * 把数据存入树中

     */

    public void transINtree(TreeNode nodechild,TreeNode nodefat){

       //大于左结点

       if(nodechild.getObj()<nodefat.getObj()){

           if(nodefat.getLeft()==null){ //如果左结点为空，则将结点存储进去

              nodefat.setLeft(nodechild);

              nodechild.setRoot(nodefat);

           }else{

              //如果左结点不为空，则继续查找

              transINtree(nodechild, nodefat.getLeft());

           }

       }

       //大于右结点

    if(nodechild.getObj()>nodefat.getObj()){

           

if(nodefat.getRight()==null){ //如果右结点为空，则将结点存储进去       nodefat.setRight(nodechild);

              nodechild.setRoot(nodefat);

           }else{

              //如果右结点不为空，则继续查找

              transINtree(nodechild, nodefat.getRight());

           }

       }

 

由二叉树的结构可以得出：在二叉树里查找数据的复杂度是n的以2为底的对数，而在一般的线性表里查找数据的复杂度为n，所以通过二叉搜索树查找数据的效率可见一斑。