二叉查找树，非递归实现
结构
查找的时间复杂度 O(logN)
对于一个二叉树的每个节点，大于左儿子，小于右儿子。
左边的是查找树，右边的不是，7>6
class ADTTreeNode<E extends Comparable<E>>{
E data;
ADTTreeNode<E> left;
ADTTreeNode<E> right;
public ADTTreeNode(E e, ADTTreeNode<E> left, ADTTreeNode<E> right) {
this.data = e;
this.left = left;
this.right = right;
}
}
contains方法
从根开始比较，大于就往右继续比较，小于就往左，直到相等，返回true，否则返回false
public Boolean contains(E e){
ADTTreeNode<E> a = root;
if (a == null){
return false;
}
while (a!=null){
int result = e.compareTo(a.data);
if (result < 0){
a = a.left;
}else if (result > 0){
a = a.right;
}else{
return true;
}
}
return false;
}
findMin和findMax
findMin：一路往左，直到没有，返回
public E finMin(){
ADTTreeNode<E> a = root;
while (a.left!=null){
a = a.left;
}
return a.data;
}
findMax：一路往右，直到没有，返回
public E finMax(){
ADTTreeNode<E> a = root;
while (a.right!=null){
a = a.right;
}
return a.data;
}
insert
从根开始比较，大于往右，小于往左，相等就表示已经存在，什么都不做，否则，插入到遍历的最后一个节点。
public void insert(E e){
ADTTreeNode<E> p = new ADTTreeNode<E>(e,null,null);
if (root == null){
root = p;
}else {
ADTTreeNode<E> a = root;
ADTTreeNode<E> b = null;
int result = 0;
while (a!=null) {
b = a;
result = e.compareTo(a.data);
if (result < 0) {
a = a.left;
} else if (result > 0) {
a = a.right;
} else {
break;
}
}
if (result < 0){
b.left = p;
}else if (result > 0){
b.right = p;
}else {
}
}
}
remove
三种情况
- 如果需要删除的节点是个叶子，直接删除
- 如果需要删除的节点有一个儿子，调整该节点的父节点的链，使它指向该节点的儿子
- 如果需要删除的节点有两个儿子，找到该节点右子树上的最小的节点，替换需要删除的节点，再把这个最小节点像第二种情况那样删除。
public void remove(E e){
ADTTreeNode<E> a = root;
ADTTreeNode<E> b = null;
int result = 1;
int x = 1;
while (e.compareTo(a.data) != 0){
b = a;
result = e.compareTo(a.data);
if (result < 0){
a = a.left;
x = -1;
}else if (result > 0){
a = a.right;
x = 1;
}
}
if (a.left != null && a.right!= null){
ADTTreeNode<E> p = a.right;
while (p.left!=null){
p = p.left;
}
a.data = p.data;
a.right = p.right;
}else {
if (x < 0) {
b.left = (a.left != null) ? a.left : a.right;
}else {
b.right = (a.left != null) ? a.left : a.right;
}
}
}
具体实现
package com.yb.shujujiegou.shu;
/**
* 二叉查找树
* Created by 杨波 on 2017/5/8.
*/
public class ADTBinaryTree<E extends Comparable<E>> {
public static class ADTTreeNode<E extends Comparable<E>>{
E data;
ADTTreeNode<E> left;
ADTTreeNode<E> right;
public ADTTreeNode(E e, ADTTreeNode<E> left, ADTTreeNode<E> right) {
this.data = e;
this.left = left;
this.right = right;
}
}
private ADTTreeNode<E> root = null;
private void display(ADTTreeNode<E> adtTreeNode){
if (adtTreeNode!=null){
display(adtTreeNode.left);
System.out.print(adtTreeNode.data+" ");
display(adtTreeNode.right);
}
}
//遍历：中序
public void display(){
display(root);
}
//插入节点e
public void insert(E e){
ADTTreeNode<E> p = new ADTTreeNode<E>(e,null,null);
if (root == null){
root = p;
}else {
ADTTreeNode<E> a = root;
ADTTreeNode<E> b = null;
int result = 0;
while (a!=null) {
b = a;
result = e.compareTo(a.data);
if (result < 0) {
a = a.left;
} else if (result > 0) {
a = a.right;
} else {
break;
}
}
if (result < 0){
b.left = p;
}else if (result > 0){
b.right = p;
}else {
}
}
}
public Boolean contains(E e){
ADTTreeNode<E> a = root;
if (a == null){
return false;
}
while (a!=null){
int result = e.compareTo(a.data);
if (result < 0){
a = a.left;
}else if (result > 0){
a = a.right;
}else{
return true;
}
}
return false;
}
public E finMin(){
ADTTreeNode<E> a = root;
while (a.left!=null){
a = a.left;
}
return a.data;
}
public E finMax(){
ADTTreeNode<E> a = root;
while (a.right!=null){
a = a.right;
}
return a.data;
}
public void remove(E e){
ADTTreeNode<E> a = root;
ADTTreeNode<E> b = null;
int result = 1;
int x = 1;
while (e.compareTo(a.data) != 0){
b = a;
result = e.compareTo(a.data);
if (result < 0){
a = a.left;
x = -1;
}else if (result > 0){
a = a.right;
x = 1;
}
}
if (a.left != null && a.right!= null){
ADTTreeNode<E> p = a.right;
while (p.left!=null){
p = p.left;
}
a.data = p.data;
a.right = p.right;
}else {
if (x < 0) {
b.left = (a.left != null) ? a.left : a.right;
}else {
b.right = (a.left != null) ? a.left : a.right;
}
}
}
public static void main(String[] args) {
ADTBinaryTree<Integer> adtBinaryTree = new ADTBinaryTree<Integer>();
adtBinaryTree.insert(3);
adtBinaryTree.insert(4);
adtBinaryTree.insert(4);
adtBinaryTree.insert(2);
adtBinaryTree.insert(7);
adtBinaryTree.insert(8);
adtBinaryTree.insert(1);
adtBinaryTree.insert(5);
adtBinaryTree.insert(7);
adtBinaryTree.display();
System.out.println();
System.out.println(adtBinaryTree.contains(3));
System.out.println(adtBinaryTree.finMin());
System.out.println(adtBinaryTree.finMax());
adtBinaryTree.remove(1);
adtBinaryTree.remove(2);
adtBinaryTree.display();
}
}