Java数据结构之二叉查找树的实现

Java数据结构之二叉查找树的实现

目录定义节点结构查找算法插入算法删除算法完整代码

定义

二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，且各结点关键词互异，其中根序列按其关键词递增排列。

等价描述：二叉查找树中任一结点 P，其左子树中结点的关键词都小于 P 的关键词，右子树中结点的关键词都大于 P 的关键词，且结点 P 的左右子树也都是二叉查找树

节点结构

:one: key：关键字的值

:two: value：关键字的存储信息

:three: left：左节点的引用

:four: right：右节点的引用

class BSTNode,V>{

public K key;

public V value;

public BSTNode left;

public BSTNode right;

}

为了代码简洁，本文不考虑属性的封装，一律设为 public

查找算法

思想：利用二叉查找树的特性，左子树值小于根节点值，右子树值大于根节点值，从根节点开始搜索

如果目标值等于某节点值，返回该节点如果目标值小于某节点值，搜索该节点的左子树如果目标值大于某节点值，搜索该节点的右子树

:one: 递归版本

public BSTNode searchByRecursion(K key) {

return searchByRecursion(root, key);

}

private BSTNode searchByRecursion(BSTNode t, K key) {

if (t == null || t.key == key) return t;

else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);

else return searchByRecursion(t.right, key);

}

:two: 迭代版本

public BSTNode searchByIteration(K key) {

BSTNode p = this.root;

while(p != null) {

if(key.compareTo(p.key) < 0) p = p.left;

else if(key.compareTo(p.key) > 0) p = p.right;

else return p;

}

return null;

}

插入算法

在以 t 为根的二叉查找树中插入关键词为 key 的结点在 t 中查找 key ，在查找失败处插入

:one: 递归版本

public void insertByRecursion(K key, V value) {

this.root = insertByRecursion(root, key, value);

}

private BSTNode insertByRecursion(BSTNode t, K key, V value) {

if (t == null) {

return new BSTNode<>(key, value);

}

else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);

else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);

else {

t.value = value; // 如果二叉查找树中已经存在关键字，则替换该结点的值

}

return t;

}

:two: 迭代版本

public void insertByIteration(K key, V value) {

BSTNode p = root;

if (p == null) {

root = new BSTNode<>(key, value);

return;

}

BSTNode pre = null;

while (p != null) {

pre = p;

if (key.compareTo(p.key) < 0) p = p.left;

else if (key.compareTo(p.key) > 0) p = p.right;

else {

p.value = value; // 如果二叉查找树中已经存在关键字，则替换该结点的值

return;

}

}

if(key.compareTo(pre.key) < 0) {

pre.left = new BSTNode<>(key, value);

} else {

pre.right = new BSTNode<>(key, value);

}

}

删除算法

在以 t 为根的二叉查找树中删除关键词值为 key 的结点

在 t 中找到关键词为 key 的结点，分三种情况删除 key

1.若 key 是叶子节点，则直接删除

2.若 keLmpFbppy 只有一棵子树，则子承父业

3.若 key 既有左子树也有右子树，则找到 key 的后继结点，替换 key 和后继节点的值，然后删除后继节点（后继节点只有一棵子树，转化为第二种情况）。

后继结点是当前结点的右子树的最左结点，如果右子树没有左子树，则后继节点就是右子树的根节点。

public void removeByRecursion(K key) {

this.root = removeByRecursion(root, key);

}

private BSTNode removeByRecursion(BSTNode t, K key) {

if(t == null) return root;

else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，递归处理右子树

else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key); // key小，递归处理左子树

else {

if(t.right == null) return t.left; // 情况一、二一起处理

if(t.left == null) return t.right; // 情况一、二一起处理

BSTNode node = t.right; // 情况三：右子树没有左子树

if (node.left == null) {

node.left = t.left;

} else { // 情况三：右子树有左子树

BSTNode pre = null;

while (node.left != null) {

pre = node;

node = node.left;

}

t.key = node.key;

t.value = node.value;

pre.left = node.right;

}

}

return t;

}

完整代码

class BSTNode, V> {

public K key;

public V value;

public BSTNode left;

public BSTNode right;

public BSTNode(K key, V value) {

this.key = key;

this.value = value;

}

}

class BSTree, V> {

public BSTNode root;

private void inorder(BSTNode root) {

if (root != null) {

inorder(root.left);

System.out.print("(key: " + root.key + " , value: " + root.value + ") ");

inorder(root.right);

}

}

private void preorder(BSTNode root) {

if (root != null) {

System.out.print("(key: " + root.key + " , value: " + root.value + ") ");

preorder(root.left);

preorder(root.right);

}

}

private void postorder(BSTNode root) {

if (root != null) {

postorder(root.left);

postorder(root.right);

System.out.print("(kLmpFbppey: " + root.key + " , value: " + root.value + ") ");

}

}

public void postorderTraverse() {

System.out.print("后序遍历：");

postorder(root);

System.out.println();

}

public void preorderTraverse() {

System.out.print("先序遍历：");

preorder(root);

System.out.println();

}

public void inorderTraverse() {

System.out.print("中序遍历：");

inorder(root);

System.out.println();

}

public BSTNode searchByRecursion(K key) {

return searchByRecursion(root, key);

}

private BSTNode searchByRecursion(BSTNode t, K key) {

if (t == null || t.key == key) return t;

else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);

else return searchByRecursion(t.right, key);

}

public BSTNode searchByIteration(K key) {

BSTNode p = this.root;

while (p != null) {

if (key.compareTo(p.key) < 0) p = p.left;

else if (key.compareTo(p.key) > 0) p = p.right;

else return p;

}

return null;

}

public void insertByRecursion(K key, V value) {

this.root = insertByRecursion(root, key, value);

}

private BSTNode insertByRecursion(BSTNode t, K key, V value) {

if (t == null) {

return new BSTNode<>(key, value);

} else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);

else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);

else {

t.value = value;

}

return t;

}

public void insertByIteration(K key, V value) {

BSTNode p = root;

if (p == null) {

root = new BSTNode<>(key, value);

return;

}

BSTNode pre = null;

while (p != null) {

pre = p;

if (key.compareTo(p.key) < 0) p = p.left;

else if (key.compareTo(p.key) > 0) p = p.right;

else {

p.value = value; // 如果二叉查找树中已经存在关键字，则替换该结点的值

return;

}

}

if (key.compareTo(pre.key) < 0) {

pre.left = new BSTNode<>(key, value);

} else {

pre.right = new BSTNode<>(key, value);

}

}

public void removeByRecursion(K key) {

this.root = removeByRecursion(root, key);

}

private BSTNode removeByRecursion(BSTNode t, K key) {

if(t == null) return root;

else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，递归处理右子树

else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key); // key小，递归处理左子树

else {

if(t.right == null) return t.left; // 情况一、二一起处理

if(t.left == null) return t.right; // 情况一、二一起处理

BSTNode node = t.right; // 情况三：右子树没有左子树

if (node.left == null) {

node.left = t.left;

} else { // 情况三：右子树有左子树

BSTNode pre = null;

while (node.left != null) {

pre = node;

node = node.left;

}

t.key = node.key;

t.value = node.value;

pre.left = node.right;

}

}

return t;

}

}

:bug: 方法测试：

public class Main {

public static void main(String[] args) {

BSTree tree = new BSTree<>();

// tree.insertByRecursion(1, 1);

// tree.insertByRecursion(5, 1);

// tree.insertByRecursion(2, 1);

// tree.insertByRecursion(4, 1);

// tree.insertByRecursion(3, 1);

// tree.insertByRecursion(1, 2);

tree.insertByIteration(1, 1);

tree.insertByIteration(5, 1);

tree.insertByIteration(2, 1);

tree.insertByIteration(4, 1);

tree.insertByIteration(3, 1);

tree.insertByIteration(1, 5);

tree.removeByRecursion(4);

tree.inorderTraverse();

tree.postorderTraverse();

tree.preorderTraverse();

BSTNode node = tree.searchByIteration(1);

System.out.println(node.key + " " + node.value);

}

}

中序遍历：(key: 1 , value: 5) (key: 2 , value: 1) (key: 3 , value: 1) (key: 5 , value: 1) 后序遍历：(key: 3 , value: 1) (key: 2 , value: 1) (key: 5 , value: 1) (key: 1 , value: 5) 先序遍历：(key: 1 , value: 5) (key: 5 , value: 1) (key: 2 , value: 1) (key: 3 , value: 1) 1 5

以上就是java数据结构之二叉查找树的实现的详细内容，更多关于Java二叉查找树的资料请关注我们其它相关文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。