JAVA语言二进制树代码实现教程

本文主要介绍用Java语言实现二进制树的代码教程. 我将通过特定内容向您展示. 希望对大家学习JAVA语言有帮助.

1. 二叉树

数组: 快速查询二叉树 java实现，插入缓慢

链接列表: 查询慢，插入快

可以快速找到并快速添加二叉树结构

2. 功能

一个节点的左子节点的关键字值小于此节点，而右子节点的关键字值大于或等于此父节点

3. 源代码实现

publicclassBinaryTree {

privateNode根;

publicNode查找（intkey）{

节点当前=根;

while（空！=当前）{

如果（current.id ==键）{

返回电流；

} elseif（键> current.id）{

current = current.right;

}其他{

current = current.left;

}

}

returnnull;

}

publicvoidinsert（intid，字符串v）{

// 1.创建一个节点

节点node = newNode（）;

node.id = id;

node.value = v;

// 2.当根节点为空时，直接将当前节点设置为根节点

if（null == root）{

root =节点；

// 3.遍历节点

}其他{

Node parent = root;

节点当前=根;

while（空！=当前）{

parent = current;

if（id

current = current.left;

如果（null ==当前）{

parent.left =节点；

返回；

}

}其他{//对

current = current.right;

如果（null ==当前）{

parent.right =节点；

返回；

}

}

}

}

}

publicbooleandelete（intkey）{

// 1.查找已删除的节点

Node parent = root;

节点当前=根;

booleanisLeftChild = false;

while（current.id！= key）{

parent = current;

if（key> current.id）{

current = current.right;

isLeftChild = false;

}其他{

current = current.left;

isLeftChild = true;

}

如果（null ==当前）{

returnfalse;

}

}

// 2.1删除的节点没有子节点

if（null == current.left && null == current.right）{

if（当前==根）{

root = null;

}其他{

如果（isLeftChild）{

parent.left = null;

}其他{

parent.right = null;

}

}

}

// 2.2删除的节点有一个子节点

elseif（null == current.left）{

if（当前==根）{

root = current.right;

} elseif（isLeftChild）{

parent.left = current.right;

}其他{

parent.right = current.right;

}

}

elseif（null == current.right）{

if（当前==根）{

root = current.left;

} elseif（isLeftChild）{

parent.left = current.left;

}其他{

parent.right = current.left;

}

}

// 2.3删除的节点有两个子节点

其他{

Node successNode = getSucceedNode（当前）； //后续节点

if（当前==根）{

root = successNode;

} elseif（isLeftChild）{

parent.left = successNode;

}其他{

parent.right = successNode;

}

succeedNode.left = current.left;

}

returntrue;

}

//获取已删除节点的后继节点（专为具有两个子节点的已删除节点而设计）

privateNode getSucceedNode（节点delNode）{

Node parent = delNode;

节点成功= delNode;

节点当前= delNode.right; //从正确的节点开始

//获取左子节点直到最后一个左子节点二叉树 java实现，这是被删除节点之后的第二大节点

while（空！=当前）{

父母=成功；

成功=当前；

current = current.left;

}

如果（成功！= delNode.right）{

parent.left = success.right; //将后继节点替换到delNode的位置，因此后继节点的右节点需要替换为父节点的左节点

succeed.right = delNode.right; //后继节点的当前右子节点是delNode的右子节点

}

成功；

}

//预购遍历

publicString perOrder（节点节点）{

StringBuilder sb = newStringBuilder（）;

if（null！=节点）{

sb.append（node.id）.append（“”）;

sb.append（perOrder（node.left））. 追加（“”）;

sb.append（perOrder（node.right））. 追加（“”）;

}

returnsb.toString（）;

}

//中阶遍历

publicString inOrder（节点节点）{

StringBuilder sb = newStringBuilder（）;

if（null！=节点）{

sb.append（顺序（node.left））. 追加（“”）;

sb.append（node.id）.append（“”）;

sb.append（顺序（node.right））. 追加（“”）;

}

returnsb.toString（）;

}

//后遍历

publicString postOrder（节点节点）{

StringBuilder sb = newStringBuilder（）;

if（null！=节点）{

sb.append（postOrder（node.left））. 追加（“”）;

sb.append（postOrder（node.right））. 追加（“”）;

sb.append（node.id）.append（“”）;

}

returnsb.toString（）;

}

//节点类

classNode {

publicintid; //节点密钥

publicString值； //节点值

publicNode左；

publicNode权限；

@Override

publicString toString（）{

返回“ id: ” + id +“，值: ” +值；

}

}

publicNode getRoot（）{

returnroot;

}

publicvoidsetRoot（节点根）{

this.root = root;

}

}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-147610-1.html