week07_day04_Tree02

本文主要是介绍week07_day04_Tree02，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

删除：分三种情况处理
a. 如果要删除结点没有孩子，那么直接将该结点删除就行了。
b. 如果要删除结点只有一个孩子，那么需要就父亲结点对应的指针，指向孩子结点。
c. 如果要删除结点有两个孩子，那么我们可以找到这个结点的右子树中最小结点 (或者
左子树中最大结点)，把它替换到要删除的结点上，然后再删除掉这个最小结点。

如果搞不懂remove方法，就假设删除结点C，手动执行一下代码

关于层次遍历（用队列来实现）：

用栈实现先序遍历：

用栈实现中序遍历：

建树操作：
1.这个方法不依赖于BinarySearchTree类对象而存在，所以得加static
2.但是这样做的话没有泛型消息，那么怎么办呢？我们可以把这个方法设置成泛型方法， 加<T>
3.但是BinarySearchTree中的元素都是可比较的，所以我们要求这个泛型extends Comparable<T>
2.有人说Comparable是接口啊，为啥用extends，extends表示泛型的向下限定，这是固定写法，T extends Comparable表示要求T必须是Comparable或者Comparable的子类类型。
4.T extends Comparable<？ super T>既然我能比较T的父类，那我也能比较T
5.你定义了泛型T，但编译器怎么知道T是啥类型呢？T怎么传入进来呢？
返回值类型：BinarySearchTre<T> 、参数：List<T> preOrder，List<T> inOrder

package com.cskaoyan.tree;import sun.security.krb5.internal.tools.Klist;import java.util.*;/*** @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<? super 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，不知道在哪个位置插入keyroot = 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.leftnode.left = add(node.left, key);} else if (cmp > 0) {//在右子树中插入key，并链接到node.rightnode.right = add(node.right, key);}//如果触cmp == 0，就什么也不做return node;}/*** 删除BST与指定对象相等的元素** @param key 执行对象* @return 如果删除成功返回true，否则返回false*/
/*    public boolean remove(E key) {if (key == null) {throw new IllegalArgumentException("key cannot be null");}TreeNode p = null;TreeNode x = root;while (x != null) {int cmp = key.compareTo(x.value);if (cmp < 0) {p = x;x = x.left;} else if (cmp > 0) {p = x;x = x.right;} else break;}//x == null或者break//BST中没有与指定对象相等的结点if (x == null) return false;//找到，break出来了，x就是我们要删除的结点// x的度为2的情况if (x.left != null && x.right != null) {//找右子树的最小结点TreeNode minP = x;TreeNode minX = x.right;while (minX.left != null) {minP = minX;minX = minX.left;}//用右子树的最小值结点替换x结点的值x.value = minX.value;//把情况退化成度为1或度为0的情况p = minP;x = minX;}//x结点就是要删除的结点，并且x结点的度为0或1TreeNode child = x.left != null ? x.left : x.right;//判断是否是根节点if (p == null) p = child;else if (p.left == x) p.left = child;else p.right = child;size--;return true;}*///remove方法的递归实现public boolean remove(E key) {if (key == null) {throw new IllegalArgumentException("key cannot be null");}int oldSize = size;// 在root这棵树中删除与key相等的元素，并把删除元素后的根节点赋值给rootroot = remove(root, key);return oldSize > size;}private TreeNode remove(TreeNode node, E key) {//边界条件if (node == null) return null;int cmp = key.compareTo(node.value);if (cmp < 0) node.left = remove(node.left, key);else if (cmp > 0) node.right = remove(node.right, key);else {//cmp == 0表示我们删除的就是这个结点if (node.left != null && node.right != null) {//找右子树的最小结点TreeNode minOfRight = node.right;while (minOfRight.left != null) {minOfRight = minOfRight.left;}node.value = minOfRight.value;node.right = remove(node.right, minOfRight.value);} else {//度为0或者1的情况TreeNode child = node.left != null ? node.left : node.right;size--;//返回孩子结点，就相当于删除了该结点return child;}}return node;}/*** 判断BST中是否有和指定对象相等的元素** @param key 指定对象* @return 如果存在返回true，否则返回false*/public boolean contains(E key) {if (key == null) {throw new IllegalArgumentException("key cannot be null");}TreeNode x = root;while (x != null) {int cmp = key.compareTo(x.value);if (cmp < 0) x = x.left;else if (cmp > 0) x = x.right;else return true;}//x == null,退出循环return false;}/*** 求BST中的最小值** @return BST中的最小值*/public E min() {if (this.isEmpty()) {throw new NoSuchElementException("BST is Empty!");}TreeNode x = root;while (x.left != null) x = x.left;return x.value;}/*** 求BST中的最大值** @return BST中的最大值*/public E max() {if (this.isEmpty()) {throw new NoSuchElementException("BST is Empty");}return max(root).value;}private TreeNode max(TreeNode node) {if (node.right != null) return max(node.right);return node;}/*** 清空BST中所有元素*/public void clear() {root = null;size = 0;}/*** 判空** @return*/public boolean isEmpty() {return root == null;}/*** 获取BST中元素的个数** @return 元素的个数*/public int size() {return size;}/*** 获取树的高度，空树高度为0** @return 数的高度*/public int height() {return height(root);}private int height(TreeNode node) {if (node == null) return 0;int leftHeight = height(node.left);int rightHeight = height(node.right);return Math.max(leftHeight, rightHeight) + 1;}/*** 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);}//用栈实现先序遍历public List<E> preOrder2() {List<E> list = new ArrayList<>();if (isEmpty()) return list;//将根节点入栈Deque<TreeNode> stack = new LinkedList<>();stack.push(root);while (!stack.isEmpty()) {TreeNode x = stack.pop();list.add(x.value);if (x.right != null) stack.push(x.right);if (x.left != null) stack.push(x.left);}return 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);}//用栈实现中序遍历public List<E> inOrder2() {List<E> list = new ArrayList<>();if (this.isEmpty()) return list;Deque<TreeNode> stack = new LinkedList<>();TreeNode x = root;while (x != null || stack.isEmpty()) {//x结点不为空时while (x != null) {stack.push(x);x = x.left;}//x == null，栈顶元素的左子树遍历完了x = stack.pop();list.add(x.value);//往右走x = x.right;}return 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 List<E> postOrder2() {//用链表来存储后序遍历的元素LinkedList<E> list = new LinkedList<>();if (this.isEmpty()) return list;//将根节点入栈Deque<TreeNode> stack = new LinkedList<>();stack.push(root);while (!stack.isEmpty()) {TreeNode x = stack.pop();//在链表表头添加元素list.addFirst(x.value);if (x.left != null) stack.push(x.left);if (x.right != null) stack.push(x.right);}return list;}/*** 层次遍历** @return 层次遍历的列表*/public List<E> levelOrder() {List<E> list = new ArrayList<>();if (isEmpty()) return list;//将根节点入队列Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//判断队列是否为空while (!queue.isEmpty()) {//出队一个元素并添加到list中TreeNode x = queue.poll();list.add(x.value);if (x.left != null) queue.offer(x.left);if (x.right != null) queue.offer(x.right);}//队列为空，返回listreturn list;}/*** 层次遍历，但可以知道每个元素在第几层** @return 层次遍历的列表*///每一层用一个list表示，如：[[C],[A,D],[B,E]]public List<List<E>> levelOrder1() {List<List<E>> list = new ArrayList<>();if (isEmpty()) return list;//将根节点入队列Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//判断队列是否为空while (!queue.isEmpty()) {//记录这一层元素的个数int count = queue.size();List<E> temp = new ArrayList<>();for (int i = 0; i < count; i++) {TreeNode x = queue.poll();temp.add(x.value);if (x.left != null) queue.offer(x.left);if (x.right != null) queue.offer(x.right);}list.add(temp);}//队列为空，返回listreturn list;}/*** 根据先序和中序构建树** @param preOrder 先序遍历列表* @param inOrder  中序遍历列表* @param <T>      元素类型* @return 构建的树*/public static <T extends Comparable<? super T>> BinarySearchTree<T> buildTree(List<T> preOrder, List<T> inOrder) {BinarySearchTree<T> tree = new BinarySearchTree<T>();//BST有两个属性：size和roottree.size = preOrder.size();// 构建整棵树tree.root = tree.build(preOrder, inOrder);return tree;}private TreeNode build(List<E> preOrder, List<E> inOrder) {// 边界条件if (preOrder == null || preOrder.isEmpty()) return null;// 构建根结点E key = preOrder.get(0);TreeNode node = new TreeNode(key);int index = inOrder.indexOf(key); //[0, index), [index+1, size)// 构建左子树List<E> leftPreOrder = preOrder.subList(1, index + 1);List<E> leftInOrder = inOrder.subList(0, index);node.left = build(leftPreOrder, leftInOrder);// 构建右子树List<E> rightPreOrder = preOrder.subList(index + 1, preOrder.size());List<E> rightInOrder = inOrder.subList(index + 1, inOrder.size());node.right = build(rightPreOrder, rightInOrder);return node;}/*** 根据后序和中序构建树** @param postOrder 后序遍历列表* @param inOrder   中序遍历列表* @param <T>       元素类型* @return 构建的树*/public static <T extends Comparable<? super T>> BinarySearchTree<T> buildTree2(List<T> postOrder, List<T> inOrder) {//首先创建一个BST类对象BinarySearchTree<T> tree = new BinarySearchTree<>();//给此对象的两个属性赋值tree.size = postOrder.size();tree.root = tree.build2(postOrder, inOrder);return tree;}private TreeNode build2(List<E> postOrder, List<E> inOrder) {//边界条件if (postOrder == null || postOrder.isEmpty()) return null;//构建根节点E key = postOrder.get(postOrder.size() - 1);TreeNode node = new TreeNode(key);int index = inOrder.indexOf(node.value);//构建左子树List<E> LeftPostOrder = postOrder.subList(0, index);List<E> LeftInOrder = inOrder.subList(0, index);node.left = build2(LeftPostOrder, LeftInOrder);//构建右子树List<E> RightPostOrder = postOrder.subList(index, postOrder.size() - 1);List<E> RightInOrder = inOrder.subList(index + 1, inOrder.size());node.right = build2(RightPostOrder, RightInOrder);return node;}public static void main(String[] args) {BinarySearchTree<Character> tree = new BinarySearchTree<>();tree.add('C');tree.add('A');tree.add('D');tree.add('B');tree.add('E');// tree.add('E');// System.out.println(tree.size());// System.out.println(tree.preOrder2()); //[C, A, B, D, E]// System.out.println(tree.inOrder()); // [A, B, C, D, E]// System.out.println(tree.postOrder2());//[B, A, E, D, C]// 删除不存在的结点
/*        System.out.println(tree.remove('X'));System.out.println(tree.size());*/// 删除度为0的结点
/*        System.out.println(tree.remove('B'));System.out.println(tree.size());System.out.println(tree.preOrder()); //[C, A, D, E]System.out.println(tree.inOrder());*/// 删除度为1的结点
/*        System.out.println(tree.remove('A'));System.out.println(tree.size());System.out.println(tree.preOrder()); //[C, B, D, E]System.out.println(tree.inOrder());*/// 删除度为2的结点/*System.out.println(tree.remove('C'));System.out.println(tree.size());System.out.println(tree.preOrder()); //[D, A, B, E]System.out.println(tree.inOrder());*//*System.out.println(tree.inOrder());System.out.println(tree.size());System.out.println(tree.isEmpty());tree.clear();System.out.println(tree.inOrder());System.out.println(tree.size());System.out.println(tree.isEmpty());*/// boolean contains(E key)/*System.out.println(tree.contains('X'));System.out.println(tree.contains('A'));*/// E min(), E max()/*System.out.println(tree.min()); //'A'System.out.println(tree.max()); //'E'*/// List<E> levelOrder()// System.out.println(tree.levelOrder()); //[C, A, D, B, E]// List<List<E>> levelOrder1()// System.out.println(tree.levelOrder1());// BinarySearTree buildTree(List preOrder, List inOrder)
//        List<Character> preOrder = Arrays.asList('C', 'A', 'B', 'D', 'E');
//        List<Character> postOrder = Arrays.asList('B', 'A', 'E', 'D', 'C');
//        List<Character> inOrder = Arrays.asList('A', 'B', 'C', 'D', 'E');
//        // BinarySearchTree<Character> tree = BinarySearchTree.buildTree(preOrder, inOrder);
//        BinarySearchTree<Character> tree = BinarySearchTree.buildTree2(postOrder, inOrder);
//        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]// int height()System.out.println(tree.height());tree.clear();System.out.println(tree.height());}}

几个问题：
Q1: BST的性能如何？增加，删除和查找的时间复杂度为多少？
增加：O(h)
删除：O(h)
查找：O(h)

Q2: 普通BST不能保证树的平衡，特别是：
假设开始时树是平衡的，但是随着动态的添加和删除（当度为2的时候每次都是从右子树中删除）
导致树最终往左倾斜，性能越来越差。
最坏情况下，就变成单支树，时间复杂度变成O(n) （退化成链表）

Q3: 自平衡的二叉搜索树
avl树：每个结点左子树的高度和右子树的高度之差不超过1
红黑树：通过红黑规则保证树的高度是log(n)的级别。

AVL vs 红黑树
a. 红黑树的高度稍高于AVL树
b. 添加和删除元素，红黑树所做的调整比AVL树少。
从工程角度看，红黑树性能稍微优于AVL树。

···············································································································································································································

接下来讲一下Set和Map，红黑树稍后会带大家实现。

Set
一个不包含重复元素的 collection。更确切地讲, set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2, 并且最多包含一个 null 元素。正如其名称所暗示的，此接口模仿了数学上的 set 抽象。

注意事项：Set 集合并不一定都是无序的，有些 Set 集合是有序的。
HashSet是无序，并且可以存储null元素
TreeSet是有序的(按字母顺序排序)，不可以存储null元素(会报空指针异常)
TreeSet底层是红黑树

set的方法都是继承自Collection，并没有自己定义的方法。

这篇关于week07_day04_Tree02的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---