week07_day03_Tree

本文主要是介绍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的定义： 左子树 <= (右子树 >=)

实现：
查找：先取根结点，如果它等于我们要查找的数就返回；如果查找的数据比根节点小，就在左子树中递归查找；如果要查找的数据比根结点大，那么就在右子树中递归查找。

插入：如果要插入的数据比结点大，并且结点的右子树为空，就将新数据直接插到右孩子的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比结点小，并且结点的左子树为空，就将新数据插入到左孩子的位置；如果不为空，就再递归遍历左子树，查找插入位置。

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

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，不知道在哪个位置插入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中元素的个数** @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]}}

关于这段代码中的增加结点的非递归遍历：

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

作业：

1. LeetCode之翻转二叉树
2. 递归实现BST的remove(E e)方法(选做)。

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

---