二叉树的一个重要应用在于它们可以在查找中使用。
今天来记录一下二叉查找树的学习心得;
首先来看看,什么是二叉查找树?
简单的说,它有一个性质。 既
对于X节点来说,
它的左子树中的所有项都小于X的项,
它的右子树中的所有项都大于X的项。
如图3
下面我们用代码来实现一个简单的二叉查找树:
代码如下:
package com.base.tree;
public class BinartSearchTree {
public static void main(String[] args) {
BinaryTree root=new BinaryTree();
BinaryTree.TreeNode t=new BinaryTree.TreeNode(6);
BinaryTree.TreeNode t2=new BinaryTree.TreeNode(2);
BinaryTree.TreeNode t3=new BinaryTree.TreeNode(1);
BinaryTree.TreeNode t4=new BinaryTree.TreeNode(5);
BinaryTree.TreeNode t5=new BinaryTree.TreeNode(3);
BinaryTree.TreeNode t6=new BinaryTree.TreeNode(4);
BinaryTree.TreeNode t7=new BinaryTree.TreeNode(8);
t.setLeft(t2);
t.setRight(t7);
t2.setLeft(t3);
t2.setRight(t4);
t4.setLeft(t5);
t5.setRight(t6);
root.setRoot(t);
/*=================构造树,如图2-1=================*/
root.remove(2);
root.printTree();
}
}
/**
* 二叉查找树的性质:对于X节点,左边子树的所有项都小于X节点的项,右边子树的所有项都大于X节点的项。
* @author google
*
*/
class BinaryTree{
private TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
public BinaryTree(){
root=null;
}
public void makeEmpty(){
root=null;
}
public boolean isEmpty(){
return root==null;
}
public boolean contains(int data){
return contains(data,root);
}
public int findMin(){
if(isEmpty()) return -1;
return findMin(root).data;
}
public int findMax(){
if(isEmpty())return -1;
return findMax(root).data;
}
public void insert(int data){
root=insert(data, root);
}
public void remove(int data){
root=remove(data,root);
}
public void printTree(){
if(isEmpty())
System.out.println("Empty Tree……");
else
printTree(root);
}
/**
* 打印树
* @param t
*/
private void printTree(TreeNode t){
if(t!=null){
printTree(t.left);
System.out.println(t.data);
printTree(t.right);
}
}
/**
* 在字树中查找与元素
*
* @param x
* @param node
* @return
*/
private boolean contains(int x,TreeNode t){
if(t==null)return false;
if(x>t.data){
return contains(x,t.right);
}if(x<t.data){
return contains(x,t.left);
}else{
return true;
}
}
/**
* 删除节点,需要考虑需要删除节点的情况如下:
* 1.当需要删除的是一片树叶,即可立刻删除
* 2.有一个节点: 可以在其父节点调整链的指向,绕过该节点被删除。 图1
* 3.当有两个儿子节点时:
* 用右子树中最小数据代替该节点数据,并递归删除那个节点。 图2-2
* @param data
* @param t
* @return
*/
private TreeNode remove(int data,TreeNode t){
if(t==null)return t;
if(data>t.data){
t.right=remove(data,t.right);
}else if(data<t.data){
t.left=remove(data,t.left);
}else if(t.left!=null&&t.right!=null){
//处理需要删除的节点有2个节点的情况
//
t.data=findMin(t.right).data;
t.right=remove(t.data,t.right);
}else{
t=(t.left!=null)?t.left:t.right;
}
return t;
}
/**
* 将x插入到子树中
* @param data
* @param t
* @return
*/
private TreeNode insert(int data,TreeNode t){
if(t==null)return new TreeNode(data,null,null);
//比较大小, 将新建一个节点后,重新构造树
if(data>t.data){
t.right=insert(data,t.right);
}else if(data<t.data){
t.left=insert(data,t.left);
}
return t;
}
/**
* 查找最小元素, 从根开始,一路向左子树查找 (递归实现)
* @param t
* @return
*/
private TreeNode findMin(TreeNode t){
if(t==null)return null;
if(t.left==null)
return t;
return findMin(t.left);
}
/**
* 查找最大元素, 从根开始,一路向右子树查找 (非递归实现)
* @param t
* @return
*/
private TreeNode findMax(TreeNode t){
if(t!=null)
while(t.right!=null)
t=t.right;
return t;
}
/**
* 树节点类
* @author google
*
*/
public static class TreeNode{
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(){}
public TreeNode(int data){
this.data=data;
}
public TreeNode(int data,TreeNode left,TreeNode right){
this.data=data;
this.left=left;
this.right=right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
}
其中的remove方法可能理解相对要难一点,下面附上图片,让其原理一目了然。
- 大小: 14 KB
- 大小: 29.7 KB
分享到:
相关推荐
二叉排序树的实现 二叉排序补充概念(也可以参考书上第九章第二节) 左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. ...课程设计数据结构二叉排序树
01-001数据结构的概念和基本术语、抽象数据类型的表示与实现 01-002算法设计的要求、算法效率的度量 02-001线性表的类型定义 02-002线性表的顺序表示与实现、线性表的基本操作 02-003单链表的创建与操作、加工型...
本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有最高效率的...
本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...
练习 参考文献第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上的插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下的删除 12.3 确定性跳跃表 12.4 aa树 12.5 treap树 ...
练习 参考文献第12章 高级数据结构及其实现 12.1 自顶向下伸展树 12.2 红黑树 12.2.1 自底向上的插入 12.2.2 自顶向下红黑树 12.2.3 自顶向下的删除 12.3 确定性跳跃表 12.4 aa树 12.5 treap树 ...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
四 二叉排序树查找的分析、程序、及运行结果 - 8 - 4.1系统简介 - 8 - 4.2设计思路 - 8 - 4.3二叉排序树算法描述 - 9 - 4.4运行结果 - 11 - 五 哈希查找的分析、程序、及运行结果 - 12 - 5.1系统简介 - 12 - 5.2设计...
二叉排序树(又称二叉查找树):(1)若左子树不空,则左子树上所有节点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有节点均大于它的根结点的值;(3)它的左右子树分别为二叉排序树。 二叉平衡树:若...
中文名: 数据结构与算法分析_Java语言描述(第2版)作者: 韦斯译者: 冯舜玺资源格式: PDF版本: 扫描版出版社: 机械工业出版社书号: ISBN:9787111231837发行时间: 2009年01月01日地区: 大陆语言: 简体中文简介: 内容...
树4.1 预备知识4.1.1 树的实现4.1.2 树的遍历及应用4.2 二叉树4.2.1 实现4.2.2 例子:表达式树4.3 查找树ADT——二叉查找树4.3.1 contains方法4.3.2 findMin方法和findMax方法4.3.3 insert方法4.3.4 remove方法...
主要介绍了JS中的算法与数据结构之二叉查找树(Binary Sort Tree),结合实例形式详细分析了二叉查找树(Binary Sort Tree)的原理、定义、遍历、查找、插入、删除等常见操作技巧,需要的朋友可以参考下
内容简介《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计) 随着计算机速度...
课程内容第一章: 数据结构与算法概述; 算法分析; 冒泡排序; 选择排序; 插入排序; 希尔排序; 归并排序;第二章: 快速排序; 排序稳定性分析; 顺序表; 链表;第三章: 栈; 队列; 符号表; 二叉查找树;第...
此外,本书还介绍了各种高级或特殊数据结构,如优先级队列、高效二叉查找树、多路查找树等。本书对大多数算法都给出了计算时间在最优、最差情形下的复杂度分析。 本书不仅可以作为计算机及相关专业本科生“数据...
在无法使用二叉查找树的时候,这三种数据结构证明对查找是很有用的。他们是:AVL树、红黑树和跳跃表。 第16章讨论了图以及图的算法。图在表示许多不同的数据类型时非常有用,特别是网络的情况。最后,第17章向读者...
数据结构和算法能起到什么作用? 数据结构的概述 算法的概述 一些定义 面向对象编程 软件工程 对于C++程序员的Java Java数据结构的类库 小结 问题 第2章 数组 Array专题Applet Java中数组的基础知识 将...
此外,《数据结构基础(C语言版)(第2版)》还介绍了各种高级或特殊数据结构,如优先级队列、高效二叉查找树、多路查找树等。《数据结构基础(C语言版)(第2版)》对大多数算法都给出了计算时间在最优、最差情形下的复杂度...