数据结构之 二叉树 (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