0 课程地址
https://coding.imooc.com/lesson/207.html#mid=14348
1 重点关注
1.1 代码草图
1.2 代码实现检查二分搜索树和平衡性
利用了二分搜索树中序遍历由小到大的特性 和 平衡二叉树的平衡因子大于1的特性
//1 校验二分搜索树(中序遍历参考之前的中序遍历一节)
public boolean judgeBST(){
List<K> list = new ArrayList<>();
inOrder(root,list);
for(int i=1;i<list.size();i++){
if(list.get(i-1).compareTo(list.get(i))>0){
return false;
}
}
return true;
}
private void inOrder(Node root, List<K> list){
if(root==null){
return;
}
inOrder(root.left,list);
list.add(root.key);
inOrder(root.right,list);
}
//2 校验平衡二叉树
public boolean judgeBalance(){
return judgeBalance(root);
}
private boolean judgeBalance(Node node){
if(root == null){
return true;
}
if(Math.abs(getBalanceFactor(node))>1){
return false;
}
return judgeBalance(node.left)&&judgeBalance(node.right);
}
2 课程内容
3 Coding
3.1 coding
案例：傲慢与偏见 统计单词
avlTree主类（测试方法在主类最下边）
package com.company;
import java.util.ArrayList;
import java.util.List;
public class AVLTree<K extends Comparable<K>,V> {
//1 定义Node
class Node{
private K key;
private V value;
private Node left,right;
private int height;
private int balanceFactor;
public Node(K key, V value){
this.key = key;
this.value = value;
this.left = null;
this.right = null;
this.height = 1;
}
@Override
public String toString() {
final StringBuffer sb = new StringBuffer("Node{");
sb.append("key=").append(key);
sb.append(", value=").append(value);
sb.append('}');
return sb.toString();
}
}
//2 定义属性
private int size;
private Node root;
/**
* getHeight
* @author weidoudou
* @date 2023/4/1 11:34
* @param node 请添加参数描述
* @return int
**/
private int getHeight(Node node){
if(null==node){
return 0;
}
return node.height;
}
/**
* getBalanceFactor
* @author weidoudou
* @date 2023/4/1 11:36
* @param node 请添加参数描述
* @return int
**/
private int getBalanceFactor(Node node){
if(null==node){
return 0;
}
return getHeight(node.left) - getHeight(node.right);
}
/**
* 无参构造函数
* @author weidoudou
* @date 2023/1/1 11:09
* @return null
**/
public AVLTree(){
this.size = 0;
this.root = null;
}
public boolean isEmpty() {
return size==0?true:false;
}
public int getSize() {
return size;
}
//3 定义包含函数
private Node containsKey(K key,Node node){
//结束条件
if(null==node){
return null;
}
//循环条件
if(key.compareTo(node.key)<0){
return containsKey(key,node.left);
}else if(key.compareTo(node.key)>0){
return containsKey(key, node.right);
}else{//key.compareTo(node.key)=0 其实这个也是结束条件
return node;
}
}
public boolean contains(K key) {
return containsKey(key,root)==null?false:true;
}
public V get(K key) {
Node node = containsKey(key,root);
if(null!=node){
return node.value;
}
return null;
}
//3 递归，添加元素
public void add(K key,V value,Node root){
//3.1 终止条件
//3.1.1 要插入的元素和二叉树原有节点相同,这个不用判断，因为已经调了containsKey方法判断了
/*if(key.equals(root.e)){
return;
}*/
//3.1.2 最终插入左孩子
if(key.compareTo(root.key)<0 && root.left==null){
root.left = new Node(key,value);
size++;
return;
}
//3.1.2 最终插入右孩子
if(key.compareTo(root.key)>0 && root.right == null){
root.right = new Node(key,value);
size++;
return;
}
//3.2 递归
//3.2.1 递归左孩子
if(key.compareTo(root.key)<0){
add(key,value,root.left);
}
//3.2.2 递归右孩子
if(key.compareTo(root.key)>0){
add(key,value,root.right);
}
root.height = 1+Math.max(getHeight(root.left),getHeight(root.right));
int balanceFactor = Math.abs(getBalanceFactor(root));
if(balanceFactor>1){
System.out.println("unbalanced:"+balanceFactor);
}
}
public void add(K key, V value) {
Node node = containsKey(key,root);
//未找到，插值
if(node==null){
//2.1 考虑特殊情况,如果是第一次调用，root为null
if(root==null){
root = new Node(key,value);
size++;
}else{
//2.2 添加递归方法
add(key,value,root);
}
}else{
node.value = value;
}
//找到后，更新值
}
public void set(K key, V value) {
Node node = containsKey(key,root);
if(node == null){
throw new IllegalArgumentException("要修改的值不存在");
}
node.value = value;
}
private Node remove(Node node,K key){
//终止条件1 基本判断不到，因为已经判断了containskey
/*if(node==null){
return null;
}*/
//递归
if(key.compareTo(node.key)<0){
node.left = remove(node.left,key);
return node;
}else if(key.compareTo(node.key)>0){
node.right = remove(node.right,key);
return node;
}else{
//已找到要删除的元素
//1 如果只有左子节点或只有右子节点，则直接将子节点替换
if(node.left==null){
return node.right;
}else if(node.right==null){
return node.left;
}else{
//2 如果有左子节点和右子节点，则寻找前驱或后继 对当前节点替换掉
Node nodeMain = findMin(node.right);
nodeMain.right = removMin(node.right);//这块一箭双雕，既把后继节点问题解决了，也把后继删除了
nodeMain.left = node.left;
node.left = node.right = null;
return node;
}
}
}
private Node findMin(Node node){
//1 终止条件
if(node.left==null){
return node;
}
//2 递归
return findMin(node.left);
}
private Node removMin(Node node){
//终止条件
if(node.left==null){
Node rightNode = node.right;
node.right = null;
return rightNode;
}
//递归
node.left = removMin(node.left);
return node;
}
/**
* 删除任意元素 若删除元素节点下只有一个节点直接接上即可，若有两个节点，则找前驱或后继，本节找前驱
* @author weidoudou
* @date 2023/1/1 11:52
* @param key 请添加参数描述
* @return V
**/
public V remove(K key) {
Node node = containsKey(key,root);
if(node == null){
throw new IllegalArgumentException("要修改的值不存在");
}
size--;
return remove(root, key).value;
}
//1 校验二分搜索树(中序遍历参考之前的中序遍历一节)
public boolean judgeBST(){
List<K> list = new ArrayList<>();
inOrder(root,list);
for(int i=1;i<list.size();i++){
if(list.get(i-1).compareTo(list.get(i))>0){
return false;
}
}
return true;
}
private void inOrder(Node root, List<K> list){
if(root==null){
return;
}
inOrder(root.left,list);
list.add(root.key);
inOrder(root.right,list);
}
//2 校验平衡二叉树
public boolean judgeBalance(){
return judgeBalance(root);
}
private boolean judgeBalance(Node node){
if(root == null){
return true;
}
if(Math.abs(getBalanceFactor(node))>1){
return false;
}
return judgeBalance(node.left)&&judgeBalance(node.right);
}
public static void main(String[] args) {
System.out.println("Pride and Prejudice");
ArrayList<String> words = new ArrayList<>();
if(FileOperation.readFile("pride-and-prejudice.txt",words)){
System.out.println("Total words: "+words.size());
AVLTree<String,Integer> avlTree = new AVLTree<>();
for(String word:words){
if(avlTree.contains(word)){
avlTree.set(word,avlTree.get(word)+1);
}else{
avlTree.add(word,1);
}
}
System.out.println("Total different words:"+avlTree.getSize());
System.out.println("judge BST:"+avlTree.judgeBST());
System.out.println("judge Balance:"+avlTree.judgeBalance());
}
}
}
文件处理类：
package com.company;
import java.io.FileInputStream;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Locale;
import java.io.File;
import java.io.BufferedInputStream;
import java.io.IOException;
// 文件相关操作
public class FileOperation {
// 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中
public static boolean readFile(String filename, ArrayList<String> words){
if (filename == null || words == null){
System.out.println("filename is null or words is null");
return false;
}
// 文件读取
Scanner scanner;
try {
File file = new File(filename);
if(file.exists()){
FileInputStream fis = new FileInputStream(file);
scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
scanner.useLocale(Locale.ENGLISH);
}
else
return false;
}
catch(IOException ioe){
System.out.println("Cannot open " + filename);
return false;
}
// 简单分词
// 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
// 在这里只做demo展示用
if (scanner.hasNextLine()) {
String contents = scanner.useDelimiter("\\A").next();
int start = firstCharacterIndex(contents, 0);
for (int i = start + 1; i <= contents.length(); )
if (i == contents.length() || !Character.isLetter(contents.charAt(i))) {
String word = contents.substring(start, i).toLowerCase();
words.add(word);
start = firstCharacterIndex(contents, i);
i = start + 1;
} else
i++;
}
return true;
}
// 寻找字符串s中，从start的位置开始的第一个字母字符的位置
private static int firstCharacterIndex(String s, int start){
for( int i = start ; i < s.length() ; i ++ )
if( Character.isLetter(s.charAt(i)) )
return i;
return s.length();
}
}
文件类：
见资源
测试结果：
unbalanced:2 unbalanced:8 unbalanced:3 unbalanced:4 unbalanced:7 Total different words:6530 judge BST:true judge Balance:false Class transformation time: 0.0251818s for 166 classes or 1.516975903614458E-4s per class Process finished with exit code 0
标签：node,Node,12,return,null,玩转,key,数据结构,root From： https://www.cnblogs.com/1446358788-qq/p/17297891.html