大家好，又见面了，我是你们的朋友全栈君。为什么实用二叉树
一,在有序数组中插入删除数据太慢
1插入或者删除一条数据会移动后面的所有数据
二,在链表中查找数据太慢
2查找只能从头或者尾部一条一条的找
用树解决问题
有没有一种插入和删除像链表那么快，查询可以向有序数组一样查得快那样就好了。
数实现了这些特点，称为了最有意思的数据结构之一
树的术语
如下图
树分平衡树和非平衡树
二叉树的类
public class Tree {
/**
* 跟节点
*/
private Node root;
/**
* 构造方法
*/
public Tree() {
}
/**
* 构造方法
*
* @param root
* 跟节点
*/
public Tree(Node root) {
this.root = root;
}
}
class Node {
/* key */
int key;
/* 值 */
Object value;
/* 左节点 */
Node leftChildNode;
/* 右节点 */
Node rightChildNode;
/**
* 构造方法
*
* @param key
* 关键字
* @param value
* 值
*/
public Node(int key, Object value) {
super();
this.key = key;
this.value = value;
}
}
二叉树插入功能
/**
* 插入节点
*
* @param key
* key
* @param value
* 值
*/
public void insert(int key, Object value) {
Node node = new Node(key, value);
if (this.root == null) {
this.root = node;
} else {
Node currentNode = this.root;
while (true) {
if (key > currentNode.key) {
if (currentNode.rightChildNode == null) {
currentNode.rightChildNode = node;
return;
} else {
currentNode = currentNode.rightChildNode;
}
} else {
if (currentNode.leftChildNode == null) {
currentNode.leftChildNode = node;
return;
} else {
currentNode = currentNode.leftChildNode;
}
}
}
}
}
二叉树的查找功能
/**
* 查找节点
*
* @param key
* @return
*/
public Node find(int key) {
if (this.root != null) {
Node currentNode = this.root;
while (currentNode.key != key) {
if (key > currentNode.key) {
currentNode = currentNode.rightChildNode;
} else {
currentNode = currentNode.leftChildNode;
}
if (currentNode == null) {
return null;
}
}
}
return currentNode ;
} 二叉树的展示功能（中序遍历）
private void show(Node node) {
if (node != null) {
this.show(node.leftChildNode);
System.out.println(node.key + ":" + node.value);
this.show(node.rightChildNode);
}
}测试
public static void main(String[] args) {
Node root = new Node(50, 24);
Tree tree = new Tree(root);
tree.insert(20, 530);
tree.insert(540, 520);
tree.insert(4, 540);
tree.insert(0, 550);
tree.insert(8, 520);
tree.show();
}
完整代码
package tree;
/**
* 二叉树
*
* @author JYC506
*
*/
public class Tree {
/**
* 跟节点
*/
private Node root;
/**
* 构造方法
*/
public Tree() {
}
/**
* 构造方法
*
* @param root
* 跟节点
*/
public Tree(Node root) {
this.root = root;
}
/**
* 查找节点
*
* @param key
* @return
*/
public Node find(int key) {
if (this.root != null) {
Node currentNode = this.root;
while (currentNode.key != key) {
if (key > currentNode.key) {
currentNode = currentNode.rightChildNode;
} else {
currentNode = currentNode.leftChildNode;
}
if (currentNode == null) {
return null;
}
}
}
return null;
}
/**
* 插入节点
*
* @param key
* key
* @param value
* 值
*/
public void insert(int key, Object value) {
Node node = new Node(key, value);
if (this.root == null) {
this.root = node;
} else {
Node currentNode = this.root;
while (true) {
if (key > currentNode.key) {
if (currentNode.rightChildNode == null) {
currentNode.rightChildNode = node;
return;
} else {
currentNode = currentNode.rightChildNode;
}
} else {
if (currentNode.leftChildNode == null) {
currentNode.leftChildNode = node;
return;
} else {
currentNode = currentNode.leftChildNode;
}
}
}
}
}
/**
* 展示
*/
public void show() {
this.show(root);
}
/**
* 中序遍历
*
* @param node
*/
private void show(Node node) {
if (node != null) {
this.show(node.leftChildNode);
System.out.println(node.key + ":" + node.value);
this.show(node.rightChildNode);
}
}
public static void main(String[] args) {
Node root = new Node(50, 24);
Tree tree = new Tree(root);
tree.insert(20, 530);
tree.insert(540, 520);
tree.insert(4, 540);
tree.insert(0, 550);
tree.insert(8, 520);
tree.show();
}
}
class Node {
/* key */
int key;
/* 值 */
Object value;
/* 左节点 */
Node leftChildNode;
/* 右节点 */
Node rightChildNode;
/**
* 构造方法
*
* @param key
* 关键字
* @param value
* 值
*/
public Node(int key, Object value) {
super();
this.key = key;
this.value = value;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/127080.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...