java：数据结构（四）二叉查找树以及树的三种遍历

@TOC

二叉树模型

二叉树是树的一种应用，一个节点可以有两个孩子：左孩子，右孩子，并且除了根节点以外每个节点都有一个父节点。当然这种简单的二叉树不能解决让树保持平衡状态，例如你一直往树的左边添加元素，就会导致查找效率的减慢。，如何解决这个问题，下一篇文章再说。

二叉树的实现

• 二叉树的实现类

import java.util.LinkedList;

/**
 * 二叉查找树
 * @param <E> 泛型节点
 */
public class BinaryTree<E extends Comparable> implements Tree<E> {
    /**
     * @param root 根节点
     */
    private Node<E> root;

    /**
     * 内部类
     * 继承Comparable类来比较泛型的大小
     * 如果泛型是一个包含个多基本类型的对象，你需要重写compareTo方法
     * @param <E> 泛型类型的节点
     */
    private class Node<E extends Comparable> {
        E data;
        Node<E> left;
        Node<E> right;

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }

        public int getNum() {
            return num;
        }

        public void setNum(int num) {
            this.num = num;
        }

        int num;
        public Node<E> getLeft() {
            return left;
        }



        public Node<E> getRight() {
            return right;
        }



        public Node(E data){
            this.data=data;
        }

        public Node(E data, Node next, Node pre) {
            this.data = data;
            this.left = next;
            this.right = pre;
        }

        public Node(){
            left=null;
            right=null;
            data=null;
            num=1;
        }
        public E getData() {
            return data;
        }

        public void setData(E data) {
            this.data = data;
        }



    }

    /**
     * 判空方法
     * @return  true 树为空 false 树不为空
     */
    @Override
    public boolean isEmpty() {
        if(root==null){
            return true;
        }else{
            return false;
        }
    }

    /**
     * 使树为空
     * 个人理解：
     * 树中其他节点有实例对象存储在实例池中
     * 根节点不仅有实例对象，而且还要引用类型，存在java栈的本地变量表中
     * 之间使根节点为NULL
     */
    @Override
    public void makeEmpty() {
        root=null;
    }

    /**
     * 判断某个泛型类型的节点在树中
     * @param p 泛型类型
     * @return true 包含在节点中 false 不包含
     */
    @Override
    public boolean contains(E p) {
       return contain(p,root);
    }

    /**
     * contains方法的具体实现
     * 采用递归实现
     * @param p 需要判断是否存在书中泛型元素
     * @param r 树中的节点
     * @return true  包含 false 不包含
     */
    private boolean contain(E p,Node<E> r){
        Node<E> temp=root;
        if(root==null){
            return false;
        }else{
            if(temp.getData().compareTo(p)>0){
                contain(p,temp.getLeft());
            }else if(temp.getData().compareTo(p)<0){
                contain(p,temp.getRight());
            }else if(temp.getData().compareTo(p)==0&&temp.num>0){
                return true;
            }
        }
        return false;
    }

    /**
     * 找到树中最小的元素
     * @return 树中最小的元素
     */
    @Override
    public E findMin() {
        if(isEmpty()){
            System.out.println("树为空");
        }else {
            /**
             * 因为采用懒惰删除，所以树中最小的元素不仅要是最左面的哪一个
             * 而且还要是num>0的哪一个
             */
            Node<E> p = root;
            Node<E> temp = root;
            while (p.getLeft() != null) {
                p = p.getLeft();
                if (p.num > 0) {
                    temp = p;
                }
            }
            return temp.getData();

        }
        throw new NullPointerException();
    }

    /**
     * 找到树中最大的元素
     * 和寻找最小的原理一样
     * @return 树中最大的元素
     */
    @Override
    public E findMax() {
        if(isEmpty()){
            System.out.println("树为空");
        }else {
            Node<E> p = root;
            Node<E> temp = root;
            while (p.getRight() != null) {
                p = p.getRight();
                if (p.num > 0) {
                    temp = p;
                }
            }
            return temp.getData();
        }
        throw new NullPointerException();
    }

    /**
     * 树的前序遍历
     * 根左右
     */
    @Override
    public void preTraversal() {
        System.out.print("前序遍历：");
        preTraversal(root);
        System.out.println();
    }

    /**
     * 前序遍历的具体实现方法
     * @param p 使用递归时进入下一个节点
     */
    private void preTraversal(Node<E> p) {
        if(isEmpty()){
            System.out.println("树为空");
        }else {
            if (p.num > 0) {
                System.out.print(p.getData() + " ");
            }
            if (p.getLeft() != null) {
                preTraversal(p.getLeft());
            }
            if (p.getRight() != null) {
                preTraversal(p.getRight());
            }
            return;
        }

    }

    /**
     * 树的层序遍历
     * 即从根开始一层一层的遍历
     */
    public void seqTraverse(){
        if(isEmpty()){
            System.out.println("树为空");
        }else {
            System.out.print("层序遍历：");
            LinkedList<Node<E>> temp = new LinkedList<>();
            Node<E> p = root;
            temp.add(p);
            while (!temp.isEmpty()) {
                Node<E> a = temp.pop();
                if (a.num > 0) {
                    System.out.print(a.getData() + " ");
                }
                if (a.getLeft() != null) {
                    temp.add(a.getLeft());
                }
                if (a.getRight() != null) {
                    temp.add(a.getRight());
                }
            }
            System.out.println();
        }
    }

    /**
     * 后序遍历的实现方法
     * @param p 使用递归时进入下一个节点
     */
    private void posTraversal(Node<E> p) {
        if(isEmpty()){
            System.out.println("树为空");
        }else {
            if (p.getLeft() != null) {
                posTraversal(p.getLeft());
            }
            if (p.getRight() != null) {
                posTraversal(p.getRight());
            }
            if (p.num > 0) {
                System.out.print(p.getData() + " ");
            }
            return;
        }
    }

    /**
     * 中序遍历的实现方法
     * @param p 使用递归时进入下一个节点
     */
    private void cenTraversal(Node<E> p) {
        if(isEmpty()){
            System.out.println("树为空");
        }else {
            if (p.getLeft() != null) {
                cenTraversal(p.getLeft());
            }
            if (p.num > 0) {
                System.out.print(p.getData() + " ");
            }
            if (p.getRight() != null) {
                cenTraversal(p.getRight());
            }

            return;
        }
    }

    /**
     * 树的后序遍历
     * 左右根
     */
    @Override
    public void posTraversal() {
        System.out.print("后序遍历：");
        posTraversal(root);
        System.out.println();
    }
    /**
     * 树的中序遍历
     * 左根右
     */
    @Override
    public void cenTraversal() {
        System.out.print("中序遍历：");
        cenTraversal(root);
        System.out.println();
    }

    /**
     * 向树中插入元素
     * @param p 待插入的元素
     */
    @Override
    public void insert(E p) {
        /**
         * 主要为了将num加一
         */
        Node temp=new Node<>(p);
        temp.num++;
        /**
         * 根为空，就给根赋值
         */
        if(root==null) {
            root=temp;
        }else{
            /**
             *如果元素小于当前的d元素就往左递归
             * 反之就向右递归
             * 如果相等就num加一
             */
            Node<E > d=root;
            while (d!=null){
               if(p.compareTo(d.getData())<0){
                   if(d.getLeft()==null){
                       d.setLeft(temp);
                       break;
                   }
                    d=d.getLeft();
               }else if(p.compareTo(d.getData())>0){
                   if(d.getRight()==null){
                       d.setRight(temp);
                       break;
                   }
                   d=d.getRight();
               }else{
                   d.num++;
               }
            }
        }
    }

    /**
     *删除树中的一个节点
     * 采用懒惰删除对num的节点进行减一
     * @param p 需要删除的内容
     */
    @Override
    public void remove(E p) {
        removePri(p,root);
    }
    private void removePri(E p,Node<E> r){
        Node temp=r;
        if(temp.getData().compareTo(p)>0){
            removePri(p,temp.getLeft());
        }else if(temp.getData().compareTo(p)<0){
            removePri(p,temp.getRight());
        }else {
            temp.num--;
        }
    }



}

• 接口的类

/**
 * 树的接口
 * @param <E> 泛型的类型
 */
public interface Tree<E > {
    /**
     * 判空函数
     * @return true 树为空 false 树不为空
     */
    boolean isEmpty();

    /**
     * 使树为空
     */
    void makeEmpty();

    /**
     * 检查书中是否包含p这个元素
     * @param p  泛型元素
     * @return true 包含 false 不包含
     */
    boolean contains(E p);

    /**
     * 找到树中最小元素
     * @return 最小的元素
     */
    E findMin();
    /**
     * 找到树中最大元素
     * @return 最大的元素
     */
    E findMax();

    /**
     * 前序遍历
     */
    void preTraversal();

    /**
     * 后序遍历
     */
    void posTraversal();

    /**
     * 中序遍历
     * 森林里没有中序遍历，森林无法判断哪个是中间
     * 所以可以不实现
     */
    default void cenTraversal() {

    }

    /**
     * 插入元素
     * @param p 待插入的元素
     */
    void insert(E p);

    /**
     * 删除方法
     * @param p 待删除的元素
     */
    void remove(E p);


}

对于代码的测试

import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        BinaryTree<Integer> dd=new BinaryTree<>();
        dd.insert(4);
        dd.insert(2);
        dd.insert(3);
        dd.insert(1);
        dd.insert(6);
        dd.insert(5);
        dd.insert(7);
       // dd.preTraversal();
        //dd.cenTraversal();
      //  dd.posTraversal();
      //  dd.seqTraverse();
       System.out.println(dd.findMin()); ;
       System.out.println(dd.findMax());
        dd.remove(2);
        dd.remove(6);
    }
}

如上图的代码构成了如下的树：

graph LR A((4)) --> B((2)) A --> C((6)) B-->d((1)) B-->e((3)) C-->g((5)) C-->j((7))

• 调用findMax和findMin方法结果如下：
• 调用remove方法前后的区别 -调用前 调用后： 可见被删除的元素没有输出

树的三种遍历

四种遍历分别是先序遍历、中序遍历、后序遍历、层序遍历

先序遍历就是：对节点的除了工作是在它的诸儿子节点被处理前进行的，也就是说先访问根再访问左子树然后访问右子树。

中序遍历：对节点的除了工作是在它的左儿子节点被处理后进行的，也就是说先访问左节点再访问根节点然后访问右节点。

后序遍历：对节点的除了工作是在它的诸儿子节点被处理后进行的，也就是说先访问左再访问根子树然后访问右子树。

层序遍历：和前三种遍历方式不一样，层序遍历需要借用队列，从根节点读入，然后出队，只要出队的元素有左节点，左节点就入队，若还有右节点，右节点就入队，直到队列为空。