数据结构与算法-二叉查找树（java描述）

一、概述

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

1.1、定义

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

二、二叉查找树的实现

这里的二叉查找树的定义是在上篇博客的二叉树的定义上扩展的，因此这些操作是二叉树已定义的那些操作的补充。

2.1、抽象实现

BinarySearchTreeADT.java:

package sihai;/*** 二叉查找树接口*/ public interface BinarySearchTreeADT<T> extends BinaryTreeADT<T> {/** * 在树中的适当位置添加一个元素*/public void addElement(T element);/** * 根据特定的元素删除元素*/ public T removeElement(T targetElement);/** * 删除和目标元素有关的所有元素*/public void removeAllOccurrences(T targetElement);/** * 删除树中的最小元素*/public T removeMin();/** * 删除树中的最大元素*/ public T removeMax();/** * 查找树中的最小元素*/ public T findMin();/** *查找树中的最大元素*/public T findMax(); }

三、用链表实现二叉查找树

这里BinaryTreeNode类来表示树中的每个节点。每个BinaryTreeNode对象要维护一个指向节点所存储元素的引用，另外还要维护指向节点的每个孩子的引用。
LinkedBinaryTree提供两个构造函数：一个负责创建空的；另外一个负责创建一颗根节点为特定的元素的链接二叉查找树。

LinkedBinaryTree.java:

package jsjf;import jsjf.exceptions.*; import jsjf.*;/*** 链接二叉查找树实现了链接二叉树接口和二叉查找树接口*/ public class LinkedBinarySearchTree<T> extends LinkedBinaryTree<T>implements BinarySearchTreeADT<T> {public LinkedBinarySearchTree() {super();}public LinkedBinarySearchTree(T element) {super(element);if (!(element instanceof Comparable))throw new NonComparableElementException("LinkedBinarySearchTree");}/*** 添加元素*/public void addElement(T element) {if (!(element instanceof Comparable))throw new NonComparableElementException("LinkedBinarySearchTree");Comparable<T> comparableElement = (Comparable<T>)element;if (isEmpty())root = new BinaryTreeNode<T>(element);else {if (comparableElement.compareTo(root.getElement()) < 0){if (root.getLeft() == null) this.getRootNode().setLeft(new BinaryTreeNode<T>(element));elseaddElement(element, root.getLeft());}else{if (root.getRight() == null) this.getRootNode().setRight(new BinaryTreeNode<T>(element));elseaddElement(element, root.getRight());}}modCount++;}/*** 在特定的节点插入元素*/private void addElement(T element, BinaryTreeNode<T> node) {Comparable<T> comparableElement = (Comparable<T>)element;if (comparableElement.compareTo(node.getElement()) < 0){if (node.getLeft() == null) node.setLeft(new BinaryTreeNode<T>(element));elseaddElement(element, node.getLeft());}else{if (node.getRight() == null) node.setRight(new BinaryTreeNode<T>(element));elseaddElement(element, node.getRight());}}/*** 删除目标元素*/public T removeElement(T targetElement)throws ElementNotFoundException {T result = null;if (isEmpty())throw new ElementNotFoundException("LinkedBinarySearchTree");else{BinaryTreeNode<T> parent = null;if (((Comparable<T>)targetElement).equals(root.element)) {result = root.element;BinaryTreeNode<T> temp = replacement(root);if (temp == null)root = null;else {root.element = temp.element;root.setRight(temp.right);root.setLeft(temp.left);}modCount--;}else { parent = root;if (((Comparable)targetElement).compareTo(root.element) < 0)result = removeElement(targetElement, root.getLeft(), parent);elseresult = removeElement(targetElement, root.getRight(), parent);}}return result;}/*** 删除元素*/private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent)throws ElementNotFoundException {T result = null;if (node == null)throw new ElementNotFoundException("LinkedBinarySearchTree");else{if (((Comparable<T>)targetElement).equals(node.element)) {result = node.element;BinaryTreeNode<T> temp = replacement(node);if (parent.right == node)parent.right = temp;else parent.left = temp;modCount--;}else { parent = node;if (((Comparable)targetElement).compareTo(node.element) < 0)result = removeElement(targetElement, node.getLeft(), parent);elseresult = removeElement(targetElement, node.getRight(), parent);}}return result;}/*** 返回一个引用代替将要删除的元素*/private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) {BinaryTreeNode<T> result = null;if ((node.left == null) && (node.right == null))result = null;else if ((node.left != null) && (node.right == null))result = node.left;else if ((node.left == null) && (node.right != null))result = node.right;else{BinaryTreeNode<T> current = node.right;BinaryTreeNode<T> parent = node;while (current.left != null){parent = current;current = current.left;}current.left = node.left;if (node.right != current){parent.left = current.right;current.right = node.right;}result = current;}return result;}/*** 删除目标元素的所有引用*/public void removeAllOccurrences(T targetElement)throws ElementNotFoundException {removeElement(targetElement);try{while (contains((T)targetElement))removeElement(targetElement);}catch (Exception ElementNotFoundException){}}/***删除最小元素*/public T removeMin() throws EmptyCollectionException {T result = null;if (isEmpty())throw new EmptyCollectionException("LinkedBinarySearchTree");else {if (root.left == null) {result = root.element;root = root.right;}else {BinaryTreeNode<T> parent = root;BinaryTreeNode<T> current = root.left;while (current.left != null) {parent = current;current = current.left;}result = current.element;parent.left = current.right;}modCount--;}return result;}/*** 删除最大元素*/public T removeMax() throws EmptyCollectionException {// TODO}/*** 查询二叉查询树中的最小值*/public T findMin() throws EmptyCollectionException {// TODO}/*** 查询二叉查询树中的最大值*/public T findMax() throws EmptyCollectionException {// TODO}/*** 查询目标元素*/public T find(T targetElement) throws ElementNotFoundException {// TODO}/*** 查询左节点*/public LinkedBinarySearchTree<T> getLeft(){// TODO}/*** 查询右节点*/public LinkedBinarySearchTree<T> getRight(){// TODO}/*** 查找目标节点*/private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) {// TODO} }

***注意：***其中还有一些没有完善，日后再慢慢学习完善。

总结

以上是生活随笔为你收集整理的数据结构与算法-二叉查找树（java描述）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。