Java实现数据结构——二叉查找树

时间：2022-04-23 11:56:54

二叉查找树

二叉树是层次结构，要么是空集，要么是一个根（root）的元素和两颗不同的二叉树组成。空树的高度为0，非空树的高度是从根结点到它最远叶子结点的路劲长度+1。

树的遍历

访问树中每个结点一次且只有一次的过程
Tree-example:
Java实现数据结构——二叉查找树

前序遍历

  1. 访问当前结点
  2. 访问该结点的左子树
  3. 访问该结点的右子树
    Java实现数据结构——二叉查找树
    遍历结果：5 3 2 4 7 6 8
    用途：打印结构性文档，书、章、节

中序遍历

  1. 访问该结点的左子树
  2. 访问当前结点
  3. 访问该结点的右子树
    Java实现数据结构——二叉查找树
    遍历结果：2 3 4 5 6 7 8
    用途：以递增的顺序显示二叉树的所有节点

后序遍历

  1. 访问该结点的左子树
  2. 访问该结点的右子树
  3. 访问当前结点
    Java实现数据结构——二叉查找树
    遍历结果：2 4 3 6 8 7 5
    用途：文件系统中，在找出根目录之前，得到每个文件和子目录。

广度优先遍历

逐层访问树中的结点
1. 访问根结点
2. 从左往右，访问根结点的所有孩子
3. 从左往右，访问根结点的所有孙子结点
遍历结果：5 3 7 2 4 6 8

详细实现

设计结构图：
Java实现数据结构——二叉查找树

接口定义

package com.edu.chapter.twenty_six.day0416;

import java.util.Iterator;

/**
 * @author xukai
 * @date 2017年4月16日 下午6:17:40
 *
 */
public interface Tree<E extends Comparable<E>> {

    public boolean search(E e);

    public boolean insert(E e);

    public boolean delete(E e);

/**
 * 先序遍历
 */
    public void inorder();

/**
 * 后序遍历
 */
    public void postorder();

/**
 * 前序遍历
 */
    public void preorder();

    public int getSize();

    public boolean isEmpty();

    public Iterator<E> iterator();

}

抽象类定义

package com.edu.chapter.twenty_six.day0416;

import java.util.Iterator;

/**
 * @author xukai
 * @param <E>
 * @date 2017年4月16日 下午6:24:12
 *
 */
public abstract class AbstractTree<E extends Comparable<E>> implements Tree<E> {

    @Override
public void inorder() {
// TODO Auto-generated method stub
    }

    @Override
public void postorder() {
// TODO Auto-generated method stub
    }

    @Override
public void preorder() {
// TODO Auto-generated method stub
    }

    @Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return getSize() == 0;
    }

    @Override
public Iterator<E> iterator() {
// TODO Auto-generated method stub
return null;
    }

}

具体实现

结点静态内部类

    /**
 * 结点类
 * @author xukai
 * @date 2017年4月18日 上午10:52:46
 * @param <E>
 *
 */
    public static class TreeNode<E extends Comparable<E>>{
        E element;
        TreeNode<E> left;
        TreeNode<E> right;

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


@Override
        public int hashCode() {
final int prime = 31;
            int result = 1;
            result =
                prime * result + ((element == null) ? 0 : element.hashCode());
            result = prime * result + ((left == null) ? 0 : left.hashCode());
            result = prime * result + ((right == null) ? 0 : right.hashCode());
return result;
        }


@Override
        public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
            TreeNode<?> other = (TreeNode<?>) obj;
if (element == null) {
if (other.element != null)
return false;
            } else if (!element.equals(other.element))
return false;
if (left == null) {
if (other.left != null)
return false;
            } else if (!left.equals(other.left))
return false;
if (right == null) {
if (other.right != null)
return false;
            } else if (!right.equals(other.right))
return false;
return true;
        }


@Override
        public String toString() {
return "TreeNode [element=" + element + ", left=" + left
                + ", right=" + right + "]";
        }

    }

添加元素

  1. 判断是否为空树
  2. 找出当前插入结点的父结点
  3. 插入节点，size++
    @Override
public boolean insert(E e) {
if (root == null) {
            root = createNewNode(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 = createNewNode(e);
            } else {
                parent.right = createNewNode(e);
            }
        }
        size ++;
return true;
    }

protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
    }

查找元素

    @Override
public boolean search(E e) {
        TreeNode<E> current = root;

while (current != null) {
if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else {
return true;
            }
        }

return false;
    }

删除元素

  1. 查找到要删除的元素
  2. 假如当前结点没有左孩子，将该结点的父结点和当前结点的右孩子相连。
  3. 假如当前结点有一个左孩子，找出当前结点current的左子树中最大元素结点rightMax，
    将rightMax的父结点和rightMax的左孩子相连，删除rightMax,size–。
    @Override
public boolean delete(E e) {
        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 
break;
        }

if (current == null) {
return false;
        }

if (current.left == null) {
// current-node not exist left-node
if (parent == null) {
                root = current.right;
            } else {
// connect to current.right and parent
if (e.compareTo(parent.element) < 0) {
parent.left = current.right;
                } else {
parent.right = current.right;
                }
            }
        } else {
// current-node exist left-node
            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 == current is true; 
                parentOfRightMost.left = rightMost.left;
            }
        }

        size --;
return true;
    }

前序遍历

    @Override
public void inorder() {
        inorder(root);
    }

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

广度优先遍历

    /**
 * 广度优先遍历
 */
public void breadthFirstTraversal() {
        LinkedList<BinaryTree.TreeNode<E>> queue = new LinkedList<>();

if (this.root == null) {
return;
        }
        queue.add(this.root);

while (!queue.isEmpty()) {
            TreeNode<E> node = queue.removeFirst();
            System.out.println(node.element + " ");
if (node.left != null) {
                queue.add(node.left);
            }
if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

附

二叉排序树是一种分层的数据结构。
查看源码(附带Applet可视化界面，乱码是因为项目是utf-8，需要改成gbk)
Java实现数据结构——二叉查找树
标签：

相关文章