week07_day03_Tree
二叉查找树（可以根据这棵树查找结点）：
又叫二叉排序树（中序遍历的结果是有序的）。要求树中的结点可以按照某个规则进行比较。
左子树中所有结点的key比根结点的key小，并且左子树也是二叉搜索树。
右子树中所有结点的key比根结点的key大，并且右子树也是二叉搜索树。
-
Q1: BST 能存储null吗？为什么？
不能，BST要求元素能进行比较 -
Q2: BST 能存储key相同的对象吗？为什么？如果不能，可以改进吗？
按照BST的定义是不能存储key相同的对象的。
如何改进？
#1：可以在结点添加一个count属性。
但是我需要存储的是Student对象，这个Student对象包含一个学生的所有信息。而不是有几个15岁的同学
#2: 拉链法, 在结点添加一个next指针域。
next执行和key相同的下一个元素。可以看成这个二叉排序树存储的是value值为key的链表开发中大多用拉链法
#3：修改BST的定义： 左子树 <= (右子树 >=)
实现：
查找：先取根结点，如果它等于我们要查找的数就返回；如果查找的数据比根节点小，就在左子树中递归查找；如果要查找的数据比根结点大，那么就在右子树中递归查找。
插入：如果要插入的数据比结点大，并且结点的右子树为空，就将新数据直接插到右孩子的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比结点小，并且结点的左子树为空，就将新数据插入到左孩子的位置；如果不为空，就再递归遍历左子树，查找插入位置。
删除：分三种情况处理
a. 如果要删除结点没有孩子，那么直接将该结点删除就行了。
b. 如果要删除结点只有一个孩子，那么需要就父亲结点对应的指针，指向孩子结点。
c. 如果要删除结点有两个孩子，那么我们可以找到这个结点的右子树中最小结点 (或者
左子树中最大结点)，把它替换到要删除的结点上，然后再删除掉这个最小结点。
Q：查找，插入和删除操作的时间复杂度分别是多少？O(h)
Q：普通的BST最终都会倾斜，我们能否对其改进，实现自平衡的BST？
自平衡的二叉搜索树：
avl (任意一个结点，左子树和右子树的高度之差不超过1)
红黑树 (树的高度是log(n))
·························································································································································································
package com.cskaoyan.tree;
import sun.reflect.generics.tree.Tree;
import java.util.ArrayList;
import java.util.List;
/**
* @author shihao
* @create 2020-05-20 10:33
* <p>
* API:
* 增：boolean add(E e) 添加成功返回true，否则返回false(二叉排序树中有和e相同的值)
* 删：boolean remove(E e) 删除成功返回true，否则返回false(二叉排序树中无和e相同的值)
* void clear(); 清空树中所有元素
* 查：boolean contains(E e)
* E min()
* E max() 求最大值和最小值
* 遍历：List<E> preOrder();
* List<E> inOrder();
* List<E> postOrder();
* List<E> levelOrder();
* 建树：静态方法，因为建树操作不依赖于BinarySearchTree对象而存在
* static <T> BinarySearchTree buildTree(List<T> preOrder,List<T> inOrder)
* 获取属性：
* boolean isEmpty() 判空
* int size() 结点个数
* int height() 树的高度（二叉排序树的性能是依赖于二叉排序树的高度的）
*/
//我们希望BinarySearchTree结点可以进行比较，在java中除了基本数据类型外，
// 要想实现比较，得实现Comparable接口，而Comparable接口本身就是泛型接口，
// 所以得Comparable<E>，如果不写<E>的话，我们认为它可以对任意元素（Object）进行比较的
//public class BinarySearchTree<E extends Comparable<E>>
//第一个<E>定义泛型，第二个<E>使用泛型。但这样的话只能对E类型的元素进行比较
//但这样写还不够好
// public class BinarySearchTree<E extends Comparable<? super E>>
// Comparable<? super E>表示能对E的父类进行比较
// 那能对E的父类进行比较，就一定能对E进行比较
public class BinarySearchTree<E extends Comparable<E>> {
//属性
private TreeNode root;
private int size;
private class TreeNode {
TreeNode left;
E value;
TreeNode right;
public TreeNode(E value) {
this.value = value;
}
public TreeNode(TreeNode left, E value, TreeNode right) {
this.left = left;
this.value = value;
this.right = right;
}
}
//构造方法
//刚开始创建一颗空树，size = 0, root = null就可以不用写构造方法
//方法
/**
* 在BST中插入一个元素
*
* @param key 待插入的元素
* @return 如果插入成功返回true，失败返回false
*/
/*
public boolean add(E key) {
if (key == null) {
throw new IllegalArgumentException("key cannot be null");
}
//处理空树情况
if (root == null) {
root = new TreeNode(key);
size++;
return true;
}
TreeNode p = null;
TreeNode x = root;
int cmp;
do {
cmp = key.compareTo(x.value);
if (cmp < 0) {
//往左走
p = x;
x = x.left;
} else if (cmp > 0) {
//往右走
p = x;
x = x.right;
} else return false;
} while (x != null);
//插入结点
TreeNode node = new TreeNode(key);
if (cmp > 0) p.right = node;
else p.left = node;
size++;
return true;
}
*/
//add方法的递归实现
public boolean add(E key) {
if (key == null) {
throw new IllegalArgumentException("key cannot be null");
}
int oldSize = size;
// 在root这棵树中插入key，并把新的根节点赋值给root
//不能直接调用add(E key)这个方法，这个方法不能把问题规模给减小
// 也就是说，我只知道要插入key，不知道在哪个位置插入key
root = add(root, key);
return oldSize < size;
}
private TreeNode add(TreeNode node, E key) {
//边界条件
//node == null 说明这就是要插入的位置
if (node == null) {
size++;
return new TreeNode(key);
}
int cmp = key.compareTo(node.value);
if (cmp < 0) {
//在左子树中插入key，并链接到node.left
node.left = add(node.left,key);
} else if(cmp>0){
//在右子树中插入key，并链接到node.right
node.right = add(node.right,key);
}
//如果触cmp == 0，就什么也不做
return node;
}
/**
* 获取BST中元素的个数
*
* @return 元素的个数
*/
public int size() {
return size;
}
/**
* BST先序遍历
*
* @return 先序遍历列表
*/
public List<E> preOrder() {
List<E> list = new ArrayList<>();
//遍历BST，并把元素放入list中
preOrder(root, list);
return list;
}
private void preOrder(TreeNode node, List<E> list) {
//边界条件 node == null表示遍历到了叶子结点 直接返回即可
if (node == null) return;
//遍历根节点
list.add(node.value);
//遍历左子树
preOrder(node.left, list);
//遍历右子树
preOrder(node.right, list);
}
/**
* BST中序遍历
*
* @return 中序遍历列表
*/
public List<E> inOrder() {
ArrayList<E> list = new ArrayList<>();
//遍历BST，并把元素放入list中
inOrder(root, list);
return list;
}
private void inOrder(TreeNode node, ArrayList<E> list) {
if (node == null) return;
//遍历左子树
inOrder(node.left, list);
//遍历根节点
list.add(node.value);
//遍历右子树
inOrder(node.right, list);
}
/**
* BST后序遍历
*
* @return 后序遍历列表
*/
public List<E> postOrder() {
ArrayList<E> list = new ArrayList<>();
postOrder(root, list);
return list;
}
private void postOrder(TreeNode node, ArrayList<E> list) {
//边界条件
if (node == null) return;
//遍历左子树
postOrder(node.left, list);
//遍历右子树
postOrder(node.right, list);
//遍历根节点
list.add(node.value);
}
public static void main(String[] args) {
BinarySearchTree<Character> tree = new BinarySearchTree<>();
System.out.println(tree.add('C'));
System.out.println(tree.add('A'));
System.out.println(tree.add('D'));
System.out.println(tree.add('B'));
System.out.println(tree.add('E'));
//System.out.println(tree.add('E'));
System.out.println(tree.size());
System.out.println(tree.preOrder()); //[C, A, B, D, E]
System.out.println(tree.inOrder()); // [A, B, C, D, E]
System.out.println(tree.postOrder());//[B, A, E, D, C]
}
}
关于这段代码中的增加结点的非递归遍历：
·························································································································································································
作业：
- LeetCode之翻转二叉树
- 递归实现BST的remove(E e)方法(选做)。
推荐阅读