文档章节

二叉查找树

notAcoder
 notAcoder
发布于 2013/10/04 17:01
字数 753
阅读 47
收藏 1

二叉查找树的特点:

1.若左子树非空,则左子树上所有结点的数据元素值均小于根结点的数据元素值。

2.若右子树非空,则右子树上所有的节点的数据元素值均大于或等于根结点的数据元素的值。

3.左右子树也均为二叉查找树

java 实现的二叉查找树:

BiTreeNode.java


public class BiTreeNode<T extends Comparable<? super T>> {
	private BiTreeNode<T> leftChild;
	private BiTreeNode<T> rightChild;
	private BiTreeNode<T> parent;
	private T data;
	
	public BiTreeNode() {
		leftChild = null;
		rightChild = null;
	}
	
	public BiTreeNode(T data){
		this.data = data;
		leftChild = null;
		rightChild = null;
	}
	
	BiTreeNode(T data,BiTreeNode<T> leftChild,BiTreeNode<T> rightChild){
		this.data = data;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}

	public BiTreeNode<T> getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(BiTreeNode<T> leftChild) {
		this.leftChild = leftChild;
	}

	public BiTreeNode<T> getRightChild() {
		return rightChild;
	}

	public void setRightChild(BiTreeNode<T> rightChild) {
		this.rightChild = rightChild;
	}

	public BiTreeNode<T> getParent() {
		return parent;
	}

	public void setParent(BiTreeNode<T> parent) {
		this.parent = parent;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}
}
BiSearchTree.java



public class BiSearchTree<T extends Comparable<? super T>> {

	private BiTreeNode<T> root;
	
	//中序遍历
	private void inOrder(BiTreeNode<T> t,Visit vs){
		if( t != null ){
			inOrder(t.getLeftChild(),vs);
			vs.print(t.getData());
			inOrder(t.getRightChild(),vs);
		}
	}
	
	//前序遍历
	private void preOrder(BiTreeNode<T> t, Visit vs){
		if(t!=null){
			vs.print(t.getData());
			preOrder(t.getLeftChild(),vs);
			preOrder(t.getRightChild(),vs);
		}
	}
	
	public BiSearchTree() {
		root = null;
	}

	public BiTreeNode<T> getRoot() {
		return root;
	}

	public void setRoot(BiTreeNode<T> root) {
		this.root = root;
	}
	
	
	public void inOrder(Visit vs){
		inOrder(root,vs);
	}

	public void preOrder(Visit vs){
		preOrder(root,vs);
	}
	
	//取得左孩子
	public BiTreeNode<T> getLeft(BiTreeNode<T> current){
		return current != null ?current.getLeftChild():null;
	}
	
	//取得右孩子
	public BiTreeNode<T> getRight(BiTreeNode<T> current){
		return current != null ? current.getRightChild() : null;
	}
	
	//查找
	public BiTreeNode<T> find(T data){
		if(root !=null){
			BiTreeNode<T> temp = root;
			while(temp!=null){
				if(temp.getData().compareTo(data)==0) return temp;
				if((temp.getData().compareTo(data))<0){
					temp = temp.getRightChild();
				} else {
					temp = temp.getLeftChild();
				}
			}
		}
		return null;
	}
	
	public void insert(BiTreeNode<T> ptr,T data){
		
		//如果插入的值小于当前节点的值,就在左子树上面插入
		if(data.compareTo(ptr.getData())<0){
			//如果左字树为空直接把该结点作为当前节点的左孩子,否则递归到左孩子
			if(ptr.getLeftChild() == null){
				BiTreeNode<T> temp  = new BiTreeNode<T>(data);
				temp.setParent(ptr);
				ptr.setLeftChild(temp);
			}else{
				insert(ptr.getLeftChild(),data);
			}
		}else if(data.compareTo(ptr.getData())>0){
			if(ptr.getRightChild() == null){
				BiTreeNode<T> temp  = new BiTreeNode<T>(data);
				temp.setParent(ptr);
				ptr.setRightChild(temp);
			}else{
				insert(ptr.getRightChild(),data);
			}
		}
		
	}
	
	/**
	 * 分四种情况:
	 * 1.删除节点没有孩子节点
	 * 2.删除节点只有左边孩子
	 * 3.删除结点只有右孩子
	 * 4.删除结点有左右结点
	 */
	public void delete(BiTreeNode<T> ptr,T data){
		if(ptr != null){
			if(data.compareTo(ptr.getData())<0){
				delete(ptr.getLeftChild(),data);
			}else if(data.compareTo(ptr.getData())>0){
				delete(ptr.getRightChild(),data);
			}else if(ptr.getLeftChild() != null && ptr.getRightChild() !=null){//删除结点有左右结点
				BiTreeNode<T> rightMin; //右子树最小的结点
				rightMin = ptr.getRightChild();
				while(rightMin.getLeftChild()!=null){
					rightMin = rightMin.getLeftChild();
				}
				ptr.setData(rightMin.getData());
				delete(ptr.getRightChild(),rightMin.getData());
			}else{
				//左孩子为空,右孩子不为空
				if(ptr.getLeftChild() == null &&ptr.getRightChild() !=null){//删除结点只有右孩子
					ptr.getParent().setRightChild(ptr.getRightChild());
					ptr.getRightChild().setParent(ptr.getParent());
				}
				else if(ptr.getLeftChild() != null && ptr.getRightChild() == null){//删除节点只有左边孩子
					ptr.getParent().setLeftChild(ptr.getLeftChild());
					ptr.getLeftChild().setParent(ptr.getParent());
				}else{//删除节点没有孩子节点
					BiTreeNode<T> p = ptr.getParent();
					if(p.getLeftChild() == ptr){
						p.setLeftChild(null);
					}else{
						p.setRightChild(null);
					}
				}
			}
		}
	}
}

测试:

public class BiSearchTreeTest {

	public static void main(String[] args) {
		BiSearchTree<Integer> searchTree = new BiSearchTree<Integer>();
		int a[] = {4,5,7,2,1,9,8,11,3};
		Visit vs = new Visit();
		BiTreeNode<Integer> root = new BiTreeNode<Integer>(a[0]);
		
		for (int i = 1; i < a.length; i++) {
			searchTree.insert(root, a[i]);
		}
		
		searchTree.setRoot(root);
		
		System.out.println("中序遍历:");
		searchTree.inOrder(vs);
		searchTree.delete(searchTree.getRoot(), 4);
		System.out.println("删除4后的中序遍历:");
		searchTree.inOrder(vs);
		
	}

}
public class Visit {
 public void print(Object o){
 System.out.print(o+" ");
 }
}


© 著作权归作者所有

下一篇: 快速排序
notAcoder
粉丝 5
博文 30
码字总数 12671
作品 0
巴南
架构师
私信 提问
二叉排序树(Binary Sort Tree)

1、定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ① 若它的左子树非空,则左子树上所有...

野渡书生
2016/04/28
189
0
算法与数据结构(五)树表的查找

树表的查找 (1)二叉排序树 (2)二叉排序树的操作——查找 (3)二叉排序树的操作——插入 (4)二叉排序树的操作——生成 (5)二叉排序树的操作——删除 (1)二叉排序树 由于线性表的查...

OrdinaryMan
2018/12/01
0
0
算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/18
0
0
深入学习二叉树(四) 二叉排序树

1 前言 数据结构中,线性表分为无序线性表和有序线性表。 无序线性表的数据是杂乱无序的,所以在插入和删除时,没有什么必须遵守的规则,可以插入在数据尾部或者删除在数据尾部。但是在查找的...

进击的Hello_World
2018/05/14
0
0
小蚂蚁学习数据结构(32)——二叉排序树的概念

二叉排序树,定义: 1,若左子树非空,则左子树上所有节点的关键字均小于根节点关键字。 2,若右子树非空,则右子树上所有节点的关键字均大于根节点关键字。 3,左右子树本身又是一颗二叉树。...

嗜学如命的小蚂蚁
2016/02/07
122
0

没有更多内容

加载失败,请刷新页面

加载更多

shangcheng-my

1.数据库主键、外键类型为bigint,那么在后台应该用什么类型的变量定义? 后台用string接收,因为前段传过来的一般都是json字符串,后台直接接收,mysql是可以吧数字类型的字符串转换为对应的...

榴莲黑芝麻糊
昨天
4
0
微服务架构依赖图

基于spring-cloud-alibaba + dubbo

龙影
昨天
5
0
Centos7 安装zabbix-agent

rpm -i https://repo.zabbix.com/zabbix/4.2/rhel/6/x86_64/zabbix-release-4.2-2.el6.noarch.rpm 可以到https://repo.zabbix.com/zabbix找到对应的版本 yum install zabbix-agent -y 出现E......

abowu
昨天
8
0
文本编辑器GNU nano 4.4 发布

GNU nano 4.4 "Hagelslag" 更新日志: 启动时,光标可以放在第一个或最后一个出现位置 字符串前面带有+/string 或 +?string的字符串。 发生自动硬包装时((--breaklonglines),任何前导引号...

linuxCool
昨天
7
0
你知道字节序吗

字节序 最近在调一个自定义报文的接口时,本来以为挺简单的,发现踩了好几个坑,其中一个比较“刻骨铭心”的问题就是数据的字节序问题。 背景 自定义报文,调用接口,服务端报文解析失败 iO...

杭城小刘
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部