> 生活笔记  > python
二叉查找树的java实现

(tree)可以用几种方式定义。定义树的一种自然的方式是递归的方式。没有儿子的节点称为树叶(leaf)。对树的任意节点ni,ni深度(depth)为从根ni唯一的路径的长。因此,根的深度为0。ni(height)是从ni到一片树叶的最长路径的长。因此所有i的树叶的高都是0。一颗树的高等于它的根的高。

树的实现

实现树的一种方法可以是在每一个节点除数据外还要有一些链,使得该节点的每一个儿子都有一个链指向它。然而,由于每个节点的儿子树可以变化很大并且事先不知道,因此在数据结构中建立到各子节点直接的链接是不可行的,应为这样会产生太多浪费的空间。实际上解决方法很简单:将每个节点的所有儿子都放在树节点的链表中。

class TreeNode{
    Object element;
    TreeNode firstChild;//第一个儿子的链
    TreeNode nextSibling;//下一兄弟的链
}

二叉树

二叉树(binary tree)是一棵树,其中每个节点都不能有多于两个的儿子。

二叉树的实现

class BinaryNode{
    Object element; //在节点中的数据
    BinaryNode left; //左儿子
    BinaryNode right; //右儿子
}

查找树ADT--二叉查找树

二叉树的一个重要的应用是它们在查找中的使用。使二叉树成为二叉查找树的性质是,对于树中的每个节点X,它的左子树中所有项的值小于X中的项,而它的右子树中所有项的值大于X中的项。

1346901453_1064.png

这意味着该树所有的元素都能够排序。要写出一个类,我们需要提供一个接口来表示这个性质。这个接口就是Comparable,该接口告诉我们,树中的两项总可以使用compareTo方法进行比较。

二叉查找树的代码实现:

/**
 *BinaryNode类,是一个嵌套类
 *
 */
private static class BinaryNode<AnyType>{
    //Constructors
    BinaryNode(AnyType theElement){
        this(theElement, null, null);
    }
    
    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt){
        element = theElement;
        left = lt;
        right = rt;
    }
    
    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
}
/**
 *BinarySearchTree类
 */
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>{
    private static class BinaryNode<Anytype>{
        //BinaryNode类
    }
     
    private BinaryNode<AnyType> root;//根节点
     
    public BinarySearchTree(){
        root = null;
     }
     
    public void makeEmpty(){
        root = null;
    }
     
    public boolean isEmpty(){
        return root == null;
    }
     
    public boolean contains(AnyType x)
        return contains(x, root);
    public AnyType findMin(){
        if(isEmpty)
            throw new UnderflowException();//如果树为null,则抛出异常。
        return findMin(root).element;
    }
    public AnyType findMax(){
        if(isEmpty)
            throw new UnderflowException();
        return findMax(root).element;
    }
    public void insert(AnyType x)
        root = insert(x, root);
    public void remove(AnyType x){
        root = remove(x, root);
    }
     
    private boolean contains(AnyType x, BinaryNode<AnyType> t){
        //...
        //具体实现
    }
    private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
            //...
        }
        private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
            //...
        }
        
        private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
            //...
        }
        private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t){
            //...
        }
}

contains方法

如果在树T中存在含有项X的节点,那么这个操作需要返回true,如果这样的节点不存在则返回false。如果T是空集,那么可以就返回false。否则,我们对树T的左子树或右子树进行一次递归调用。

/**
 *@param x 要查找的X项
 *@param t 树T
 */
 private boolean contains(AnyType x, BinaryNode<AnyType> t){
     if(t == null)
         return false;//如果为空,返回false
     
     /*
      * compareTo方法把x和t中节点数据进行比较
      * 如果x小于t.element则返回负整数,等于则返回0,大于返回正整数。
      */
     int compareResult = x.compareTo(t.element);
     
     if(compareResult < 0)
         return contains(x, t.left);//递归调用查找左节点
     else if(compareResult > 0)
         return contains(x, t.right);//递归查找右节点
     else
         return true;//说明找到X项,返回true
 }

findMin()方法和findMax()方法,其中findMin()方法采用递归实现,findMax()方法用非递归方式实现

private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
    if(t == null)
        return null;
    else if(t.left == null)
        return t;//根据二叉查找树的性质,左子树中所有项的值小于它的值,如果左子树为空,则
                 //其本省最小。
    return findMin(t.left);
}

private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
    if(t!=null)
        while(t.right != null)
            t = t.right;
    return t;
}

insert方法

private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t){
    if(t == null)
        return new BinaryNode<AnyType>(x, null, null);
        
    int compareResult = x.compareTo(t.element);
    
    if(compareResult < 0)
        t.left = insert(x, t.left);
    else if(compareResult > 0)
        t.right = insert(x, t.right);
    else
        ;
    return t;
}

remove方法暂时没有实现。这就是二叉查找树的实现。

0条评论
猜你喜欢
精品推荐
扫二维码,加好友一起学习吧!