- 浏览: 51695 次
- 性别:
- 来自: 湘潭
-
文章分类
最新评论
-
yuxingfirst:
Mon__cherie 写道无意中发现一个bug当数组中有两个 ...
算法研究系列---快速排序 -
Mon__cherie:
无意中发现一个bug
当数组中有两个一样的数字事 whi ...
算法研究系列---快速排序 -
fka2004:
学习了,谢谢~~
算法研究系列---快速排序 -
yuxingfirst:
自己先占个坐,由于小弟水平有限,有不对的地方,请各位指正... ...
对java的一些总结<一> -
yuxingfirst:
补充:上面程序中的“//是在给maze分配内存的时候有点点问题 ...
自己写的链栈实现的迷宫算法,发帖纪念下...
查找树以便于查找的方式来存放数据,尤其是二叉查找树,二叉查找树的特性使其可以使用简单的递归算法进行查找,这种算法在思路上类似于数组的折半查找,且同样高效.
二叉查找树是其节点含有Comparable的对象,并且按如下组织的二叉树:
1:节点的数据大于节点的左子树中的数据。
2:节点的数据小于节点的右子树中的数据。
下面着重讨论如何基于java实现二叉查找树 并实现 诸如:插入,查找,删除,遍历等方法
package tree; public class BinaryTree { // Root node pointer. Will be null for an empty tree. private Node root; /* --Node-- The binary tree is built using this nested node class. Each node stores one data element, and has left and right sub-tree pointer which may be null. The node is a "dumb" nested class -- we just use it for storage; it does not have any methods. */ private static class Node { Node left; Node right; int data; Node(int newData) { left = null; right = null; data = newData; } } public BinaryTree() { root = null; } /** Returns true if the given target is in the binary tree. Uses a recursive helper. */ public boolean lookup(int data) { return(lookup(root, data)); } /** Recursive lookup -- given a node, recur down searching for the given data. */ private boolean lookup(Node node, int data) { if (node==null) { return(false); } if (data==node.data) { return(true); } else if (data<node.data) { return(lookup(node.left, data)); } else { return(lookup(node.right, data)); } } /** Inserts the given data into the binary tree. Uses a recursive helper. */ public void insert(int data) { root = insert(root, data); } /** Remove the given data into the binary tree Uses a recursive helper */ public void remove(int data){ remove(root, data); } private Node remove(Node node, int data) { if(node == null) { return null; } if(data < node.data) { node.left = remove(node.left,data); } else if(data > node.data) { node.right = remove(node.right,data); } else{ if(node.left != null && node.right != null) { node.data = findMax(node.right).data; node.right = removeMax(node.right); } else { node = ((node.left == null) ? node.right:node.left); } } return node; } private Node removeMax(Node node) { if(node != null) { if(node.right != null) { removeMax(node.right); } else { node = node.left; } } return node; } private Node findMax(Node node) { if(node != null) { while(node.right != null) { node = node.right; } } return node; } private Node remove2(Node node, int data) { if(node == null) { return node; } if(node.data < data) { node.right = remove2(node.right,data); } else if(node.data > data) { node.left = remove2(node.left,data); } else { if(node.left != null && node.right != null) { node.data = findMin(node.left).data; node.left = removeMin(node.left); } else { node = ((node.left == null) ? node.right:node.left); } } return node; } private Node removeMin(Node node) { if(node != null) { if(node.left != null) { removeMin(node.left); } else { node = node.right; } } return node; } private Node findMin(Node node) { if(node != null) { while(node.left != null) { node = node.left; } } return node; } private Node insert(Node node, int data) { if (node==null) { node = new Node(data); } else { if (data <= node.data) { node.left = insert(node.left, data); } else { node.right = insert(node.right, data); } } return(node); } /** * 中序历遍 */ public void inOrderTraverse() { inOrderTraverse(root); } /** * 先序历遍 */ public void preOrderTraverse(){ preOrderTraverse(root); } /** * 后序历遍 * @param node */ public void lastOrderTraverse(){ lastOrderTraverse(root); } private void lastOrderTraverse(Node node){ if(node != null) { lastOrderTraverse(node.left); lastOrderTraverse(node.right); System.out.print(node.data + " "); } } private void preOrderTraverse(Node node){ if(node != null) { System.out.print(node.data + " "); preOrderTraverse(node.left); preOrderTraverse(node.right); } } private void inOrderTraverse(Node node) { if(node == null) { return; } inOrderTraverse(node.left); System.out.print(node.data + " "); inOrderTraverse(node.right); } }
package test;
import tree.BinaryTree; public class TestBinaryTree { /** * @param args */ public static void main(String[] args) { BinaryTree biTree=new BinaryTree(); int[] data={2,1,3,5,4,55,1245}; for(int i=0; i < data.length; i++) { biTree.insert(data[i]); } biTree.preOrderTraverse(); System.out.println(); biTree.insert(5); biTree.preOrderTraverse(); System.out.println(); biTree.remove(2); biTree.inOrderTraverse(); System.out.println(); } }
上述代码实现了一颗二叉查找树,并提供了插入,删除,遍历,查找节点的操作,下面一一解释各操作:
插入: 往二叉查找树中插入元素是一个基本操作,因为它正是建树时的基本操作。假设已有一颗二叉查找树,如要往其中插入一个新元素,首先必须要确保节点间的相互关系,即需要保证插入元素后的树仍是一颗二叉查找树,并且须保证方法lookup能找到这个元素,同时,每次的插入操作都是给这棵树加上一个新的叶子节点.
遍历,查找:这两个操作比较简单,采用递归方式,具体实现如代码.
删除: 删除操作可以说是最复杂的一个了,为了从二叉查找树中删除元素,需要将与之相匹配的元素传递给方法remove,待删除的元素随后从树中删除并返回, 如果不存在这样的元素则返回null
但是删除元素时,不是简单的删除就可以了,这里需要看待删除的元素的左右孩子的情况:
1:节点没有孩子,为叶子节点
2: 该节点有一个孩子
3:该节点有两个孩子
第一种情况是最简单的,同时第二种情况也不难,只需要将该节点的一个孩子取代这个节点就可以了,这两种情况的处理可以合二为一,具体实现如代码所示
下面考虑节点有两个孩子的情况:
假设待删除的节点为N,但现在N有两个孩子,如果试图删除它,就会留下两个没有双亲的孩子,尽管节点N可以被其中一个所取代,但总会有一个孩子没有双亲,即总有一个孩子没有被引用,所以删除节点N 的办法是不可行的.
实际上,并不是非得删除节点N才能删除其中的元素,这里,不防寻找一个容易删除的节点,我们称为A,这个节点A只有一个孩子或者没有孩子,然后将节点N中的元素用A中的元素替代,随后删除节点A,并使树中仍然还有正确的元素,但是这里的一个问题,如何确定这个节点A,并保证树仍然为二叉查找树呢? 显然,节点A是不可以随便选择的,它必须有可以合法的替代节点N中的元素的条件。
假设e为N中的元素,因为节点N有两个孩子,则e不可能是树中最小的元素,也不可能是最大元素,(为了讨论方便,假设树中没有重复元素), 并且书中没有重复的元素,若树中元素升序排列,所以有:
...a<e<b...(a,b为节点N左右孩子的元素)
由于a为节点N的左子树中的元素,b为节点N右子树中的元素,且有上述关系,我们可以想到 a将是N左子树中最大的元素,b是右子树中最小的元素。现假定删除了还有a的节点X,并用a替代e,那么现在N的左子树中所有剩下的元素都小于a,满足所需条件,而且N的右子树中的所有的元素都大于e,从而也大于a,因此该树仍是二叉查找树.
那么如何寻找元素a呢? 假设以上论述能够找到适当的俄元素a,所以现在应寻找含有a的节点并且确认他没有两个孩子,为了找到比任一个指定节点中的元素更大的元素,需要查看这个节点的右孩子,因此,a位于这颗子树最右侧的节点R中, 节点R不可能有右孩子,因为如果他有的话,该孩子的元素就会大于a,因此节点R的孩子不可能多余一个,可以很容易的删除它。
下面总结上述讨论(由于节点N的右子树情况类似于左子树,不过右子树中我们只要找右子树中最左侧的节点就可以了):
1: 删除位于有两个孩子的节点N中的元素e
找到N的左子树中最右侧的节点R
以节点R中的元素替代节点N的元素
删除节点R
2: 删除位于有两个孩子的节点N中的元素e
找到N的右子树中最左侧的节点L,
以节点L中的元素替代节点N的元素,
删除节点L
发表评论
-
Lucene02----整体架构
2011-12-02 13:57 835Lucene的总体架构 Lucene ... -
Lucene02----整体架构
2011-11-30 13:36 5Lucene的总体架构 Lucene ... -
Lucene01----全文索引
2011-11-30 13:29 913一:全文检索 在文本检索里,全文索引是一种搜索单 ... -
Java HashMap分析
2011-11-29 13:07 1034基于哈希表 ... -
stack heap
2011-10-19 00:00 774一、预备知识—程序的内存分配 一个由C/C++编译的程 ... -
关于IntegerCache的理解
2011-10-17 16:51 2387今天在javaeye上看到一兄弟贴的代码, ... -
记录2
2011-10-11 22:47 7线程池的原理: ... -
记录1
2011-10-11 22:41 10链表、树、线程安全、 ... -
面试题汇总
2011-10-11 22:35 10/////////////////////////////// ... -
算法研究系列---快速排序
2011-10-09 01:07 1225快速排序是由冒泡排序改进而来的. 算法思想: ... -
算法研究系列---冒泡排序
2011-10-08 16:34 922为了毕业面试需要,计划好好的研究一遍算法,以博客的形式记录下来 ... -
谈谈对于企业级系统架构的理解
2011-05-30 00:49 717在我们刚开始学习架构的时候,首先会想到分层的概念,分层架构 ... -
字符集和整理
2011-03-27 16:07 1006整理 描述 armscii8 (ARMSCI ... -
页面静态化方案
2011-03-08 22:13 841在大型网站中,访问者看到的页面基本上是静态页面。为什么都要 ... -
ASCII
2011-03-01 08:23 866ASCII表 ASCII值 控制字符 A ... -
解决方案:Tomcat启动时窗口一闪而过(startup.bat)
2011-02-22 22:23 3369有时候我们在apache网站上下载了tomcat的zip包后, ... -
对于构造方法有可能产生异常的情况下垃圾清理问题的研究
2011-02-17 16:23 992有时候我们可能会问:“当异常发生的时候,所有的东西都会被 ... -
String ,StringBuilder,StringBuffer的区别
2011-02-17 16:18 812String类代表字符串,java ... -
Java 技术新手入门
2011-01-11 21:31 812Java 技术是什么? ... -
数组的初始化
2011-01-10 13:27 938就我自己而言,一般在 ...
相关推荐
最近在研究数据结构这本书,自己动手实现的一个二叉查找排序树的类BinSortTree,实现数据的插入,查找,删除,层序遍历,中序遍历等操作,熟悉数据结构的朋友都知道,根据二叉排序树的定义,中序遍历后得到的序列...
二叉排序树(Binary Search Tree),又称二叉查找树,是一种特殊的二叉树,其中每个节点的值大于或等于其左子树中所有节点的值,并且小于或等于其右子树中所有节点的值。这一特性使得二叉排序树能够快速定位节点,...
6. **数据结构**:除了算法,源代码也可能涉及各种数据结构的实现,如链表、栈、队列、堆、树(二叉搜索树、平衡树如AVL和红黑树)等。这些数据结构是构建高效算法的基础。 7. **数值与计算方法**:书中可能包含...
在这个课程设计中,我们将重点探讨如何利用二叉链表作为存储结构来实现二叉排序树,并进一步研究平衡二叉排序树的概念。 首先,二叉排序树的特性是每个节点的左子树只包含小于该节点的元素,而右子树则包含大于或...
为了更深入地理解二叉排序树,你可以研究平衡二叉树,例如AVL树和红黑树,它们通过保持树的平衡来确保最坏情况下的性能也能接近最优。在实际应用中,平衡二叉树可以提供更稳定的性能表现。 总结来说,二叉排序树是...
《算法导论--教师手册》不仅涵盖了广泛的算法知识,还提供了深入的数据结构分析,适合于计算机科学教育中的本科生和研究生课程。通过本书的学习,读者可以掌握算法设计、分析和实现的核心技能,为解决实际问题提供...
此外,二叉搜索树广泛应用于数据库索引、排序、查找算法等场景。 学习二叉搜索树,不仅需要理解基本概念和操作,还要掌握如何优化和调整树的结构以适应不同场景。这包括了解如何避免退化为链表的情况(这会导致性能...
根据给定文件的信息,我们可以提炼出以下IT领域的关键知识点,主要围绕二叉排序树的...通过深入研究这段代码,可以更好地掌握二叉排序树的原理及其在实际应用中的作用,如在数据库索引、编译器符号表等场景中的应用。
在这个主题中,我们将深入探讨几个关键概念:单链表、二叉树遍历、折半查找、二叉排序树以及内部排序。 首先,单链表是一种基本的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。这种线性...
二叉排序树,又称二叉查找树或二叉搜索树,是计算机科学中一种非常重要的数据结构,尤其在处理搜索和排序操作时表现突出。它是一种特殊的二叉树,每个节点都满足以下两个条件: 1. 左子树中的所有节点的值都小于该...
例如,哈希表在数据库索引中的应用,二叉搜索树在实现高效查找中的作用,图算法在路由规划和社交网络分析中的应用。 总的来说,这份资料集提供了一个全面的学习平台,让学习者能够通过实践来掌握数据结构、算法及其...
二叉排序树(又称二叉查找树):(1)若左子树不空,则左子树上所有节点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有节点均大于它的根结点的值;(3)它的左右子树分别为二叉排序树。 二叉平衡树:若...
### 最优二叉搜索树的动态规划算法研究 #### 摘要与背景介绍 本文主要探讨了在解决最优二叉搜索树问题时所采用的一种高效算法——动态规划算法。最优二叉搜索树(Optimal Binary Search Tree, OBST)是在特定概率下...
通过研究这些源代码,开发者可以学习如何在实际项目中应用自平衡二叉查找树,提升数据结构的效率,优化算法性能,尤其是在处理大量数据的场景下。同时,了解这些数据结构的实现也有助于培养对计算机科学底层原理的...
3.3.2 红黑二叉查找树 275 3.3.3 实现 280 3.3.4 删除操作 282 3.3.5 红黑树的性质 284 3.4 散列表 293 3.4.1 散列函数 293 3.4.2 基于拉链法的散列表 297 3.4.3 基于线性探测法的散列表 300 3.4.4...
二叉树可以分为二叉查找树和非二叉查找树两种。 二叉查找树(Binary Search Tree)是一种特殊的二叉树,它的每个节点都满足以下特点: 1. 左子树的所有节点值小于根节点的值。 2. 右子树的所有节点值大于根节点的...
通过对二叉排序树的构建、遍历、查找、插入和删除等基本操作的研究与实现,不仅加深了对二叉排序树这一数据结构的理解,也为后续更复杂的数据结构与算法学习打下了坚实的基础。此外,通过比较顺序与链式两种不同的...
在这个项目中,我们将实现一个二叉排序树的查找算法,并使用C语言编写代码。 binary search tree 是一种特殊的二叉树,它的每个节点都包含一个键值,并且所有键值都遵循 左子树键值小于根节点键值,右子树键值大于...