- 浏览: 400519 次
- 性别:
- 来自: 天津
文章分类
最新评论
-
junchao_qin:
[img][flash=200,200][url][img]引 ...
MyEclipse中使用VSS插件 -
tigerwood008:
IE11不好用!!
js弹出窗口 + 获取上传文件全路径 -
TheMatrix:
$.ajaxSetup({async : false});这种 ...
jquery 中的post和get方法如何同步 -
多多成长记:
Blazeds与java通信 -
ZED.CWT:
[align=ceiinter][/align]
java中利用JFrame创建窗体 【转】
转自:http://blog.csdn.net/zyj8170/article/details/7045226
- /**
- * @author zyj8170 2011-2-13
- *
- * 此程序实现一个二叉查找树的功能,可以进行动态插入、删除关键字;
- * 查询给定关键字、最小关键字、最大关键字;转换为有序列表(用于排序)
- *
- *
- */
- import java.util.ArrayList;
- import java.util.List;
- public class BinarySearchTree {
- // 树的根结点
- private TreeNode root = null ;
- // 遍历结点列表
- private List<TreeNode> nodelist = new ArrayList<TreeNode>();
- private class TreeNode {
- private int key;
- private TreeNode leftChild;
- private TreeNode rightChild;
- private TreeNode parent;
- public TreeNode( int key, TreeNode leftChild, TreeNode rightChild,
- TreeNode parent) {
- this .key = key;
- this .leftChild = leftChild;
- this .rightChild = rightChild;
- this .parent = parent;
- }
- public int getKey() {
- return key;
- }
- public String toString() {
- String leftkey = (leftChild == null ? "" : String
- .valueOf(leftChild.key));
- String rightkey = (rightChild == null ? "" : String
- .valueOf(rightChild.key));
- return "(" + leftkey + " , " + key + " , " + rightkey + ")" ;
- }
- }
- /**
- * isEmpty: 判断二叉查找树是否为空;若为空,返回 true ,否则返回 false .
- *
- */
- public boolean isEmpty() {
- if (root == null ) {
- return true ;
- } else {
- return false ;
- }
- }
- /**
- * TreeEmpty: 对于某些二叉查找树操作(比如删除关键字)来说,若树为空,则抛出异常。
- */
- public void TreeEmpty() throws Exception {
- if (isEmpty()) {
- throw new Exception( "树为空!" );
- }
- }
- /**
- * search: 在二叉查找树中查询给定关键字
- *
- * @param key
- * 给定关键字
- * @return 匹配给定关键字的树结点
- */
- public TreeNode search( int key) {
- TreeNode pNode = root;
- while (pNode != null && pNode.key != key) {
- if (key < pNode.key) {
- pNode = pNode.leftChild;
- } else {
- pNode = pNode.rightChild;
- }
- }
- return pNode;
- }
- /**
- * minElemNode: 获取二叉查找树中的最小关键字结点
- *
- * @return 二叉查找树的最小关键字结点
- * @throws Exception
- * 若树为空,则抛出异常
- */
- public TreeNode minElemNode(TreeNode node) throws Exception {
- if (node == null ) {
- throw new Exception( "树为空!" );
- }
- TreeNode pNode = node;
- while (pNode.leftChild != null ) {
- pNode = pNode.leftChild;
- }
- return pNode;
- }
- /**
- * maxElemNode: 获取二叉查找树中的最大关键字结点
- *
- * @return 二叉查找树的最大关键字结点
- * @throws Exception
- * 若树为空,则抛出异常
- */
- public TreeNode maxElemNode(TreeNode node) throws Exception {
- if (node == null ) {
- throw new Exception( "树为空!" );
- }
- TreeNode pNode = node;
- while (pNode.rightChild != null ) {
- pNode = pNode.rightChild;
- }
- return pNode;
- }
- /**
- * successor: 获取给定结点在中序遍历顺序下的后继结点
- *
- * @param node
- * 给定树中的结点
- * @return 若该结点存在中序遍历顺序下的后继结点,则返回其后继结点;否则返回 null
- * @throws Exception
- */
- public TreeNode successor(TreeNode node) throws Exception {
- if (node == null ) {
- return null ;
- }
- // 若该结点的右子树不为空,则其后继结点就是右子树中的最小关键字结点
- if (node.rightChild != null ) {
- return minElemNode(node.rightChild);
- }
- // 若该结点右子树为空
- TreeNode parentNode = node.parent;
- while (parentNode != null && node == parentNode.rightChild) {
- node = parentNode;
- parentNode = parentNode.parent;
- }
- return parentNode;
- }
- /**
- * precessor: 获取给定结点在中序遍历顺序下的前趋结点
- *
- * @param node
- * 给定树中的结点
- * @return 若该结点存在中序遍历顺序下的前趋结点,则返回其前趋结点;否则返回 null
- * @throws Exception
- */
- public TreeNode precessor(TreeNode node) throws Exception {
- if (node == null ) {
- return null ;
- }
- // 若该结点的左子树不为空,则其前趋结点就是左子树中的最大关键字结点
- if (node.leftChild != null ) {
- return maxElemNode(node.leftChild);
- }
- // 若该结点左子树为空
- TreeNode parentNode = node.parent;
- while (parentNode != null && node == parentNode.leftChild) {
- node = parentNode;
- parentNode = parentNode.parent;
- }
- return parentNode;
- }
- /**
- * insert: 将给定关键字插入到二叉查找树中
- *
- * @param key
- * 给定关键字
- */
- public void insert( int key) {
- TreeNode parentNode = null ;
- TreeNode newNode = new TreeNode(key, null , null , null );
- TreeNode pNode = root;
- if (root == null ) {
- root = newNode;
- return ;
- }
- while (pNode != null ) {
- parentNode = pNode;
- if (key < pNode.key) {
- pNode = pNode.leftChild;
- } else if (key > pNode.key) {
- pNode = pNode.rightChild;
- } else {
- // 树中已存在匹配给定关键字的结点,则什么都不做直接返回
- return ;
- }
- }
- if (key < parentNode.key) {
- parentNode.leftChild = newNode;
- newNode.parent = parentNode;
- } else {
- parentNode.rightChild = newNode;
- newNode.parent = parentNode;
- }
- }
- /**
- * insert: 从二叉查找树中删除匹配给定关键字相应的树结点
- *
- * @param key
- * 给定关键字
- */
- public void delete( int key) throws Exception {
- TreeNode pNode = search(key);
- if (pNode == null ) {
- throw new Exception( "树中不存在要删除的关键字!" );
- }
- delete(pNode);
- }
- /**
- * delete: 从二叉查找树中删除给定的结点.
- *
- * @param pNode
- * 要删除的结点
- *
- * 前置条件: 给定结点在二叉查找树中已经存在
- * @throws Exception
- */
- private void delete(TreeNode pNode) throws Exception {
- if (pNode == null ) {
- return ;
- }
- if (pNode.leftChild == null && pNode.rightChild == null ) { // 该结点既无左孩子结点,也无右孩子结点
- TreeNode parentNode = pNode.parent;
- if (pNode == parentNode.leftChild) {
- parentNode.leftChild = null ;
- } else {
- parentNode.rightChild = null ;
- }
- return ;
- }
- if (pNode.leftChild == null && pNode.rightChild != null ) { // 该结点左孩子结点为空,右孩子结点非空
- TreeNode parentNode = pNode.parent;
- if (pNode == parentNode.leftChild) {
- parentNode.leftChild = pNode.rightChild;
- pNode.rightChild.parent = parentNode;
- } else {
- parentNode.rightChild = pNode.rightChild;
- pNode.rightChild.parent = parentNode;
- }
- return ;
- }
- if (pNode.leftChild != null && pNode.rightChild == null ) { // 该结点左孩子结点非空,右孩子结点为空
- TreeNode parentNode = pNode.parent;
- if (pNode == parentNode.leftChild) {
- parentNode.leftChild = pNode.leftChild;
- pNode.rightChild.parent = parentNode;
- } else {
- parentNode.rightChild = pNode.leftChild;
- pNode.rightChild.parent = parentNode;
- }
- return ;
- }
- // 该结点左右孩子结点均非空,则删除该结点的后继结点,并用该后继结点取代该结点
- TreeNode successorNode = successor(pNode);
- delete(successorNode);
- pNode.key = successorNode.key;
- }
- /**
- * inOrderTraverseList: 获得二叉查找树的中序遍历结点列表
- *
- * @return 二叉查找树的中序遍历结点列表
- */
- public List<TreeNode> inOrderTraverseList() {
- if (nodelist != null ) {
- nodelist.clear();
- }
- inOrderTraverse(root);
- return nodelist;
- }
- /**
- * inOrderTraverse: 对给定二叉查找树进行中序遍历
- *
- * @param root
- * 给定二叉查找树的根结点
- */
- private void inOrderTraverse(TreeNode root) {
- if (root != null ) {
- inOrderTraverse(root.leftChild);
- nodelist.add(root);
- inOrderTraverse(root.rightChild);
- }
- }
- /**
- * toStringOfOrderList: 获取二叉查找树中关键字的有序列表
- *
- * @return 二叉查找树中关键字的有序列表
- */
- public String toStringOfOrderList() {
- StringBuilder sbBuilder = new StringBuilder( " [ " );
- for (TreeNode p : inOrderTraverseList()) {
- sbBuilder.append(p.key);
- sbBuilder.append(" " );
- }
- sbBuilder.append("]" );
- return sbBuilder.toString();
- }
- /**
- * 获取该二叉查找树的字符串表示
- */
- public String toString() {
- StringBuilder sbBuilder = new StringBuilder( " [ " );
- for (TreeNode p : inOrderTraverseList()) {
- sbBuilder.append(p);
- sbBuilder.append(" " );
- }
- sbBuilder.append("]" );
- return sbBuilder.toString();
- }
- public TreeNode getRoot() {
- return root;
- }
- public static void testNode(BinarySearchTree bst, TreeNode pNode)
- throws Exception {
- System.out.println("本结点: " + pNode);
- System.out.println("前趋结点: " + bst.precessor(pNode));
- System.out.println("后继结点: " + bst.successor(pNode));
- }
- public static void testTraverse(BinarySearchTree bst) {
- System.out.println("二叉树遍历:" + bst);
- System.out.println("二叉查找树转换为有序列表: " + bst.toStringOfOrderList());
- }
- public static void main(String[] args) {
- try {
- BinarySearchTree bst = new BinarySearchTree();
- System.out.println("查找树是否为空? " + (bst.isEmpty() ? "是" : "否" ));
- int [] keys = new int [] { 15 , 6 , 18 , 3 , 7 , 13 , 20 , 2 , 9 , 4 };
- for ( int key : keys) {
- bst.insert(key);
- }
- System.out.println("查找树是否为空? " + (bst.isEmpty() ? "是" : "否" ));
- TreeNode minkeyNode = bst.minElemNode(bst.getRoot());
- System.out.println("最小关键字: " + minkeyNode.getKey());
- testNode(bst, minkeyNode);
- TreeNode maxKeyNode = bst.maxElemNode(bst.getRoot());
- System.out.println("最大关键字: " + maxKeyNode.getKey());
- testNode(bst, maxKeyNode);
- System.out.println("根结点关键字: " + bst.getRoot().getKey());
- testNode(bst, bst.getRoot());
- testTraverse(bst);
- System.out.println("****************************** " );
- testTraverse(bst);
- } catch (Exception e) {
- System.out.println(e.getMessage());
- e.printStackTrace();
- }
- }
-
}
发表评论
-
判断二叉树是否平衡及计算二叉树深度和结点个数
2012-09-01 10:12 7649参考:http://blog.csdn.net/zz19880 ... -
二叉树及其遍历
2012-08-21 09:50 1508转自:http://www.iteye.com/t ... -
java栈中缀表达式转为后缀表达式
2012-07-19 11:33 2413思路: 遇到数字,则输出。 遇到操作符,入栈,在入栈前若该 ... -
java栈实现括号匹配
2012-07-19 09:48 4502算法思想: 做一个空栈,读入字符。 若字符是左运算符,则入 ... -
【转】java静态变量和实例变量的区别
2012-06-20 11:02 1291转自:http://www.2cto.com/kf/20100 ... -
【转】java中会存在内存泄漏吗,请简单描述。
2012-06-20 10:24 1341java中 ... -
【转】java匿名内部类2
2012-06-12 13:45 1169匿名内部类就是没有名字的内部类。什么情况下需要使用匿名内部类? ... -
【转】java匿名内部类
2012-06-12 13:32 1382java匿名内部类 (2010-11 ... -
【转】JAVA中获取路径
2012-03-25 16:57 813转自:http://wenku.baidu.com/view/ ... -
【转】Map遍历
2012-03-25 16:56 908转自:http://wenku.baidu.com/view/ ... -
【转】java解析xml文件四种方式
2012-03-25 16:54 1325转自:http://wenku.baidu.com ... -
【转】JDOM解析处理xml
2012-03-25 16:52 1193转自http://qingbyqing.iteye.com/b ... -
【转】解析Html页面:HTML Parser的试用
2012-03-24 15:10 1365转自:http://blog.csdn.net/scud/ar ... -
【转】java随机排列数组
2012-02-20 18:58 2325转自:http://blog.csdn.net/liang ... -
设计模式——代理模式
2012-01-06 13:14 1232代理模式: 为其他对象提供一种代理以控制对这个对象的访问 ... -
设计模式——装饰模式
2012-01-05 15:58 1230首先介绍三个重要原则: 依赖倒转原则:高层模块不应该依赖于 ... -
设计模式——策略模式 & 单例模式
2011-12-29 16:26 1469策略模式: * 策略模式定义了算法家族,分别封装起来,让他 ... -
排序算法
2011-12-28 22:41 902参考:http://student.zjzk.cn/cours ... -
设计模式——简单工厂 VS 工厂方法
2011-12-28 15:07 1140简单工厂模式: 它最大优点在于工厂类中包含了必要的逻辑 ... -
String
2011-12-27 10:53 12221. String s = new String(" ...
相关推荐
说明: 可实现:构造树,插入,查找,删除. 通过模式的选择,可以插入值相等的点.但是不建议使用.
二叉查找树的实现。包括树的平衡以及树节点的删除。以及树的广度优先遍历,深度优先遍历。
java实现二叉查找树的插入、删除、遍历、查询
二叉查找树实现源码(C、C++、JAVA)
二叉搜索树的效率: 树的大部分操作需要从上至下一层层的查找树的节点,对于一棵满树,大约有一半的节点处于最底层(最底层节点数 = 其它层节点数的和 + 1),故节点操作大约有一半需要找到最底层节点,大约有四分...
C++编写的查找算法,用二叉排序树查找,是在VC++6.0上实现的
主要介绍了Java基于二叉查找树实现排序功能,结合实例形式分析了Java二叉查找树的定义、遍历及排序等相关操作技巧,需要的朋友可以参考下
ios编程:实现二叉排序树增删改查。 开发环境:windows下codeblocks。
二叉查找树是以一种特殊的二叉树。它的特征是,没一个节点左子树中结点的值都小于该结点的值,右子树中结点的值都大于该结点的值。 二叉查找树的主要操作是插入元素、删除元素、遍历元素。 插入元素:如果...
分别采用二叉链表和顺序表作存储结构,实现对二叉排序树与平衡二叉树的操作。 重庆理工大学,软件工程系,课程设计。
下面小编就为大家分享一篇Java创建二叉搜索树,实现搜索,插入,删除的操作实例,具有很好的参考价值,希望对大家有所帮助
本文主要介绍了Java实现二叉搜索树的查找、插入、删除、遍历等内容。具有很好的参考价值,下面跟着小编一起来看下吧
主要为大家详细介绍了java二叉查找树的实现代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
界面操作二叉树的查找,并可观察结果。是桌面程序
如果您想在Matlab中实现查找二叉排序树,可以按照以下步骤进行: 1/定义二叉树节点类型 2/实现二叉排序树的插入操作 3/实现二叉排序树的查找操作
主要介绍了java 二叉查找树实例代码的相关资料,需要的朋友可以参考下
java使用jtree动态实现二叉树,包含二叉树的插入删除很查找
主要介绍了Java删除二叉搜索树的任意元素的方法,结合实例形式详细分析了java这对二叉搜索树的遍历、查找、删除等相关操作技巧与使用注意事项,需要的朋友可以参考下
凸包问题(包含蛮力算法和快速凸包算法两种解法)+最优二叉查找树,并且都利用javafx生成可视化界面,开箱即用,代码含注释,原理通俗易懂。
C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 03选择排序 04顺序排序 05折半排序 06递归算法 07递归折半查找 08算法_perm 09插入排序 10快速排序 11归并排序 12顺序栈 13顺序队列 14链表的基本概率 15...