数据结构-二叉树(BTree)
程序员文章站
2024-01-19 13:02:04
...
BTree
特征:
1.一个节点最多只有两个子节点,其中左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。
2.执行查找,插入,删除的时间复杂度都是:O(logN)。
3.遍历有中序,前序,后序。前,中和后只是在递归的时候先输出左子,自己或右子的顺序。可以通过中排序,按左子,自己,右子的顺序就是升序,反之则是降序。
4.最大值是树的右边底层叶子;最小值是左边底层叶子。
JAVA代码实现:
package org.acooly.datastructure.btree;
import java.util.Random;
/**
* 特征:一个节点的左子节点的关键字小于这个节点,右子节点的关键字大于等于该节点。
*
* @author zhangpu
*
*/
public class BinaryTree {
/** 根节点 */
private Node root;
/**
* 查找
*
* @param key
* @return
*/
public Node find(int key) {
if (root == null) {
return null;
}
Node current = root;
while (current.getKey() != key) {
if (key < current.getKey()) {
// 小于本节点在左边
current = current.getLeftNode();
} else {
// 大于等于本节点在右边
current = current.getRightNode();
}
if (current == null) {
// 搜索到最后叶子为空,表示没有找到
return null;
}
}
return current;
}
public Node getParent(int key) {
if (root == null) {
return null;
}
Node current = root;
Node parent = root;
while (current.getKey() != key) {
if (key < current.getKey()) {
// 小于本节点在左边
parent = current;
current = current.getLeftNode();
} else {
// 大于等于本节点在右边
parent = current;
current = current.getRightNode();
}
if (current == null) {
// 搜索到最后叶子为空,表示没有找到
return null;
}
}
return parent;
}
/**
* 插入
*
* @param key
* @param value
*/
public void insert(int key, Object value) {
Node node = new Node(key, value);
if (root == null) {
root = node;
return;
}
Node current = root;
while (true) {
if (key < current.getKey()) {
if (current.getLeftNode() == null) {
current.setLeftNode(node);
return;
} else {
current = current.getLeftNode();
}
} else {
if (current.getRightNode() == null) {
current.setRightNode(node);
return;
} else {
current = current.getRightNode();
}
}
}
}
/**
* 中遍历(升序)
*
* @param startNode
*/
public void inOrderAsc(Node startNode) {
if (startNode != null) {
inOrderAsc(startNode.getLeftNode());
System.out.println(startNode);
inOrderAsc(startNode.getRightNode());
}
}
/**
* 中遍历(降序)
*
* @param startNode
*/
public void inOrderDesc(Node startNode) {
if (startNode != null) {
inOrderDesc(startNode.getRightNode());
System.out.println(startNode);
inOrderDesc(startNode.getLeftNode());
}
}
/**
* 最大值 算法:树中最底层的右子叶
*
* @return
*/
public Node getMax() {
Node current = root;
while (current.getRightNode() != null) {
current = current.getRightNode();
}
return current;
}
/**
* 算法:树中最底层的左子叶
*
* @return
*/
public Node getMin() {
return getMin(root);
}
/**
* 指定节点的最小节点,如果指定节点为root,则是树的最小节点
*
* @param localRoot
* @return
*/
private Node getMin(Node localRoot) {
Node current = localRoot;
while (current.getLeftNode() != null) {
current = current.getLeftNode();
}
return current;
}
/**
* 删除节点存在3中情况 <li>目标节点是叶子:直接删除,置为null <li>
* 目标节点只有一个子节点:如果目标节点是在父节点的左边,直接使用子节点作为父节点的左子,反正则为右子。 <li>
* 目标节点有两个子节点:找到后继节点,作为目标节点父节点的对应子节点。(后继:目标节点子节点中大于目标节点最小的个。路径:目标节点右子的最小节点。)
*
* @param key
*/
public void delete(int key) {
Node target = find(key);
if (target == null) {
return;
}
boolean leftExsit = (target.getLeftNode() != null ? true : false);
boolean rightExsit = (target.getRightNode() != null ? true : false);
// 第一种情况,目标是叶子,直接设置为null
if (!leftExsit && !rightExsit) {
target = null;
return;
}
// 获得目标的父节点
Node parent = getParent(key);
Node child = null;
if (leftExsit != rightExsit) {
// 第二种情况:只有一个子
child = (leftExsit ? target.getLeftNode() : target.getRightNode());
} else {
// 第三种情况:有两个子
Node rightChild = target.getRightNode();
child = getMin(rightChild);
getParent(child.getKey()).setLeftNode(null);
child.setRightNode(rightChild);
}
if (parent == null) {
root = child;
target = null;
return;
}
if (parent.getLeftNode() != null && target.getKey() < parent.getLeftNode().getKey()) {
// 目标是父的左子
parent.setLeftNode(child);
} else {
// 目标是父的右子
parent.setRightNode(child);
}
target = null;
}
public Node getRoot() {
return root;
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
Random random = new Random();
// INSERT
for (int i = 1; i <= 10; i++) {
int key = random.nextInt(100);
tree.insert(key, "value" + key);
}
int key = 0;
tree.insert(key, "value" + key);
System.out.println("TARGET key: " + key);
// FIND
System.out.println("FIND: " + tree.find(key));
// GETPARENT
System.out.println("PARENT: " + tree.getParent(key));
// MIX
System.out.println("MAX: " + tree.getMax());
// MIN
System.out.println("MIN: " + tree.getMin());
tree.delete(key);
System.out.println();
System.out.println("中遍历(升序):");
tree.inOrderAsc(tree.getRoot());
System.out.println("中遍历(降序):");
tree.inOrderDesc(tree.getRoot());
}
}
节点类:
package org.acooly.datastructure.btree;
/**
* BTree 节点
*
* @author zhangpu
*
*/
public class Node {
/** 节点KEY */
private int key;
private Object value;
/** 左子节点 */
private Node leftNode;
/** 右子节点 */
private Node rightNode;
public Node() {
super();
}
public Node(int key, Object value) {
super();
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(key) + "=" + value;
}
@Override
public boolean equals(Object obj) {
if(obj instanceof Node){
Node n = (Node)obj;
if(n.getKey() != getKey()){
return false;
}
}else{
return false;
}
return true;
}
}
上一篇: 纯css实现宽高等比缩放
下一篇: 二分实现的插入排序