树的相关概念
树是使用递归方式定义的一种数据结构，树的子树仍然是树。
-根节点：树最顶端的节点，一棵树是有根节点和0个或多个非空子树组成
-叶子节点：没有子树的节点或度为0的节点
-父节点、子节点、兄弟节点：拥有相同父节点的节点是兄弟节点
-深度：从根节点到该节点唯一路径的长，根的深度为0
-度：拥有子树的数目
-高：节点的高是从该节点到一片树叶的最长路径长
树的实现
使用双向链表实现树，将每个节点的所有子节点都放在链表中。
每一个节点都有一个链指向第一个子节点，另一条链指向下一个兄弟节点，没有则为空
class TreeNode{
Object obj;
TreeNode firstChild;
TreeNode nextSibling;
}
二叉树
每个节点不能有多余两个子节点，即每个节点的子节点个树不超过两个。
二叉树的实现
在树的实现上稍作改变即可，每一个节点的两条链分别指向左子节点和右子节点。
class BinaryNode{
Object obj;
BinaryNode leftChild;
BinaryNode rightChild;
}
二叉树的应用：表达式树
表达式树的树叶是操作数，其他节点为操作符，这里限制所有的操作符均为二元操作符
通过遍历一棵表达式树可以获得此表达式，遍历的方式为先序遍历、中序遍历、后序遍历，遍历出来的结果分别是前缀表达式，中缀表达式和后缀表达式。三种遍历方式针对的父节点的访问顺序而言。
通过表达式也可以构造表达式树，通过将操作数压栈，遇到操作符弹出栈，组成易课新的树再压栈。
二叉搜索树
是二叉树的一个特例，性质是对于数中的每个节点，它的左子树中所有项的值小于该节点中的项，而他的右子树中所有项的值大于该节点中的项。
二叉搜索树的实现
1.一个封装节点的类，包含该节点数据和左右两个子节点引用
2.查找
根据二叉搜索树的特点，从根节点开始查找，通过比较值的大小选择向左子树搜索还是向右子树搜索，以此类推直到找到该节点，或者到最后一个叶子节点依然没有找到，证明树中没有该节点。可采用递归或while循环
3.寻找最值
最大值则从根节点开始，循环访问右子节点，直到叶子节点
最小值则从根节点开始，循环访问左子节点，直到叶子节点
4.插入
先查找到该节点位置，再将父节点的左子节点或右子节点指向新的节点即可
5.移除
需考虑三种情况：均需要考虑移除节点是其父节点的左子节点还是右子节点
-移除的节点是叶子节点，可直接删除，将其父节点指向它的引用置为null。
-移除的节点有一个子节点，将其父节点指向它的引用直接指向它的子节点以及将他指向子节点的引用置为null。
-移除的节点右两个子节点，首先要找出后继节点（该节点的右子树的最小数据），然后将该节点的父节点指向后继节点，后继节点的父节点指向他的引用置为null。
public class BinarySearchTree <T extends Comparable<? super T>>{
//利用双链表实现二叉搜索树
private static class Node<T> {
private T t;//数据
private Node<T> left;//左节点引用
private Node<T> right;//右节点引用
public Node(T t) {
this(t,null,null);
}
public Node(T t, Node<T> left, Node<T> right) {
this.t = t;
this.left = left;
this.right = right;
}
}
private Node<T> root;//根节点
public BinarySearchTree() {
root = null;
}
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(T t) {
return contains(t,root);
}
/**
* 根据二叉搜索树的特点，对于每个节点，左子树的值小于该节点值，右子树则大于该节点值
* @param t 指需查找的值
* @param node 指树的节点
* @return 若找到返回true
*/
public boolean contains(T t,Node<T> node) {
if(node == null) {//未找到或树为空
return false;
}
int result = t.compareTo(node.t);
if(result < 0) {
return contains(t,node.left);
}
else if(result > 0) {
return contains(t,node.right);
}
else {
return true;
}
}
//查找最小值，非递归实现
public T findMin() {
if(isEmpty()) {
try {
throw new Exception();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
Node<T> curr = root;
while(curr.left != null) {
curr = curr.left;
}
return curr.t;
}
//查找最大值，递归实现
public T findMax() {
if(isEmpty()) {
try {
throw new Exception();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
return findMax(root);
}
public T findMax(Node<T> node) {
if(node == null) {
return null;
}else if(node.right == null){
return node.t;
}
return findMax(node.right);
}
//插入操作
public void insert (T t) {
Node<T> newNode = new Node<T>(t);
if(root == null) {
root = newNode;
}
Node<T> curr = root;
while(true) {
if(t.compareTo(curr.t) > 0) {
if(curr.right == null) {
curr.right = newNode;
return;
}
curr = curr.right;
}else if(t.compareTo(curr.t) < 0) {
if(curr.left == null) {
curr.left = newNode;
return;
}
curr = curr.left;
}
}
}
//删除操作，考虑三种情况，该节点是叶节点，该节点有一个子节点，该节点有两个子节点
public boolean remove(T t) {
Node<T> parent = null;//删除节点的父节点
Node<T> curr = root;//删除节点
boolean isLeft = true;//删除节点是否未父节点的左子节点
//1.找到需要删除的节点和它的父节点
while(t != curr.t) {
parent = curr;
if(t.compareTo(curr.t) < 0) {
curr = curr.left;
}else {
isLeft = false;
curr = curr.right;
}
if(curr == null) {
return false;
}
}
//2.判断哪一种属于情况
//叶子节点
if(curr.left == null && curr.right == null) {
if(curr == root) {
root = null;
}else if(isLeft) {
parent.left = null;
}else {
parent.right = null;
}
}else if(curr.left == null && curr.right != null) {//有一个右节点
if(curr == root) {
root = curr.right;
}else if(isLeft) {
parent.left = curr.right;
}else {
parent.right = curr.right;
}
}else if(curr.left != null && curr.right == null) {//有一个左节点
if(curr == root) {
root = curr.left;
}else if(isLeft) {
parent.left = curr.left;
}else {
parent.right = curr.left;
}
}else {//有两个节点，先找到后继节点，右子树里面最小节点
Node<T> node = curr.right;
Node<T> nodeParent = null;
while(node.left != null) {
nodeParent = node;
node = node.left;
}
if(nodeParent == null) {//后继节点为删除节点的右子节点
if(curr == root) {
root = node;
root.left = curr.left;
}else if(isLeft) {
parent.left = node;
node.left = curr.left;
}else {
parent.right = node;
node.left = curr.left;
}
}else {//后继节点不是删除节点的右子节点
nodeParent.left = node.right;
node.right = curr.right;
}if(curr == root) {
root = node;
root.left = curr.left;
}else if(isLeft) {
parent.left = node;
node.left = curr.left;
}else {
parent.right = node;
node.left = curr.left;
}
}
return true;
}
}
