ddlgyq
- 浏览: 144333 次
- 性别:
- 来自: 北京
-
文章分类
最新评论
-
java_web_hack1：
HashMap和HashTable区别 几乎是百分之百会出现老 ...
面试 java -
hj01kkk：
剖析地很深入,谢谢!!
Java：单例模式的七种写法 -
hj01kkk：
很不错
Java：单例模式的七种写法 -
sunway00：
Map<Integer, String> ha ...
为KeySet遍历HashMap辟谣---效率问题 -
Shen.Yiyang：
ddlgyq 写道lyplyz 写道如果你在循环中只用key, ...
为KeySet遍历HashMap辟谣---效率问题
二叉查找树
二叉查找树（Binary Search Tree），或者是一颗空树，或者是具有下列性质的二叉树：
1、若它的左子树不空，则其左子树上的所有结点的值均小于它根结点的值；
2、若它的右子树不空，则其右子树上的所有结点的值均大于它根结点的值；
3、它的左、右子树也分别为二叉查找树。
二叉查找树是基于二叉树的，其结点数据结构定义为如下：
[java] view plaincopyprint?/**结点数据结构*/
static class BinaryNode<T>
{
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data,null,null);
}
public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data =data;
this.left = left;
this.right =right;
}
public BinaryNode()
{
data =null;
this.left = left;
this.right =right;
}
}
/**结点数据结构*/
static class BinaryNode<T>
{
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data,null,null);
}
public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data =data;
this.left = left;
this.right =right;
}
public BinaryNode()
{
data =null;
this.left = left;
this.right =right;
}
}
现在明白了什么是二叉查找树，那么二叉查找书的基本操作又是如何来实现的呢？
查找操作
在二叉查找树中查找x的过程如下：
1、若二叉树是空树，则查找失败。
2、若x等于根结点的数据，则查找成功，否则。
3、若x小于根结点的数据，则递归查找其左子树，否则。
4、递归查找其右子树。
根据上述的步骤，写出其查找操作的代码：
[java] view plaincopyprint?/**查找指定的元素,默认从
* 根结点出开始查询*/
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**从某个结点出开始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;//结点为空，查找失败
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);//递归查询右子树
else if(result<0)
return contains(t, node.left);//递归查询左子树
else
return true;
}
/**
这里我提供一个对二叉树最大值
最小值的搜索*/
/**找到二叉查找树中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找树中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMax(rootTree).data;
}
/**查询出最小元素所在的结点*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
}
/**查询出最大元素所在的结点*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
/**查找指定的元素,默认从
* 根结点出开始查询*/
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**从某个结点出开始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;//结点为空，查找失败
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);//递归查询右子树
else if(result<0)
return contains(t, node.left);//递归查询左子树
else
return true;
}
/**
这里我提供一个对二叉树最大值
最小值的搜索*/
/**找到二叉查找树中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找树中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMax(rootTree).data;
}
/**查询出最小元素所在的结点*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
}
/**查询出最大元素所在的结点*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
插入操作
二叉树查找树b插入操作x的过程如下：
1、若b是空树，则直接将插入的结点作为根结点插入。
2、x等于b的根结点的数据的值，则直接返回，否则。
3、若x小于b的根结点的数据的值，则将x要插入的结点的位置改变为b的左子树，否则。
4、将x要出入的结点的位置改变为b的右子树。
代码实现如下：
[java] view plaincopyprint?/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**在某个位置开始判断插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**在某个位置开始判断插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
删除操作
对于二叉查找树的删除操作（这里根据值删除，而非结点）分三种情况：
不过在此之前，我们应该确保根据给定的值找到了要删除的结点，如若没找到该结点
不会执行删除操作！
下面三种情况假设已经找到了要删除的结点。
1、如果结点为叶子结点（没有左、右子树），此时删除该结点不会玻化树的结构
直接删除即可，并修改其父结点指向它的引用为null.如下图:
2、如果其结点只包含左子树，或者右子树的话，此时直接删除该结点，并将其左子树
或者右子树设置为其父结点的左子树或者右子树即可，此操作不会破坏树结构。
3、 当结点的左右子树都不空的时候，一般的删除策略是用其右子树的最小数据
（容易找到）代替要删除的结点数据并递归删除该结点（此时为null），因为
右子树的最小结点不可能有左孩子，所以第二次删除较为容易。
z的左子树和右子树均不空。找到z的后继y，因为y一定没有左子树，所以可以删除y，
并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替z的值.如图：
删除操作源码：
[java] view plaincopyprint?/**删除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
} /**在某个位置开始判断删除某个结点*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
/**删除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
} /**在某个位置开始判断删除某个结点*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
完整源码
[java] view plaincopyprint?<P></P><PRE class=java name="code">package com.kiritor;
/**
* Java实现二叉查找树
* @author Kiritor
* @param <T>*/
public class BinarySearchTree<T extends Comparable<? super T>> {
/**结点数据结构*/
static class BinaryNode<T>
{
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data,null,null);
}
public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data =data;
this.left = left;
this.right =right;
}
public BinaryNode()
{
data =null;
this.left = left;
this.right =right;
}
}
private BinaryNode<T> rootTree;
/**构造一颗空的二叉查找树*/
public BinarySearchTree()
{
rootTree = null;
}
/**清空二叉查找树*/
public void clear()
{
rootTree = null;
}
/**判断是否为空*/
public boolean isEmpty()
{
return rootTree == null;
}
/**查找指定的元素,默认从
* 根结点出开始查询*/
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**找到二叉查找树中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找树中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMax(rootTree).data;
}
/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**删除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
}
/**打印二叉查找树*/
public void printTree()
{
}
/**从某个结点出开始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);
else if(result<0)
return contains(t, node.left);
else
return true;
}
/**查询出最小元素所在的结点*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
}
/**查询出最大元素所在的结点*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
/**在某个位置开始判断插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
/**在某个位置开始判断删除某个结点*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
public BinaryNode<Integer> init()
{
BinaryNode<Integer> node3 = new BinaryNode<Integer>(3);
BinaryNode<Integer> node1 = new BinaryNode<Integer>(1);
BinaryNode<Integer> node4 = new BinaryNode<Integer>(4,node3,null);
BinaryNode<Integer> node2 = new BinaryNode<Integer>(2,node1,node4);
BinaryNode<Integer> node8 = new BinaryNode<Integer>(8);
BinaryNode<Integer> root = new BinaryNode<Integer>(6,node2,node8);
return root;
}
public void preOrder(BinaryNode node) {
if (node != null) {
System.out.print(node.data);
preOrder(node.left);
preOrder(node.right);
}
}
/*简单测试*/
public static void main(String[] args) {
BinarySearchTree searchTree = new BinarySearchTree<>();
BinaryNode<Integer> node= searchTree.init();
searchTree.rootTree=node;
searchTree.preOrder(searchTree.rootTree);
searchTree.remove(4);
searchTree.preOrder(searchTree.rootTree);
}
} </PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
二叉查找树（Binary Search Tree），或者是一颗空树，或者是具有下列性质的二叉树：
1、若它的左子树不空，则其左子树上的所有结点的值均小于它根结点的值；
2、若它的右子树不空，则其右子树上的所有结点的值均大于它根结点的值；
3、它的左、右子树也分别为二叉查找树。
二叉查找树是基于二叉树的，其结点数据结构定义为如下：
[java] view plaincopyprint?/**结点数据结构*/
static class BinaryNode<T>
{
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data,null,null);
}
public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data =data;
this.left = left;
this.right =right;
}
public BinaryNode()
{
data =null;
this.left = left;
this.right =right;
}
}
/**结点数据结构*/
static class BinaryNode<T>
{
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data,null,null);
}
public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data =data;
this.left = left;
this.right =right;
}
public BinaryNode()
{
data =null;
this.left = left;
this.right =right;
}
}
现在明白了什么是二叉查找树，那么二叉查找书的基本操作又是如何来实现的呢？
查找操作
在二叉查找树中查找x的过程如下：
1、若二叉树是空树，则查找失败。
2、若x等于根结点的数据，则查找成功，否则。
3、若x小于根结点的数据，则递归查找其左子树，否则。
4、递归查找其右子树。
根据上述的步骤，写出其查找操作的代码：
[java] view plaincopyprint?/**查找指定的元素,默认从
* 根结点出开始查询*/
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**从某个结点出开始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;//结点为空，查找失败
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);//递归查询右子树
else if(result<0)
return contains(t, node.left);//递归查询左子树
else
return true;
}
/**
这里我提供一个对二叉树最大值
最小值的搜索*/
/**找到二叉查找树中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找树中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMax(rootTree).data;
}
/**查询出最小元素所在的结点*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
}
/**查询出最大元素所在的结点*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
/**查找指定的元素,默认从
* 根结点出开始查询*/
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**从某个结点出开始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;//结点为空，查找失败
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);//递归查询右子树
else if(result<0)
return contains(t, node.left);//递归查询左子树
else
return true;
}
/**
这里我提供一个对二叉树最大值
最小值的搜索*/
/**找到二叉查找树中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找树中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMax(rootTree).data;
}
/**查询出最小元素所在的结点*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
}
/**查询出最大元素所在的结点*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
插入操作
二叉树查找树b插入操作x的过程如下：
1、若b是空树，则直接将插入的结点作为根结点插入。
2、x等于b的根结点的数据的值，则直接返回，否则。
3、若x小于b的根结点的数据的值，则将x要插入的结点的位置改变为b的左子树，否则。
4、将x要出入的结点的位置改变为b的右子树。
代码实现如下：
[java] view plaincopyprint?/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**在某个位置开始判断插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**在某个位置开始判断插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
删除操作
对于二叉查找树的删除操作（这里根据值删除，而非结点）分三种情况：
不过在此之前，我们应该确保根据给定的值找到了要删除的结点，如若没找到该结点
不会执行删除操作！
下面三种情况假设已经找到了要删除的结点。
1、如果结点为叶子结点（没有左、右子树），此时删除该结点不会玻化树的结构
直接删除即可，并修改其父结点指向它的引用为null.如下图:
2、如果其结点只包含左子树，或者右子树的话，此时直接删除该结点，并将其左子树
或者右子树设置为其父结点的左子树或者右子树即可，此操作不会破坏树结构。
3、 当结点的左右子树都不空的时候，一般的删除策略是用其右子树的最小数据
（容易找到）代替要删除的结点数据并递归删除该结点（此时为null），因为
右子树的最小结点不可能有左孩子，所以第二次删除较为容易。
z的左子树和右子树均不空。找到z的后继y，因为y一定没有左子树，所以可以删除y，
并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替z的值.如图：
删除操作源码：
[java] view plaincopyprint?/**删除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
} /**在某个位置开始判断删除某个结点*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
/**删除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
} /**在某个位置开始判断删除某个结点*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
完整源码
[java] view plaincopyprint?<P></P><PRE class=java name="code">package com.kiritor;
/**
* Java实现二叉查找树
* @author Kiritor
* @param <T>*/
public class BinarySearchTree<T extends Comparable<? super T>> {
/**结点数据结构*/
static class BinaryNode<T>
{
T data;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode(T data) {
this(data,null,null);
}
public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {
this.data =data;
this.left = left;
this.right =right;
}
public BinaryNode()
{
data =null;
this.left = left;
this.right =right;
}
}
private BinaryNode<T> rootTree;
/**构造一颗空的二叉查找树*/
public BinarySearchTree()
{
rootTree = null;
}
/**清空二叉查找树*/
public void clear()
{
rootTree = null;
}
/**判断是否为空*/
public boolean isEmpty()
{
return rootTree == null;
}
/**查找指定的元素,默认从
* 根结点出开始查询*/
public boolean contains(T t)
{
return contains(t, rootTree);
}
/**找到二叉查找树中的最小值*/
public T findMin()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMin(rootTree).data;
}
/**找到二叉查找树中的最大值*/
public T findMax()
{
if(isEmpty())
{
System.out.println("二叉树为空");
return null;
}else
return findMax(rootTree).data;
}
/**插入元素*/
public void insert(T t)
{
rootTree = insert(t, rootTree);
}
/**删除元素*/
public void remove(T t)
{
rootTree = remove(t,rootTree);
}
/**打印二叉查找树*/
public void printTree()
{
}
/**从某个结点出开始查找元素*/
public boolean contains(T t, BinaryNode<T> node)
{
if(node==null)
return false;
int result = t.compareTo(node.data);
if(result>0)
return contains(t,node.right);
else if(result<0)
return contains(t, node.left);
else
return true;
}
/**查询出最小元素所在的结点*/
public BinaryNode<T> findMin(BinaryNode<T> node)
{
if(node==null)
return null;
else if(node.left==null)
return node;
return findMin(node.left);//递归查找
}
/**查询出最大元素所在的结点*/
public BinaryNode<T> findMax(BinaryNode<T> node)
{
if(node!=null)
{
while(node.right!=null)
node=node.right;
}
return node;
}
/**在某个位置开始判断插入元素*/
public BinaryNode<T> insert(T t,BinaryNode<T> node)
{
if(node==null)
{
//新构造一个二叉查找树
return new BinaryNode<T>(t, null, null);
}
int result = t.compareTo(node.data);
if(result<0)
node.left= insert(t,node.left);
else if(result>0)
node.right= insert(t,node.right);
else
;//doNothing
return node;
}
/**在某个位置开始判断删除某个结点*/
public BinaryNode<T> remove(T t,BinaryNode<T> node)
{
if(node == null)
return node;//没有找到,doNothing
int result = t.compareTo(node.data);
if(result>0)
node.right = remove(t,node.right);
else if(result<0)
node.left = remove(t,node.left);
else if(node.left!=null&&node.right!=null)
{
node.data = findMin(node.right).data;
node.right = remove(node.data,node.right);
}
else
node = (node.left!=null)?node.left:node.right;
return node;
}
public BinaryNode<Integer> init()
{
BinaryNode<Integer> node3 = new BinaryNode<Integer>(3);
BinaryNode<Integer> node1 = new BinaryNode<Integer>(1);
BinaryNode<Integer> node4 = new BinaryNode<Integer>(4,node3,null);
BinaryNode<Integer> node2 = new BinaryNode<Integer>(2,node1,node4);
BinaryNode<Integer> node8 = new BinaryNode<Integer>(8);
BinaryNode<Integer> root = new BinaryNode<Integer>(6,node2,node8);
return root;
}
public void preOrder(BinaryNode node) {
if (node != null) {
System.out.print(node.data);
preOrder(node.left);
preOrder(node.right);
}
}
/*简单测试*/
public static void main(String[] args) {
BinarySearchTree searchTree = new BinarySearchTree<>();
BinaryNode<Integer> node= searchTree.init();
searchTree.rootTree=node;
searchTree.preOrder(searchTree.rootTree);
searchTree.remove(4);
searchTree.preOrder(searchTree.rootTree);
}
} </PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
<PRE></PRE>
分享到：
发表评论
-
CopyOnWriteArrayList
2014-10-17 13:58 545CopyOnWriteArrayList是ArrayLi ... -
Java多线程-工具篇-BlockingQueue
2013-09-03 23:22 1882一：前言： 在新增的Concurrent包中，Blo ... -
Java：单例模式的七种写法
2013-07-04 16:22 1685第一种（懒汉，线程不安全）： 1 public cla ... -
Spring 资源访问剖析和策略模式应用
2013-06-21 18:07 904Spring 把所有能记录信息 ... -
Mysql Explain 详解
2013-06-08 13:28 811一.语法 explain < table_name & ... -
spring mvc 框架搭建及详解
2013-05-08 09:04 908现在主流的Web MVC框架除了Struts这个主力 外，其次 ... -
Spring 使用注解方式进行事务管理
2013-05-08 09:05 1135大家在使用spring的注解 ... -
Spring MVC framework深入分析
2013-05-08 09:06 868在当今的MVC framework里， ... -
JMS 异步传输与Spring结合实例
2013-05-08 09:06 1258在Spring 2.0之前，Spring的JMS的作用局限于产 ... -
spring scope自定义
2013-05-07 22:39 1168BeanFactory除了拥有作为IoC Service Pr ... -
Spring的autowire自动装配bean的四种方式
2013-05-07 22:37 932default [html] view plaincopyp ... -
Spring总结
2013-05-07 22:34 761一、Spring中JDK的动态代 ... -
mysql字符串长度的一些问题
2013-05-07 22:14 1235length: 是计算字段的长度一个汉字是算三个字符,一个 ... -
HIGH_PRIORITY/LOW_PRIORITY/INSERT DELAYED
2013-05-03 18:18 1117MySQL 还允许改变语句调 ... -
BIT_COUNT()&BIT_OR()
2013-05-02 21:04 739在学习MySQL手册时，看 ... -
mysql时间函数
2013-04-30 20:38 843一、MySQL 获得当前日期时间 函数 1.1 获得当前日期+ ... -
SQL中EXISTS的用法
2013-04-28 11:51 717SELECT c.CustomerId,CompanyName ... -
sql之left join、right join、inner join的区别
2013-04-28 10:09 798sql之left join、right join、inner ... -
关于with cube ，with rollup 和 grouping
2013-04-28 09:37 820http://www.cnblogs.com/shuangne ... -
Spring的注解
2013-03-29 11:25 807注释配置相对于 XML 配置具有很多的优势： 它可以充分利用 ...
相关推荐
二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，它的每个节点都包含一个键（key）、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉查找树中，对于任意节点，其左子树中的...
二叉查找树（Binary Search Tree, BST）是一种基础但非常重要的数据结构，它在计算机科学中扮演着核心角色，尤其是在算法和数据结构的学习中。二叉查找树的主要特性是每个节点的左子树只包含小于该节点的元素，右子...
二叉查找树（Binary Search Tree, BST）是一种特殊的数据结构，它在计算机科学中用于高效地存储和检索数据。在二叉查找树中，每个节点包含一个键（key）、一个关联的值、一个指向左子节点的引用以及一个指向右子节点...
在C++编程中，二叉查找树（Binary Search Tree，简称BST）是一种常见的数据结构，它具有以下特性：对于任意节点，其左子树中的所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值。这种性质使得...
二叉查找树（Binary Search Tree，BST）是一种特殊类型的二叉树，它的每个节点都包含一个键（key）、一个关联的值、一个指向左子树的指针和一个指向右子树的指针。在二叉查找树中，每个节点的键都大于其左子树中的...
二叉查找树（Binary Search Tree，BST）是一种特殊类型的二叉树，它的每个节点都包含一个键（key）、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。在二叉查找树中，对于任意节点，其左子树中的所有...
用C++实现的最优二叉查找树，简单，明了，是数据结构里经典必学算法，初学者适用
最优二叉查找树（Optimal Binary Search Tree, OBST）是一种高效的检索数据结构，它根据键值分布的不同，自适应地调整树的形态以达到最小化查找时间的目的。在计算机科学中，动态规划（Dynamic Programming, DP）是...
### 一种高效二叉查找树——红黑树 #### 一、引言 在计算机科学领域，二叉查找树(Binary Search Tree, BST)是一种非常重要的数据结构，它能够有效地实现查找、插入和删除等基本操作。然而，在某些情况下，普通的...
标题：最优二叉查找树 描述：算法对最优二叉树的实现（课本上对最优二叉树的基本实现） 在计算机科学中，最优二叉查找树（Optimal Binary Search Tree，简称OBST）是一种特殊的二叉查找树，其设计目标是在平均情况...
二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，它具有以下特性：对于树中的每个节点，其左子树上的所有节点的值都小于该节点的值，而右子树上的所有节点的值都大于该节点的值。这样的特性使得...
1、 定义二叉查找树的类。 2、 实验验证如下算法的正确性、各种功能及指标： 1）实现二叉查找树结构； 2） 实现二叉查找树的查找、插入和删除等算法；
### C++ 实现二叉查找树 #### 一、引言 本文将详细介绍如何使用C++来实现一个二叉查找树(Binary Search Tree, BST)，包括其基本操作：插入、删除、遍历等，并通过示例代码进行解释。二叉查找树是一种非常重要的数据...
### 一、二叉查找树简介 二叉查找树是一种特殊的二叉树数据结构，它具有以下特性： 1. **左子树**中的所有节点值均小于其根节点的值。 2. **右子树**中的所有节点值均大于其根节点的值。 3. 左右子树也分别满足上述...
二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树结构，它的每个节点都包含一个键值（key）、一个指向左子树的指针和一个指向右子树的指针。在二叉查找树中，对于任意节点，其左子树中的所有节点的键值都...
二叉查找树（Binary Search Tree，BST），也称为二叉排序树，是一种特殊的二叉树数据结构。它的每个节点都包含一个键（key）、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉查找树中，对于...
二叉查找树（Binary Search Tree，BST），也称为二叉排序树，是一种特殊的二叉树数据结构，它的每个节点都包含一个键值、一个指向左子树的指针和一个指向右子树的指针。在二叉查找树中，对于任意节点，其左子树中的...
二叉查找树的常用操作，含C++代码，找工作的时候可以放在手机里看。