`
mabusyao
  • 浏览: 252737 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

二叉搜索树的java实现

阅读更多


public class BinarySearchTree<T extends Comparable> {

	private static class Entity<T extends Comparable> {
		private T node = null;
		private Entity<T> parent = null;
		private Entity<T> left = null;
		private Entity<T> right = null;
		
		public T getNode() {
			return node;
		}
		public void setNode(T node) {
			this.node = node;
		}
		public Entity<T> getParent() {
			return parent;
		}
		public void setParent(Entity<T> parent) {
			this.parent = parent;
		}
		public Entity<T> getLeft() {
			return left;
		}
		public void setLeft(Entity<T> left) {
			this.left = left;
		}
		public Entity<T> getRight() {
			return right;
		}
		public void setRight(Entity<T> right) {
			this.right = right;
		}
	}

	private Entity<T> head = null;
	
	public void append(T node) {
		Entity<T> entity = new Entity<T>();
		entity.setNode(node);
		if(head == null) {
			head = entity;
		} else {
			Entity<T> pointer = head;
			while(pointer != null) {
				if(pointer.getNode().compareTo(entity.getNode()) > 0) {
					if(pointer.getLeft() == null) {
						pointer.setLeft(entity);
						entity.setParent(pointer);
						
						break;
					}
					
					pointer = pointer.getLeft();
				} else{
					if(pointer.getRight() == null) {
						pointer.setRight(entity);
						entity.setParent(pointer);
						
						break;
					}

					pointer = pointer.getRight();
				}
			}
		}
	}
	
	public boolean remove(T node) {
		if(head == null) return false;
		
		Entity<T> pointer = head;
		while(pointer != null) {
			if(pointer.getNode().compareTo(node) > 0) {
				pointer = pointer.getLeft();
			} else if(pointer.getNode().compareTo(node) < 0) {
				pointer = pointer.getRight();
			} else {
				removeNode(pointer);
				return true;
			}
		}
		
		return false;
	}
	
	private void removeNode(Entity<T> pointer) {
		Entity<T> cursor = pointer;
		
		while(true) {
			if(cursor.getLeft() != null) {
				cursor = cursor.getLeft();
			} else if (cursor.getRight() != null) {
				cursor = cursor.getRight();
			} else {
				break;
			}
		}
		
		Entity<T> parent = cursor.getParent();
		if(parent.getNode().compareTo(cursor.getNode()) > 0) {
			parent.setLeft(null);
		} else {
			parent.setRight(null);
		}
		
		cursor.setParent(null);
		
		pointer.setNode(cursor.getNode());
		
		rebuild(pointer);
	}
	
	private void rebuild(Entity<T> pointer) {
		if(pointer != null) {
			if(pointer.getLeft() != null) {
				if(pointer.getNode().compareTo(pointer.getLeft().getNode()) < 0) {
					T node = pointer.getNode();
					
					pointer.setNode(pointer.getLeft().getNode());
					
					pointer.getLeft().setNode(node);
				}
			} 
			
			if(pointer.getRight() != null) {
				if(pointer.getNode().compareTo(pointer.getRight().getNode()) > 0) {
					T node = pointer.getNode();
					
					pointer.setNode(pointer.getRight().getNode());
					
					pointer.getLeft().setNode(node);
				}
			}
			
			if(pointer.getLeft() != null) {
				rebuild(pointer.getLeft());
			}
			
			if(pointer.getRight() != null) {
				rebuild(pointer.getRight());
			}
		}
	}
	
	public void print() {
		treeWalk(head);
		System.out.println();
	}
	
	private void treeWalk(Entity<T> entity) {
		if(entity != null) {
			treeWalk(entity.getLeft());
			System.out.print(entity.getNode() + " ");
			treeWalk(entity.getRight());
		}
	}
	
	public T search(T node) {
		T result = binarySearch(head, node);
		
		return result;
	}
	
	public T search2(T node) {
		Entity<T> top = head;
		
		while(top != null) {
			if(node.equals(top.getNode())) {
				return top.getNode();
			} 
			
			if(node.compareTo(top.getNode()) > 0) {
				top = top.getRight();
			} else {
				top = top.getLeft();
			}
		}
		
		return null;
	}
	
	public T maximun() {
		Entity<T> top = head;
		while(top.getRight() != null) {
			top = top.getRight();
		}
		
		return top.getNode();
	}
	
	public T minimum() {
		Entity<T> top = head;
		while(top.getLeft() != null) {
			top = top.getLeft();
		}
		
		return top.getNode();
	}
	
	private T binarySearch(Entity<T> top, T node) {
		if(top == null) return null;
		
		if(node.equals(top.getNode())) {
			return top.getNode();
		}
		if(node.compareTo(top.getNode()) > 0) {
			return binarySearch(top.getRight(), node);
		} else {
			return binarySearch(top.getLeft(), node);
		}
	}
	
	public static void main(String[] args) {
		BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
		
		tree.append(10);
		tree.append(5);
		tree.append(13);
		tree.append(6);
		tree.append(4);
		tree.append(18);
		tree.append(11);
		tree.append(9);
		tree.append(16);
		tree.append(7);
		tree.append(2);
		
		tree.print();
		
		tree.remove(5);
		tree.remove(18);
		
		tree.print();
		
		System.out.println(tree.search(18));
	}
	
}


分享到:
评论

相关推荐

    Java实现二叉排序树

    二叉排序树(Binary Sort Tree,BST),也称为二叉搜索树,是一种特殊的二叉树数据结构,它的每个节点都包含一个键(key)、一个关联的值、一个指向左子节点的指针和一个指向右子节点的指针。在二叉排序树中,对于...

    数据结构 二叉排序树 java图形界面实现

    二叉排序树(Binary Sort Tree,也称为二叉搜索树),是数据结构中的一种特殊类型树,它具有以下特性:对于任意一个节点,其左子树中的所有节点的值都小于该节点的值,而右子树中的所有节点的值都大于该节点的值。...

    红黑树、二叉平衡树、二叉排序树的java实现

    其次,二叉平衡树(AVL树)是最早被提出的自平衡二叉搜索树,由G. M. Adelson-Velsky和E. M. Landis于1962年提出。AVL树要求每个节点的两个子树的高度差不超过1,以确保树的高度保持在log2(n+1)的范围内。为了维持这...

    二叉查找树java

    以上就是关于二叉查找树在Java中的基本实现,包括插入、删除、遍历和查询等操作。通过这些操作,我们可以高效地管理一组有序数据,并进行各种数据操作。二叉查找树在实际应用中广泛用于数据库索引、文件系统以及各种...

    二叉搜索树的源码,加上注释和自己理解

    `BST.java`很可能是二叉搜索树的实现,`TreeDoc.java`可能包含了关于数据结构或树操作的文档,而`BSTMain.java`应该是主程序,用于测试和展示二叉搜索树的功能。 在`BST.java`中,二叉搜索树的节点可能包含以下属性...

    二叉搜索树

    在JAVA中,构建二叉搜索树通常需要定义一个Node类来表示树的节点,节点通常包含一个键值(key)、一个指向左子节点的引用和一个指向右子节点的引用。例如: ```java public class Node { int key; Node left, ...

    简单二叉查找树的java实现

    二叉查找树的实现。包括树的平衡以及树节点的删除。以及树的广度优先遍历,深度优先遍历。

    算法笔记,将有序数组转为二叉搜索树

    本文将详细解释如何将有序数组转换为二叉搜索树,包括问题描述、解题思路、Java 和 Python 实现代码以及时间和空间复杂度分析。 问题描述 给定一个整数数组 nums,其中元素已经按升序进行了排序,请将其转换为一棵...

    二叉查找树的具体实现-java

    二叉搜索树的效率: 树的大部分操作需要从上至下一层层的查找树的节点,对于一棵满树,大约有一半的节点处于最底层(最底层节点数 = 其它层节点数的和 + 1),故节点操作大约有一半需要找到最底层节点,大约有四分...

    Java创建二叉搜索树,实现搜索,插入,删除的操作实例

    Java 创建二叉搜索树、实现搜索、插入、删除的操作实例 Java 创建二叉搜索树是指通过 Java 语言实现一个二叉搜索树数据结构,该树具有查找、插入、删除等操作的功能。二叉搜索树是一种特殊的二叉树,每个节点的值...

    二叉搜索树 转为 双向链表,

    二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树结构,其每个节点的值都大于左子树中所有节点的值,...这个转换过程对于理解和实现二叉搜索树到链表的转换具有重要意义,有助于提升对数据结构和算法的理解。

    使用Java实现二叉搜索树

    这段代码展示了构建一个基本的二叉搜索树(Binary Search Tree, BST)的实现。二叉搜索树是一种特殊的二叉树,其中每个节点的值大于其左子树中所有节点的值,并且小于其右子树中所有节点的值。这种数据结构在查找、...

    数据结构二叉平衡树课程设计

    二叉平衡树是一种特殊类型的二叉树,它在保持二叉搜索树特性的同时,通过特定的结构调整策略确保了树的高度平衡。这样的平衡状态使得在树中进行查找、插入和删除等操作的时间复杂度都能保持在对数级别,极大地提高了...

    java实现二叉搜索树

    java实现二叉搜索树,包括插入和查找等基本功能

    Java实现的二叉搜索树和平衡二叉树的代码示例

    以下是一个简单的二叉搜索树的Java实现: ```java public class Node { int key; int value; Node left, right; public Node(int item) { key = item; value = item; left = right = null; } } public ...

    不同的二叉搜索树(java代码).docx

    ### 不同的二叉搜索树(Java代码) #### 核心知识点 1. **动态规划的概念与应用** 2. **二叉搜索树的基本定义及性质** 3. **使用Java实现动态规划解决组合计数问题** #### 详细解析 **1. 动态规划的概念与应用**...

    二叉查找树实现源码(C、C++、JAVA)

    C、C++和Java实现二叉查找树时,通常会定义一个结构体(或类)来表示树节点,包括键值、指向左右子节点的指针以及可能的额外信息。对于C++和Java,还可以使用面向对象的方式,定义一个类来封装插入、查找和删除的...

    java-leetcode题解之第98题验证二叉搜索树.zip

    这个“java-leetcode题解之第98题验证二叉搜索树.zip”压缩包文件显然是针对LeetCode上的第98题提供的Java解决方案。这道题目涉及的核心知识点是二叉搜索树(Binary Search Tree, BST)和树的遍历。 **二叉搜索树**...

    tree-java.rar_tree_二叉搜索树

    在Java中实现二叉搜索树,我们需要定义一个`Node`类来表示树的节点,通常包括键、值、左子节点和右子节点。接着,我们需要一个`BinarySearchTree`类来操作这些节点,包含插入、查找、删除等基本操作。 例如,在`src...

    二叉搜索树代码.zip

    常见的编程语言如C++、Java、Python都有库支持二叉搜索树的实现。 总的来说,二叉搜索树是一种高效的数据结构,能够快速地执行查找、插入和删除操作,适用于需要频繁进行这些操作的场景。理解并熟练掌握二叉搜索树...

Global site tag (gtag.js) - Google Analytics