数据结构之 二叉树 （java 链表实现）
数据结构之 二叉树 （java 链表实现）
一.树
在介绍二叉树之前，先普及一下树的概念，和一些名词：
树有一下特点：
1.每个节点有一个或多个子结点，从A看那 B和C 就是A的子结点，那A就是B和C的父结点
2.没有父结点的结点叫根节点
3.每一个非根节点只有一个父结点
4.没个节点往下看都可以看作一颗树，左边的结点就叫 左子树，右边的节点就叫右子树；
树的相关名词：
节点：每一个树的最小组成单元，上面的ABCD
结点的度: 没一个节点的子节点总数
树的度：选取所有结点中最大的度，就是树的度
叶子结点：度为0的结点就是叶子结点，它位于树最深层，并且树只要非空，就一定存在叶子结点
分支结点：度大于0的结点为分支结点，显然除了叶子结点之外的结点都为分支结点
路径(path)：从一个结点到另一个结点之间的边和结点构成路径
树的深度：与树的度对应于结点的度一样，树的深度也是选取结点中的最大深度
二.二叉树
二叉树呢是一种特殊的树，具又一下特点：
1、普通二叉树的特点：
（1）结点的度：一个结点含有的子树的个数（0，1，2）；
（2）在非空二叉树中，第i层的结点总数不超过 ， i>=1；
（3）深度为h的二叉树最多有 个结点(h>=1)，最少有h个结点；
（4）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
我们今天要实现的是二叉查找树：他具有下特点：（官方定义）
1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
2. 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树
基于这个特点我们上代码
package com.data.structure;
public class BinaryTree <K,V>{
//根节点
private Node<K,V> root;
// //树的高度
// private int height ;
//节点总树
private int size;
public int getSize() {
return size;
}
class Node<K,V> {
//存储数据对象
K key;
V value;
//左子树
Node<K,V> leftTree;
//右子树
Node<K,V> rightTree;
public Node() {
}
public Node(K key, V value, Node<K, V> leftTree, Node<K, V> rightTree) {
this.key = key;
this.value = value;
this.leftTree = leftTree;
this.rightTree = rightTree;
}
}
public void put(K key, V value){
root=putTree(root,key,value);
}
public Node<K,V> putTree(Node root,K k, V v){
if (root==null){
//如果根节点为null 把当前节点作为根节点
//节点数量加一
size++;
return new Node<>(k,v,null,null);
}
int newKey = k.hashCode();
int rootKey = root.key.hashCode();
if (newKey>rootKey){
//利用递归把右节点作为根节点继续往下找
root.rightTree= putTree(root.rightTree ,k,v);
}else if (newKey<rootKey){
//利用递归把右左点作为根节点继续往下找
root.leftTree= putTree(root.leftTree,k,v);
}else {
//如果key 相等就做 覆盖操作
root.value=v;
}
//返回这棵树的根节点
return root;
}
public V getValue(K key){
Node<K,V> currNode= getTree(root,key);
if (currNode!=null){
return currNode.value;
}
return null;
}
public Node<K,V> getTree( Node<K,V> tree,K k ){
//如果当前节点为空，说明没有找到
if (tree==null){
return null;
}
//用k的hashCode 作为比较依据
int newKey = k.hashCode();
int rootKey = tree.key.hashCode();
if (newKey>rootKey){
//利用递归把右节点作为根节点继续往下找
return getTree(tree.rightTree,k);
}else if (newKey<rootKey){
//利用递归把右左点作为根节点继续往下找
return getTree(tree.leftTree,k);
}else {
//如果key 相等就返回当前的
return tree;
}
}
public void delete(K key ){
root=deleteTree(root,key);
}
public Node<K,V> deleteTree(Node<K,V> tree ,K k){
if(tree==null){
//树是空的，不删除
return null;
}
int newKey = k.hashCode();
int rootKey = tree.key.hashCode();
//如果要删除的节点 大于 根节点 说明要删除的节点在 根节点的右边
if (newKey>rootKey){
tree.rightTree=deleteTree(tree.rightTree,k);
}else if(newKey<rootKey){
//如果要删除的节点 小于 根节点 说明要删除节点在 根节点的左边
tree.leftTree=deleteTree(tree.leftTree,k);
}else {
//key 相等说明 找到了要删除的节点
//如果要删除节点的右节点不存在
if (tree.rightTree==null){
//自己让根节点指向 要删除节点的左节点
size--;
return tree.leftTree;
}
//如果要删除的节点的左节点不存在
if (tree.leftTree==null){
size--;
return tree.rightTree;
}
//如果左右都存在，那就找到 右子树中最小的叶子节点
Node<K,V> rTree=tree.rightTree;
Node<K,V> tempRTree=rTree;
while (rTree.leftTree!=null){
//说明下一个左节点就是叶子节点（最后一个节点）
if (rTree.leftTree.leftTree==null){
tempRTree=tree.leftTree;
//删除最后一个节点
rTree.leftTree=null;
break;
}
}
//让Tree的左子树和右子树变成，tempRTree 的左右子树
tempRTree.leftTree=tree.leftTree;
tempRTree.rightTree=tree.rightTree;
tree=tempRTree;
//返回TempTree
size--;
}
return tree;
}
}
由于他的put 方法和get 方法 比较简单主要是利用递归去实现的，就不画图了我这里要解释的主要是他 删除的方法：
情况1（要删除的节点没有左子树）
直接让根节点指向要删除的节点的右节点
情况2（要删除的节点没有右简单，和情况一类似就不画了）
情况3(要删除的节点有左右子树)
假设我们要删除上述二叉树的中的 8，我可以 去找到 8的右节点中左节点 10 把8替换成 10 然后 把13指向10的这条引用给删除掉这样就可一个即满足二叉树的特性，又完成了删除操作（因为，右子树的值一定比左子树大，所以选择右子树中的最小的节点，也就是右子树中的最后一个左子树作为替换）2
测试一下代码：
完美成功！
今天的分享就到这了，大佬评论区见
————————————————
版权声明：本文为CSDN博主「javaLeadrWei」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_42711376/article/details/114714416