Tree可以通过多种方式定义。常见的方式是通过递归，一个Tree是多个Nodes的集合，这个集合可以是空集。因此Tree是由一个独一无二的root（根节点），空或者非空的子树T1，T2，T3，……，这些子树有一条边和r节点连接。
每一个子树也被称为r的孩子，r是每一个子树根节点的父节点。通过递归定义方式，我们发现一个Tree是一个N个Nodes的集合，其中一个被称为root，同时有N-1条edges。
Tree实现
一种tree的实现方式是每一个节点都由数据、连接所有孩子的边组成。但是，因为每一个节点的孩子数量可以非常大，并且不能提前知道，我们不能存储所有节点的连接，可以通过将所有孩子节点存储为一个list来解决。
class TreeNode {
Object element;
TreeNode firstChild;
TreeNode nextSibling;
}
Binary Tree
二叉树是一个只允许有两个孩子节点的树。
class BinaryNode {
Object element;
BinaryNode left;
BinaryNode right;
}
The Search Tree ADT
二叉树的重要应用之一是查找。我们假设每一个节点存储一个元素，我们暂时假设他们是int类型，同时不存在相等的。二叉树能够实现查找的重要属性是对于节点X，左子树的所有元素都小于它，右子树的所有元素都大于它。因此二分查找树要求所有元素是有序的。
private static class BinaryNode<AnyType> {
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;
}
以上为BinaryNode类，类似于在链表中的node节点一样是一个嵌套类。
/**
* Copyright (C), 2015-2019, XXX有限公司
* FileName: BinarySearchTree
* Author: dalu
* Date: 2019/7/28 23:28
* Description:
* History:
* <author> <time> <version> <desc>
* 作者姓名 修改时间 版本号 描述
*/
import java.nio.BufferUnderflowException;
/**
* 〈一句话功能简述〉<br>
* 〈〉
*
* @author dalu
* @create 2019/7/28
* @since 1.0.0
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
private static class BinaryNode<AnyType> {
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;
}
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 BufferUnderflowException();
return findMin(root).element;
}
public AnyType findMax() {
if(isEmpty()) throw new BufferUnderflowException();
return findMax(root).element;
}
public void insert(AnyType x) {
root = insert(x, root);
}
public void remove(AnyType x) {
root = remove(x, root);
}
public void printTree() {
}
private boolean contains(AnyType x, BinaryNode<AnyType> t) {
if(t == null) {
return false;
}
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;
}
}
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;
}
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
if (t == null)
return new BinaryNode<>(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;
}
private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
if (t == null) {
return t;
}
int compareResult = x.compareTo(t.element);
if(compareResult < 0) {
t.left = remove(x, t.left);
}
else if (compareResult > 0) {
t.right = remove(x, t.right);
}
else if(t.left != null && t.right != null) {
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
}
else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}
private void printTree(BinaryNode<AnyType> t) {
}
}
以上为二分查找树的基本结构，单一数据字段关联root节点，public方法调用私有的递归方法。
contains
这个操作返回true，当X元素在树中时。当X元素不在T中或者T为空时，我们返回false。查找时，我们会递归的访问T的子树，根据X和根节点的大小关系左或者右。
一定要注意首先需要判断是否为空，同时，递归很容易被while循环改写，这里由于栈的深度，我们可以简单的使用递归的方法。
findMin and findMax
这些私有方法返回树中最小和最大的元素的节点。findMin从root节点一直往左找最终的节点；findMax则向右。
insert
这个方法比较简单，将X插入树T，这里需要调用contains方法，当X在其中时，更新或者不做任何事情。否则，将X插入到查找路径的最后一个点。
remove
类似于其他数据结构，remove方法是比较复杂的。当我们找到需要删除的点后，我们需要考虑几种情况。
加入这个节点是叶子节点，可以直接被删除。加入这个节点有一个孩子节点，需要连接它的父节点和它的子节点。比较复杂的例子是有两个孩子节点的节点。
一般的策略是用右子树最小的节点替换这个节点，然后删除这个节点，因为在右子树中最小的节点不会有左子树。如下图所示,删除2后的变化。
image.png
文中实现的删除是比较低效的，因为他需要找到并且删除右子树的最小节点，当我们删除的数量不多时，比较流行的策略是lazy deletion，当元素被删除时，我们仅仅标记为被删除,尤其是当有重复元素时，字段存储出现的频率可以被递减。
网友评论