-
编程语言
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
小标
2018-08-30
来源 ：
阅读 1482
评论 0
摘要：本文主要向大家介绍了JAVA语言实现二叉树的代码教程，通过具体的内容向大家展示，希望对大家学习JAVA语言有所帮助。
本文主要向大家介绍了JAVA语言实现二叉树的代码教程，通过具体的内容向大家展示，希望对大家学习JAVA语言有所帮助。
1.二叉树
数组：查询快，插入慢
链表：查询慢，插入快
而二叉树结构既能快速查找，也能快速添加
2.特点
一个节点的左子节点的关键字值小于这个节点，右子节点的关键字值大于或等于这个父节点
3.源码实现
public class BinaryTree {
private Node root;
public Node find(int key){
Node current = root;
while(null != current){
if(current.id == key){
return current;
}else if(key > current.id){
current = current.right;
}else{
current = current.left;
}
}
return null;
}
public void insert(int id,String v){
// 1.创建节点
Node node = new Node();
node.id = id;
node.value = v;
// 2.根节点为null时，将当前直接置为根节点
if(null == root){
root = node;
// 3.遍历节点
}else{
Node parent = root;
Node current = root;
while(null != current){
parent = current;
if(id < current.id){//left
current = current.left;
if(null == current){
parent.left = node;
return;
}
}else {//right
current = current.right;
if(null == current){
parent.right = node;
return;
}
}
}
}
}
public boolean delete(int key){
// 1.查找被删除节点
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.id != key){
parent = current;
if(key > current.id){
current = current.right;
isLeftChild = false;
}else{
current = current.left;
isLeftChild = true;
}
if(null == current){
return false;
}
}
// 2.1被删除节点没有子节点
if(null == current.left && null == current.right){
if(current == root){
root = null;
}else{
if(isLeftChild){
parent.left = null;
}else{
parent.right = null;
}
}
}
// 2.2被删除节点有一个子节点
else if(null == current.left){
if(current == root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}
else if (null == current.right){
if(current == root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else {
parent.right = current.left;
}
}
// 2.3被删除节点有两个子节点
else{
Node succeedNode = getSucceedNode(current);//后继节点
if(current == root){
root = succeedNode;
}else if(isLeftChild){
parent.left = succeedNode;
}else{
parent.right = succeedNode;
}
succeedNode.left = current.left;
}
return true;
}
// 获取被删除节点的后继节点（专为被删除节点有两个子节点使用）
private Node getSucceedNode(Node delNode){
Node parent = delNode;
Node succeed = delNode;
Node current = delNode.right;//从右节点开始
//获取左子节点，一直到最后一个左子孙节点，就是比删除节点的次大节点
while(null != current){
parent = succeed;
succeed = current;
current = current.left;
}
if(succeed != delNode.right){
parent.left = succeed.right;//后继节点要被替换到delNode的位置，所以需要把后继节点的右节点替换给parent的左节点
succeed.right = delNode.right;//后继节点的现右子节点就是delNode的右子节点
}
return succeed;
}
//前序遍历
public String perOrder(Node node){
StringBuilder sb = new StringBuilder();
if(null != node){
sb.append(node.id).append(" ");
sb.append(perOrder(node.left)).append(" ");
sb.append(perOrder(node.right)).append(" ");
}
return sb.toString();
}
//中序遍历
public String inOrder(Node node){
StringBuilder sb = new StringBuilder();
if(null != node){
sb.append(inOrder(node.left)).append(" ");
sb.append(node.id).append(" ");
sb.append(inOrder(node.right)).append(" ");
}
return sb.toString();
}
//后序遍历
public String postOrder(Node node){
StringBuilder sb = new StringBuilder();
if(null != node){
sb.append(postOrder(node.left)).append(" ");
sb.append(postOrder(node.right)).append(" ");
sb.append(node.id).append(" ");
}
return sb.toString();
}
//节点类
class Node{
public int id;//节点key
public String value;//节点值
public Node left;
public Node right;
@Override
public String toString() {
return "id:"+id+",value:"+value;
}
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
}
本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道！
喜欢 | 1
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
