不知不觉都快5天没更新内容了，倒不是自己坚持不下来。一方面是因为二叉树这一块难度也比开始增大了，所以学习进度也就相对来说慢了一点。但更重要的是在学算法的同时也还有其他东西需要学习，在算法上面不能花太多时间。
今天写的是和二叉查找树相关的java代码，包括了二叉查找树的创建，中序遍历，查询（分为递归和非递归两种），查找最小节点，查找最大节点，插入节点，删除节点，查找节点的前驱，查找节点的后继，查找节点的父亲节点。差不多有10种操作吧。
在贴代码之前，先介绍一下什么是二叉查找树（来自百度百科）：
二叉排序树（Binary Sort Tree）又称二叉查找树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；
至于具体的操作我就不说了，在我代码里面都有详细的注释说明，运行结果我也会贴出来。
ps:代码比较多，如果发现问题还望留言指正。
/*
* 二叉查找树的java实现，包涵构造二叉查找树和对二叉查找树的一系列操作
* @version 1.0 2012/4/9
* @author akon
*/
package com.akon405.www;
public class BSTree {
BSTreeNode rootNode;//创建根节点
//创建二叉查找树
public void createBSTree(int[] A){
rootNode=new BSTreeNode(A[0],null,null);//初始化根节点
for(int i=1;i<A.length;i++){//逐个取出数组A中的元素用来构造二叉查找树
BSTreeNode tmpNode=rootNode;
while(true){
if(tmpNode.data>=A[i]){//小于等于根节点
if(tmpNode.left==null){//如果左孩子为空，这把当前数组元素插入到左孩子节点的位置
tmpNode.left=new BSTreeNode(A[i],null,null);
break;
}
tmpNode=tmpNode.left;//如果不为空的话，则把左孩子节点用来和当前数组元素作比较
}else{//大于根节点
if(tmpNode.right==null){//如果右孩子为空，这把当前数组元素插入到左孩子节点的位置
tmpNode.right=new BSTreeNode(A[i],null,null);
break;
}
tmpNode=tmpNode.right;//如果不为空的话，则把右孩子节点用来和当前数组元素作比较
}
}
}
}
//中序遍历二叉查找树（中序遍历之后便可以排序成功）
public void inOrderBSTree(BSTreeNode x){
if(x!=null){
inOrderBSTree(x.left);//先遍历左子树
System.out.print(x.data+",");//打印中间节点
inOrderBSTree(x.right);//最后遍历右子树
}
}
//查询二叉排序树--递归算法
public BSTreeNode searchBSTree1(BSTreeNode x,BSTreeNode k){
if(x==null||k.data==x.data){
return x;//返回查询到的节点
}
if(k.data<x.data){//如果k小于当前节点的数据域
return searchBSTree1(x.left,k);//从左孩子节点继续遍历
}else{//如果k大于当前节点的数据域
return searchBSTree1(x.right,k);//从右孩子节点继续遍历
}
}
//查询二叉排序树--非递归算法
public BSTreeNode searchBSTree2(BSTreeNode x,BSTreeNode k){
while(x!=null&&k.data!=x.data){
if(x.data>k.data){
x=x.left;//从左孩子节点继续遍历
}else{
x=x.right;//从右孩子节点继续遍历
}
}
return x;
}
//查找二叉查找树的最小节点
public BSTreeNode searchMinNode(BSTreeNode x){
while(x.left!=null){
x=x.left;
}
return x;
}
//查找二叉查找树的最大节点
public BSTreeNode searchMaxNode(BSTreeNode x){
while(x.right!=null){
x=x.right;
}
return x;
}
//插入节点进入二叉查找树
public void insert(BSTreeNode k){
BSTreeNode r=rootNode;
BSTreeNode p,q=null;
p=r;
while(p!=null){//while语句可以找到k节点所要插入的位置的父亲节点q
q=p;
if(p.data>k.data){
p=p.left;
}else{
p=p.right;
}
}
if(q==null){//二叉查找树为空树的情况下，直接插入到根节点，这里的q为已知的k的父亲节点
r.data=k.data;
}else if(q.data>k.data){//插入到父亲节点q的左边
q.left=k;
}else{//插入到父亲节点q的右边
q.right=k;
}
}
//删除二叉查找树中指定的节点
public void delete(BSTreeNode k){//分三种情况删除
if(k.left==null&&k.right==null){//第一种情况--没有子节点的情况下
BSTreeNode p=parent(k);
if(p.left==k){//其为父亲节点的左孩子
p.left=null;
}else if(p.right==k){//其为父亲节点的右孩子
p.right=null;
}
}else if(k.left!=null&&k.right!=null){//第二种情况--有两个孩子节点的情况下
BSTreeNode s=successor(k);//k的后继节点
delete(s);
k.data=s.data;
}else{//第三种情况--只有一个孩子节点的情况下
BSTreeNode p=parent(k);
if(p.left==k){
if(k.left!=null){
p.left=k.left;
}else{
p.left=k.right;
}
}else if(p.right==k){
if(k.left!=null){
p.right=k.left;
}else{
p.right=k.right;
}
}
}
}
//查找节点的前驱节点
public BSTreeNode predecessor(BSTreeNode k){
if(k.left!=null){
return searchMaxNode(k.left);//左子树的最大值
}
BSTreeNode y=parent(k);
while(y!=null&&k==y.left){//向上找到最近的一个节点，其父亲节点的右子树包涵了当前节点或者其父亲节点为空
k=y;
y=parent(y);
}
return y;
}
//查找节点的后继节点
public BSTreeNode successor(BSTreeNode k){
if(k.right!=null){
return searchMinNode(k.right);//右子树的最小值
}
BSTreeNode y=parent(k);
while(y!=null&&k==y.right){//向上找到最近的一个节点，其父亲节点的左子树包涵了当前节点或者其父亲节点为空
k=y;
y=parent(y);
}
return y;
}
//求出父亲节点，在定义节点类BSTreeNode的时候，没有申明父亲节点，所以这里专门用parent用来输出父亲节点（主要是不想修改代码了，就在这里加一个parent函数吧）
public BSTreeNode parent(BSTreeNode k){
BSTreeNode p=rootNode;
BSTreeNode tmp=null;
while(p!=null&&p.data!=k.data){//最后的p为p。data等于k.data的节点，tmp为p的父亲节点
if(p.data>k.data){
tmp=p;//临时存放父亲节点
p=p.left;
}else{
tmp=p;//临时存放父亲节点
p=p.right;
}
}
return tmp;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A={23,12,43,2,87,54};
BSTreeNode searchNode1=null;//递归查找到的结果
BSTreeNode searchNode2=null;//非递归查找到的结果
BSTreeNode searchMinNode=null;//最小节点
BSTreeNode searchMaxNode=null;//最大节点
BSTreeNode k=null,l=null,p=null,q=null,m=null,n=null;//申明6个节点k,l,p,q,m,n
System.out.print("打印出数组A中的元素");
for(int i=0;i<A.length;i++)
System.out.print(A[i]+",");
BSTree bs=new BSTree();
bs.createBSTree(A);//创建二叉查找树
System.out.println();
System.out.print("中序遍历构造的二叉查找树：");
bs.inOrderBSTree(bs.rootNode);//中序遍历二叉查找树
k=new BSTreeNode(23,null,null);//初始化一节点k，其data为null，左右孩子为null
l=new BSTreeNode(17,null,null);//初始化一节点l，其data为null，左右孩子为null
q=new BSTreeNode(12,null,null);//初始化一节点q，其data为null，左右孩子为null
m=bs.searchBSTree2(bs.rootNode, k);//从二叉查找树里面查找一个节点，其m.data为k.data(这个m节点在后面用来测试程序)
searchNode1=bs.searchBSTree1(bs.rootNode,k);//查询二叉查找树----递归算法
searchNode2=bs.searchBSTree2(bs.rootNode,k);//查询二叉查找树----递归算法
System.out.println("");
System.out.println("递归算法--查找节点域："+searchNode1.data+"左孩子："+searchNode1.left.data+"右孩子："+"查找节点域："+searchNode1.right.data);//这里的左孩子或者右孩子节点可能打印为空，会出现null异常
System.out.println("非递归算法--查找节点域："+searchNode2.data+"左孩子："+searchNode2.left.data+"右孩子："+"查找节点域："+searchNode2.right.data);//这里的左孩子或者右孩子节点可能打印为空，会出现null异常
searchMinNode=bs.searchMinNode(bs.rootNode);//找到最小节点
searchMaxNode=bs.searchMaxNode(bs.rootNode);//找到最大节点
System.out.println("最小节点："+searchMinNode.data);
System.out.println("最大节点："+searchMaxNode.data);
bs.insert(l);//把l节点插入到二叉查找树中
System.out.print("插入l节点(l的data为17)之后的二叉查找树的中序遍历结果:");
bs.inOrderBSTree(bs.rootNode);//中序遍历二叉查找树
p=bs.parent(q);//取q节点的父亲节点
System.out.println("");
System.out.println("q的父亲节点(q的data为12)："+p.data+"左孩子："+p.left.data+"右孩子："+"查找节点域："+p.right.data);//这里的左孩子或者右孩子节点可能打印为空，会出现null异常
bs.delete(l);
System.out.print("删除l节点(l的data为17)之后的二叉查找树的中序遍历结果:");
bs.inOrderBSTree(bs.rootNode);//中序遍历二叉查找树
n=bs.successor(m);
System.out.println("");
System.out.println("K的后继节点(k的data为23)："+n.data);
n=bs.predecessor(m);
System.out.println("K的前驱节点(k的data为23)："+n.data);
}
}
//二叉查找树的节点类
class BSTreeNode{
int data;//数据域
BSTreeNode right;//左孩子
BSTreeNode left;//右孩子
//构造二叉查找树的节点
public BSTreeNode(int data,BSTreeNode right,BSTreeNode left){
this.data=data;
this.right=right;
this.left=left;
}
}
运行结果如下：
打印出数组A中的元素23,12,43,2,87,54,
中序遍历构造的二叉查找树：2,12,23,43,54,87,
递归算法--查找节点域：23左孩子：12右孩子：查找节点域：43
非递归算法--查找节点域：23左孩子：12右孩子：查找节点域：43
最小节点：2
最大节点：87
插入l节点(l的data为17)之后的二叉查找树的中序遍历结果:2,12,17,23,43,54,87,
q的父亲节点(q的data为12)：23左孩子：12右孩子：查找节点域：43
删除l节点(l的data为17)之后的二叉查找树的中序遍历结果:2,12,23,43,54,87,
K的后继节点(k的data为23)：43
K的前驱节点(k的data为23)：12
分享到：
相关推荐
代码里有二叉排序树插入操作递归算法，二叉排序树插入操作非递归算法，二叉排序树删除操作，创建二叉排序树，二叉排序树查找递归算法，二叉排序树查找非递归算法
实验过程中，应该注意代码的清晰性和效率，同时理解各种操作对树形状的影响，以及如何维护二叉排序树的平衡，以优化查找性能。 总结来说，"数据结构实验之二叉排序树"是一个实践性的学习项目，旨在通过动手实现二叉...
二叉排序树，又称二叉查找树或二叉搜索树，是计算机科学中一种重要的数据结构，主要用于数据的存储和检索。它具有以下特性：对于任意一个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值...
数据结构是计算机科学中的核心课程，它探讨了如何有效地存储和检索数据，以优化...这个实验报告提供了一个实用的框架，可以帮助其他学生理解和实现二叉排序树的各种操作，进一步巩固他们在数据结构课程中的学习成果。
这种结构使得二叉排序树在插入、删除和查找操作上的性能表现优秀，尤其在树保持平衡的情况下。 1. **二叉排序树的插入操作**： 插入新节点时，首先与根节点比较。如果新节点的值小于根节点，则插入到左子树；反之...
这种结构使得二叉排序树在查找、插入和删除操作上有较高的效率。 在给定的场景中，我们需要用C++来处理一个文件，该文件包含不少于100个整型数，并计算这些数在二叉排序树中的平均查找长度。平均查找长度（Average ...
最近在研究数据结构这本书，自己动手实现的一个二叉查找排序树的类BinSortTree，实现数据的插入，查找，删除，层序遍历，中序遍历等操作，熟悉数据结构的朋友都知道，根据二叉排序树的定义，中序遍历后得到的序列...
【二叉排序树】，全称为Binary Sort Tree，是一种特殊的二叉树，其每个节点的值都大于其左子树中的所有节点值，且小于...在C语言中，通过结构体和指针可以方便地实现二叉排序树的各种操作，为数据处理提供了强大工具。
二叉排序树（Binary Search Tree，BST），也称为二叉查找树或有序二叉树，是一种自平衡的二叉树数据结构，它在处理搜索、插入和删除操作时具有较高的效率。二叉排序树的主要特点是：对于任意节点，其左子树中的所有...
除了上述操作外，二叉排序树还支持诸如查找、遍历等其他基本操作。例如： - **查找操作**：搜索特定键值对应的节点。 - **遍历操作**：按照一定的顺序访问树中的所有节点，如前序遍历、中序遍历、后序遍历。 这些...
二叉排序树的主要优点在于其搜索效率高，因为其结构保证了查找、插入和删除操作的时间复杂度在最坏情况下为O(log n)，而在平均情况下也为O(log n)。然而，如果插入的数据已经排序或近似排序，二叉排序树可能会退化成...
二叉排序树插入算法 二叉排序树插入是指在二叉排序树中插入新的数据元素的过程。...二叉排序树插入算法是二叉排序树操作的基础，它能够确保树的结构满足二叉排序树的性质，并且能够快速地查找和插入新的数据元素。
4. **查找操作**：查找操作是二叉排序树的一个重要应用。从根节点开始，如果待查找的键值小于当前节点的键值，就向左子树搜索；如果待查找的键值大于当前节点的键值，就向右子树搜索。重复这个过程，直到找到目标...
二叉排序树，又称二叉查找树或二叉搜索树，是计算机科学中一种非常重要的数据结构，主要用于高效地进行查找、插入和删除操作。它具有以下特性：对于任意一个节点，其左子树中的所有节点的值都小于该节点的值，而右子...
二叉排序树，又称二叉查找树或二叉搜索树，是一种特殊的二叉树数据结构，它具有以下特性：对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。这种性质使得...
二叉排序树，又称二叉查找树或二叉有序树，是一种特殊的二叉树数据结构，它的每个节点都满足以下两个性质：1) 左子树中的所有节点的值都小于当前节点的值；2) 右子树中的所有节点的值都大于当前节点的值。这种结构...
提供的代码示例展示了如何构建、插入和查找二叉排序树中的节点。其中： - `main`函数是程序的入口点，负责读取用户输入的整型数组，并调用`CreateBST`函数构建二叉排序树。 - `CreateBST`函数负责构建二叉排序树。 -...
用函数实现如下二叉排序树算法： （1） 插入新结点 （2） 前序、中序、后序遍历二叉树 （3） 中序遍历的非递归算法 （4） 层次遍历二叉树 （5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6） ...
二叉排序树（Binary Sort Tree，BST），也称为二叉查找树或二叉搜索树，是一种自平衡的二叉树数据结构，它在处理搜索、插入和删除操作时具有较高的效率。二叉排序树的主要特性是：对于任意节点，其左子树中的所有...