二叉搜索树(二叉查找树,排序二叉树,有序二叉树)
定义
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
【注】：以上的三种定义在不同的数据结构教材中均有不同的定义方式 但是都是正确的 在开发时需要根据不 同的需求进行选择
【注2】：没有键值相等的结点。
实现
// 二叉搜索树类
public class BinarySearchTree{
// 节点类
private class Node{
// 数据域
int data;
// 右子树
Node right;
// 左子树
Node left;
}
// 根节点
private Node root;
//insert
public void insert(int key){
// 待插入的节点
Node p = new Node();
p.data = key;
if (root == null){
root = p;
}else{
Node parent = new Node();
Node current = root;
while (true){
parent = current;
if (key > current.data){
current = current.right; // 右子树
if (current == null){
parent.right = p;
return;
}
}else {
// 本程序没有做key出现相等情况的处理，暂且假设用户插入的节点值都不同
current = current.left; // 左子树
if (current == null){
parent.left = p;
return;
}
}
}
}
}
//delete
//寻找要删除节点的中序后继结点
private Node getSuccessor(Node delNode){
Node successorParent=delNode;
Node successor=delNode;
Node current=delNode.right;
//用来寻找后继结点
while(current!=null){
successorParent=successor;
successor=current;
current=current.left;
}
//如果后继结点为要删除结点的右子树的左子，需要预先调整一下要删除结点的右子树
if(successor!=delNode.right) {
successorParent.left=successor.right;
successor.right=delNode.right;
}
return successor;
}
public boolean delete(int key){
Node current = root;
Node parent = new Node();
boolean isRightChild = true;
while (current.data != key)
parent = current;
if (key > current.data){
current = current.right;
isRightChild = true;
}else{
current = current.left;
isRightChild = false;
}
// 没有找到要删除的结点
if (current == null) return false;
// 此时current就是要删除的结点,parent为其父结点
// 要删除结点为叶子结点
if (current.right == null && current.left == null) {
if (current == root){
root = null; // 整棵树清空
}else{
if (isRightChild)
parent.right = null;
else
parent.left = null;
}
return true;
}else if(current.left==null){
//要删除结点有一个子结点
if(current==root)
root=current.right;
else if(isRightChild)
parent.right=current.right;
else
parent.left=current.right;
return true;
}else if(current.right==null){
if(current==root)
root=current.left;
else if(isRightChild)
parent.right=current.left;
else
parent.left=current.left;
return true;
}else{
//要删除结点有两个子结点
//找到要删除结点的后继结点
Node successor=getSuccessor(current);
if(current==root)
root=successor;
else if(isRightChild)
parent.right=successor;
else
parent.left=successor;
successor.left=current.left;
return true;
}
}
//update
//select
// 选择以何种方式遍历
public void traverse(int traverseType){
switch (traverseType){
case 1:
System.out.print("preOrder traversal ");
preOrder(root);
System.out.println();
break;
case 2:
System.out.print("inOrder traversal ");
inOrder(root);
System.out.println();
break;
case 3:
System.out.print("postOrder traversal ");
postOrder(root);
System.out.println();
break;
}
}
// 前序遍历,"中左右"
public void preOrder(Node root){
if (root != null){
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
}
// 中序遍历,"左中右"
public void inOrder(Node root){
if (root != null){
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
}
// 后序遍历,"左右中"
public void postOrder(Node root){
if (root != null){
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + " ");
}
}
// 从树中按照关键值查找元素
public Node find(int key){
Node current = root;
while (current.data != key){
if (key > current.data)
current = current.right;
else
current = current.left;
if (current == null) return null;
}
return current;
}
//输出节点的数据域
public void show(Node node){
if(node!=null)
System.out.println(node.data);
else
System.out.println("null");
}
public static void main(String[] args){
BinarySearchTree tree = new BinarySearchTree();
tree.insert(39);
tree.insert(24);
tree.insert(64);
tree.insert(23);
tree.insert(30);
tree.insert(53);
tree.insert(60);
/**
* 39
* / \
* 24 64
* / \ /
* 23 30 53
* \
* 60
*
*/
tree.traverse(1);
//preOrder traversal 39 24 23 30 64 53 60
tree.traverse(2);
//inOrder traversal 23 24 30 39 53 60 64
tree.traverse(3);
//postOrder traversal 23 30 24 60 53 64 39
tree.show(tree.find(23));
//23
//tree.show(tree.find(60));
//tree.show(tree.find(64));
tree.delete(23);
//tree.delete(60);
//tree.delete(64);
tree.show(tree.find(23));
//
//tree.show(tree.find(60));
//tree.show(tree.find(64));
}
}Last updated