数据结构树的算法,java树形数据结构
一.导言：二叉查找树的历史。
二叉查找树算法是由几位研究人员独立发现的，包括PF Windley、安德鲁唐纳德布思、Andrew Colin和Thomas N. Hibbard。这种算法归功于康威伯纳斯李和大卫惠勒，他们在1960年使用这种算法将标签数据存储在磁带中。最早和最流行的二叉查找树算法之一是Hibbard算法。
二、二叉查找树数据结构二叉查找树，又称二叉查找树。如果你看到有序二叉树和排序二叉树，是一回事。
如果任一节点的左子树不为空，则左子树中所有节点的值都小于其根节点的值；如果任一节点的右子树不为空，则右子树中所有节点的值都大于其根节点的值；任意节点的左右子树也是二分搜索法树；二叉查找树在日常开发中应用广泛，比如基于组合模式的规则引擎，就是一个二叉查找树。但是像这样开发用的二叉树场景都是基于配置生成的，所以组合的节点更方便控制树的高度和平衡。这与Java API HashMap中的红黑树不同，红黑树可以在插入节点后保持树的平衡。
因此，二叉查找树也是一个没有被平衡的基本数据结构。在一定概率下，可能退化为链表，即从近似O(logn)到O(n)的时间复杂度。二叉查找树的平衡解决方案，包括：AVL树，2-3树，红黑树等。这一点福哥将在后续章节中继续实施。
二叉查找树结构的实现二叉查找树是整个树形结构中最基本的树，也是树形系统中最容易实现的数据结构。然而，使用基于二叉查找树的其他树结构，主要是因为数据结构用于存储和读取数据。然后为了提高吞吐效率，需要尽可能平衡元素的排序，树中需要一些列操作，所以会有不同的结构树实现。
二叉查找树的实现是最好的基础学习，了解了基本的数据结构之后再扩展学习其他的树结构就更容易了。
1\.分支定义公共整数值；
公共节点父节点；
公共节点左；
公共节点权限；用于形成树的节点需要包括：值和与之关联的三角形结构，一个父节点和两个子节点。如果AVL树还需要树高，红黑树也需要染色标记。
2\.插入节点公共节点插入(int e) {
if (null==root) {
root=新节点(e，null，null，null)；
尺寸；
返回根目录；
}
//Index要插入的元素的位置，即插入到哪个父元素的下面。
节点parent=root
节点搜索=根；
而(搜索！=空搜索值！=null) {
parent=search
if (e search.value) {
search=search.left
}否则{
search=search.right
}
}
//插入元素
Node newNode=新节点(e，parent，null，null)；
if (parent.value newNode.value) {
parent.left=newNode
}否则{
parent.right=newNode
}
尺寸；
返回newNode
}首先在插入元素时判断是否有根，如果没有，则创建当前节点的一个根。
如果当前树有根，则在插入的元素和当前树之间执行节点遍历操作，找到可以插入元素的索引位置父节点(挂在此父节点下)。也就是搜索过程。
最后，通过为插入的值创建一个节点节点，绑定其父元素，并将新元素挂在索引的父节点下，来插入元素。
3\.信息节点公共节点搜索(int e) {
Node node=root
while(节点！=null node.value！=null node.value！=e) {
if (e node.value) {
node=node.left
}否则{
node=node.right
}
}
返回节点；
}值搜索的过程是遍历二叉查找树，不断循环节点，根据节点值的左右匹配，找出最终的等值节点。
4\.删除节点公共节点delete(int e) {
node delNode=search(e)；
if (null==delNode)返回null；
return delete(delNode)；
}
私有节点删除(节点delNode) {
if (delNode==null)返回null；
节点结果=null
if (delNode.left==null) {
result=transplant(delNode，delNode . right)；
} else if (delNode.right==null) {
result=transplant(delNode，delNode . left)；
}否则{
//因为删除了节点，所以有2个子节点。此时，在该分支下，找到最左边的节点作为小节点。用它来替换被删除的节点。
node miniNode=getMiniNode(del node . right)；
if(min node . parent！=delNode) {
//交换位置，用min node的右节点替换min node。
移植(miniNode，min node . right)；
//提升miniNode到父节点，设置右边子树，挂链。要删除的替代点
min node . right=del node . right；
min node . right . parent=min node；
}
//交换位置、删除节点和miniNode可打印测试观察；system . out . println(this)；
移植(delNode，mini node)；
//提升miniNode到父节点，设置左子树，挂链。
min node . left=del node . left；
min node . left . parent=min node；
result=miniNode
}
尺寸-；
返回结果；
}
私有节点getMinimum(Node node) {
while (node.left！=null) {
node=node.left
}
返回节点；
}
私有节点移植(节点delNode，节点addNode) {
if (delNode.parent==null) {
this.root=addNode
}
//确定被删除的元素是左/右节点。
else if(del node . parent . left==del node){
del node . parent . left=add node；
}否则{
del node . parent . right=add node；
}
//设置父节点
if (null！=addNode) {
add node . parent=del node . parent；
}
返回addNode
}4.1删除单个节点
删除节点14，判断这个节点的父节点的子节点，等于14，找出左右节点。
将要删除的点的右子节点挂在已删除节点的右节点上。
将上层父节点设置为要删除的点的右侧子节点。
4.2删除双节点
如果要删除的节点64包含两个孩子，则需要根据第一个右孩子找到最小的左孩子。从89到72，如果有小于72的左子节点，继续故障排除。检查节点72，并将准备替换要删除的元素的节点72的位置与右子节点73交换。过程与4.1中的相同。最后，使用交换函数移植将节点72与要删除的节点64交换，三角关系、父节点、左子节点和右子节点被替换。4.二叉查找树的功能测试。为了方便观察树木结构的变化，在这里，付晓师兄找到了一些资料。一种是我们可以通过程序打印出来(类似于之前打印99张乘法表，另一种是使用在线可视化：https://visualgo.net/zh/bst?幻灯片=1)
1\.随机插入@Test元素
公共void test_binary_search_tree() {
binary search tree tree=new binary search tree()；
for(int I=0；i i ) {
tree.insert(new Random()。nextInt(100))；
}
system . out . println(tree)；
}测试结果/- 91
\ - 78
/- 74
\ - 67
61
/- 51
\ - 40
/- 28
\ - 14
\ - 7
进程以退出代码0结束因为你测试的随机数是不同的，可能有许多不同结构的二分搜索法树，或者一个退化的树有相似的链表结构。
2\.插入和删除@Test
public void test _ insert _ delete(){
binary search tree tree=new binary search tree()；
tree . insert(32)；
tree . insert(7)；
tree . insert(64)；
tree . insert(63)；
tree . insert(89)；
tree . insert(72)；
tree . insert(94)；
tree . insert(6)；
tree . insert(14)；
tree . insert(18)；
tree . insert(73)；
system . out . println(tree)；
//删除只有一个子级父节点的单个节点。
//tree . delete(14)；
//删除双节点，即有两个子节点的父节点
tree . delete(64)；
system . out . println(tree)；
}测试结果/- 94
/- 89
/- 73
\ - 72
/- 64
\ - 63
32
/- 18
/- 14
\ - 7
\ - 6
/- 94
/- 89
\ - 73
/- 72
\ - 63
32
/- 18
/- 14
\ - 7
\ - 6
以退出代码0结束流程的情况是在4.2中删除两个节点的情况。删除节点64后，提取并使用节点72。读者也可以尝试删除其他节点测试验证。
动词（verb的缩写）常见面试问题的二叉查找树结构简介。改T的可能性也可以手写。
插入、删除和索引二叉查找树的时间复杂度。
在二叉查找树删除具有双节点的元素的过程描述。
二叉查找树的节点包含哪些信息？
为什么Java HashMap说红黑树而不是二叉查找树？
版权归作者所有：原创作品来自博主小二上九8，转载请联系作者取得转载授权，否则将追究法律责任。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。