您的位置: 首页  >  文章  >  java实现数据结构：二叉排序树的插入，查找，删除节点

java实现数据结构：二叉排序树的插入，查找，删除节点

分类: 文章 • 2022-11-07 09:37:05

引入树的前提：
在有序数组中，查找一个数据非常快，但是插入和删除非常慢。
在一个链表中，插入和删除一个数据非常快，但是查找一个数据非常慢。
要是有个数据结构可以满足查找和删除，插入都很方便。
用树来解决问题：
节点用类表示。
边（两个节点的关联关系）用引用来表示。
树的分类：二叉树
多路树：（2-3-4树，外部存储）

一.二叉搜索（排序）树（左节点<根<右节点）

1.节点表示：
包含数据项，还有两个指向子节点的引用。

class Node{
**Datatype** data;//可以是基本类型或类类型。
Node leftChild;
Node rightChild;
public void displayNode(){
//do something;
}
}

java实现数据结构：二叉排序树的插入，查找，删除节点
2.树：

class Tree{
	private Node root;//根节点
	public Tree(){
	root=null;
	}
	public Node find(int key){//查找方法
	4
	}
	public void insert(int id,double dd){//插入     返回值可以是boolean
	5
	}
	public void delete(int id){//删除              返回值可以是boolean
	8
	}
}

3.操作树的类：

class TreeApp{
	public static void main(String[] args){
		Tree theTree=new Tree();
		theTree.insert(50,1.5);
		theTree.insert(52,1.4);
		theTree.insert(53,1.6);
		Node found=theTree.find(25);
		if(found!=null)
		System.out.println("found the node with key 25");
		else
		System.out.println("Could not find node with key 25");
	}
}

4.查找节点

public Node find(int key){

	Node current=root;//利用一个变量current来保存正在查看的节点。
	while(current!=key){
		if(current.data>key)
		current=current.lefChild;//key的值比current的值小就往左子树进行查找。
		else
			current=current.rightChild;//key的值比current的值大就往右子树进行查找。
		if(current==null)
		return null;//空节点
		}
	return current;
}

java实现数据结构：二叉排序树的插入，查找，删除节点
5.插入节点
两个过程变量：current和parent。
（1）新建立一个节点。
（2）空树，直接插入。
（3）找到相应位置（find(int key))，插入。

public void insert(int id,double dd){
	Node newNode=new Node();
	newNode.data=id;
	newNode.dData=dd;
	if(root==null)
	root=newNode;
	else{
		Node current=root;
		Node parent;
		while(true){
			parent=current;
			if(id<current.iData){
				current=current.leftChild;
				if(current==null){
					parent.lefChild=newNode;
					return;
				}		
			}
			else{
				current=current.rightChild;
				if(current==null){
					parent.rightChild=newNode;
					return;
				}
			}
		}
	}
}

6.遍历树
三种：前序，中序，后序。
遍历树的最简单方法就是递归方法。
访问节点意味着对这个节点做某种操作：显示节点，把几点写入文件，或其他别的操作。
先讲一下中序遍历：

private void inOrder(Node localRoot){
	if(localRoot!=null){
		inOrder(localRoot.leftChild);
		Syste.out.print(localRoot.aData_*  *);
		inOrder(localRoot.rightChild);
	}
}
开始时用根作为参数调用这个方法：
inOrder(root);
之后就自己调用自己，知道所有节点都被访问完。

先序：
后序：
以此类推。
7.查找最小值和最大值
找到最小值：从根开始查找，顺着左子树，找到最左边的节点。
找到最大值：从根开始查找，顺着右子树，找到最右边的节点。
在这里就演示找最小值的代码：
查找过程中需要两个变量：current,last。

public Node mininum(){
	Node current,last;
	current=root;
	while(current!=null){
	last=current;
	current=current.leftChild;//current=current.rightChild;
	}
	return las;
}

8.删除节点
删除节点会有三种情况：
1.叶子节点。
2.该节点有一个子节点。
3.该节点有两个子节点。

public boolean delete(int key){
	Node current=root;
	Node parent=root;
	boolean isLeftChild=true;
	while(current.iData!=key){
		parent=current;
		if(key<current.iData){
			current=current.leftChild;
			isLeftChild=true;
		}
		else{
			current=current.rightChild;
			isLefChild=false;
		}
		if(current==null)
			return false;
	}//end while
//found node to delete
	if(current.leftChild==null&&current.rightChild==null){
		if(current==root)
			root=null;
		else if(isLeftChild)
			parent.leftChild=null;
		else
			parent.rightChild=null;
	}//end to if    叶子节点的删除
	else if(current.rightChild==null){//只有左子节点
		if(current==root)
			root=current.leftChild;
		else if(isLeftChild)
			parent.leftChild=current.leftChild;
		else
			parent.rightChild=curremt.leftChild;
	}
	else  if(current.leftChild==null){//只有右子节点
		if(current==root)
			root=current.rightChild;
		else if(isLeftChild)
			parent.leftChild=current.rightChild;
		else
			parent.rightChild=current.rightChild;
	}end to else if 删除只有一个子节点的节点
	else{//有两个子节点
		Node successor=getSuccessor(current);
		if(current==root)
			root=successor;
		else if(isLeftChild)
			parent.lefChild=successor;
		else
			parent.rightChild=successor;
		successor.leftChild=parent.lefChild;
	}	
}
//找到要删节点的中序后继节点，即右节点的最左孩子。
public Node getSuccessor(Node delNode){
	Node successorParent=delNode;
	Node successor=delNode;
	Node current=delNode.rightChild;
	while(current!=null){
		successorParent=successor;
		successor=current;
		current=current.leftChild;
	}
	if(successor!=delNode.rightChild){
		successParent.leftChild=successor.rightChild;
		successor.rightChild=delNode.rightChild;
	}
	return successor;
}

相关推荐