首页 > 代码库 > java 二叉查找树

java 二叉查找树

//接口+抽象类+实现类
package wangChaoPA实习工作练习.com.进阶篇.二叉查找树;

import java.util.Iterator;
public interface Tree<E extends Comparable<E>>
{
    // 从树中删除e
    boolean delete(E e);

    // 树的大小
    int getSize();

    // 中序遍历树
    void inorder();

    // 把e插入到tree中
    boolean insert(E e);

    // 树是否为空
    boolean isEmpty();

    /*
     * 返回迭代器
     */
    Iterator iterator();

    // 后续遍历树
    void postorder();

    // 先序遍历树
    void preorder();

    // 查找e是否在tree中
    boolean search(E e);
}



package wangChaoPA实习工作练习.com.进阶篇.二叉查找树;

import java.util.Iterator;
public abstract class AbstractTree<E extends Comparable<E>> implements Tree<E>
{
    @Override
    public boolean isEmpty()
    {
        return getSize() == 0;
    }

    @Override
    public Iterator iterator()
    {
        return null;
    }
}



package wangChaoPA实习工作练习.com.进阶篇.二叉查找树;

import java.util.ArrayList;
import java.util.Iterator;
public class BinaryTree<E extends Comparable<E>> extends AbstractTree<E>
{
    class InorderItertor implements Iterator
    {
        private int current = 0;
        private ArrayList<E> list = new ArrayList<E>();

        public InorderItertor()
        {
            inorder(root);
        }

        @Override
        public boolean hasNext()
        {
            if (this.current < this.list.size())
            {
                return true;
            }
            return false;
        }

        private void inorder(TreeNode<E> root)
        {
            if (root == null)
            {
                return;
            }
            inorder(root.left);
            this.list.add(root.element);
            inorder(root.right);
        }

        @Override
        public Object next()
        {
            return this.list.get(this.current++);
        }

        // 删除当前元素 并刷新list
        @Override
        public void remove()
        {
            delete(this.list.get(this.current));// 删除当前元素
            this.list.clear();// 清空list
            inorder(root);// 重新排序
        }
    }

    public static class TreeNode<E extends Comparable<E>>
    {
        E element;
        TreeNode<E> left;
        TreeNode<E> right;

        public TreeNode(E e)
        {
            this.element = e;
        }
    }

    protected TreeNode<E> root;
    protected int size = 0;

    public BinaryTree()
    {
    }

    public BinaryTree(E[] objects)
    {
        for (int i = 0; i < objects.length; i++)
        {
            insert(objects[i]);
        }
    }

    // 清空
    public void clear()
    {
        this.root = null;
        this.size = 0;
    }

    // 创建新的结点
    protected TreeNode<E> creatNewNode(E e)
    {
        return new TreeNode<E>(e);
    }

    // 删除结点e 难点
    @Override
    public boolean delete(E e)
    {
        TreeNode<E> parent = null;
        TreeNode<E> current = root;
        // 找到需要删除的结点current以及它的父结点parent
        while (current != null)
        {
            if (e.compareTo(current.element) < 0)
            {
                parent = current;
                current = current.left;
            }
            else if (e.compareTo(current.element) > 0)
            {
                parent = current;
                current = current.right;
            }
            else
            {
                break;
            }
        }
        // e结点不在tree中
        if (current == null)
        {
            return false;
        }
        // e在tree中 current结点没有左孩子
        if (current.left == null)
        {
            // 删除的是根结点
            if (parent == null)
            {
                // root指向current的右结点
                this.root = current.right;
            }
            else
            {// 不是根结点
                if (e.compareTo(parent.element) < 0)
                {
                    parent.left = current.right;// 父结点与current的右结点联系到一起
                }
                else
                {
                    parent.right = current.right;
                }
            }
        }
        else
        {// current结点有左孩子
            // rightMost的父结点
            TreeNode<E> parentOfRightMost = current;
            // 左子树最右端的结点
            TreeNode<E> rightMost = current.left;
            while (rightMost.right != null)
            {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;
            }
            // 替换值
            current.element = rightMost.element;
            if (parentOfRightMost.right == rightMost)
            {
                parentOfRightMost.right = rightMost.left;
            }
            else
            {
                parentOfRightMost.left = rightMost.left;
            }
        }
        this.size--;
        return true;
    }

    @Override
    public int getSize()
    {
        return this.size;
    }

    // 中序遍历
    @Override
    public void inorder()
    {
        inorder(this.root);
    }

    protected void inorder(TreeNode<E> e)
    {
        if (this.root == null)
        {
            return;
        }
        inorder(this.root.left);
        System.out.println(this.root.element + " ");
        inorder(this.root.right);
    }

    public Iterator inorderIterator()
    {
        return new InorderItertor();
    }

    // 插入
    @Override
    public boolean insert(E e)
    {
        if (this.root == null)
        {
            this.root = creatNewNode(e);
        }
        else
        {
            // 父结点
            TreeNode<E> parent = null;
            // 当前结点
            TreeNode<E> current = root;
            // 找到需要插入的结点的父结点位置
            while (current != null)
            {
                if (e.compareTo(current.element) < 0)
                {
                    parent = current;
                    current = current.left;
                }
                else if (e.compareTo(current.element) > 0)
                {
                    parent = current;
                    current = current.right;
                }
                else
                {
                    return false;
                }
            }
            // 插入
            if (e.compareTo(parent.element) < 0)
            {
                parent.left = creatNewNode(e);
            }
            else
            {
                parent.right = creatNewNode(e);
            }
        }
        this.size++;
        return true;
    }

    // 返回从根结点到指定结点之间的结点
    public ArrayList<TreeNode<E>> path(E e)
    {
        ArrayList<TreeNode<E>> list = new ArrayList<TreeNode<E>>();
        TreeNode<E> current = this.root;
        while (current != null)
        {
            list.add(current);
            if (e.compareTo(current.element) < 0)
            {
                current = current.left;
            }
            else if (e.compareTo(current.element) > 0)
            {
                current = current.right;
            }
            else
            {
                break;
            }
        }
        return list;
    }

    // 后序遍历
    @Override
    public void postorder()
    {
        postorder(this.root);
    }

    protected void postorder(TreeNode<E> e)
    {
        if (this.root == null)
        {
            return;
        }
        inorder(this.root.left);
        inorder(this.root.right);
        System.out.println(this.root.element + " ");
    }

    // 先序遍历
    @Override
    public void preorder()
    {
        preorder(this.root);
    }

    protected void preorder(TreeNode<E> e)
    {
        if (this.root == null)
        {
            return;
        }
        System.out.println(this.root.element + " ");
        inorder(this.root.left);
        inorder(this.root.right);
    }

    @Override
    public boolean search(E e)
    {
        TreeNode<E> current = this.root;
        while (current != null)
        {
            if (e.compareTo(current.element) < 0)
            {
                current = current.left;
            }
            else if (e.compareTo(current.element) > 0)
            {
                current = current.left;
            }
            else
            {
                return true;
            }
        }
        return false;
    }
}

java 二叉查找树