(1)二叉树
class Tree { class Node { public long value; public Node leftChild; public Node rightChild; public Node(long value) { this.value = value; leftChild = null; rightChild = null; } } public Node root; public Tree() { root = null; } // 向树中插入一个节点 public void insert(long value) { Node newNode = new Node(value); // 树是空的 if (root == null) root = newNode; else { Node current = root; Node parentNode; while (true) { parentNode = current; if (value < current.value) { current = current.leftChild; // 要插入的节点为左孩子节点 if (current == null) { parentNode.leftChild = newNode; return; } } else { // 要插入的节点为右孩子节点 current = current.rightChild; if (current == null) { parentNode.rightChild = newNode; return; } } } } } // 先续遍历树中的所有节点 public void preOrder(Node currentRoot) { if (currentRoot != null) { System.out.print(currentRoot.value + " "); preOrder(currentRoot.leftChild); preOrder(currentRoot.rightChild); } } // 中续遍历树中的所有节点 public void inOrder(Node currentNode) { if (currentNode != null) { inOrder(currentNode.leftChild); System.out.print(currentNode.value + " "); inOrder(currentNode.rightChild); } } // 后续遍历树中的所有节点 public void postOrder(Node currentNode) { if (currentNode != null) { postOrder(currentNode.leftChild); postOrder(currentNode.rightChild); System.out.print(currentNode.value + " "); } } public void traverse(int traverseType) { switch (traverseType) { case 1: preOrder(root); break; case 2: inOrder(root); break; case 3: postOrder(root); break; default: break; } } // 依据树节点的值删除树中的一个节点 public boolean delete(int value) { // 遍历树过程中的当前节点 Node current = root; // 要删除节点的父节点 Node parent = root; // 记录树的节点为左孩子节点或右孩子节点 boolean isLeftChild = true; while (current.value != value) { parent = current; // 要删除的节点在当前节点的左子树里 if (value < current.value) { isLeftChild = true; current = current.leftChild; } // 要删除的节点在当前节点的右子树里 else { isLeftChild = false; current = current.rightChild; } // 在树中没有找到要删除的节点 if (current == null) return false; } // 要删除的节点为叶子节点 if (current.leftChild == null && current.rightChild == null) { // 要删除的节点为根节点 if (current == root) root = null; // 要删除的节点为左孩子节点 else if (isLeftChild) parent.leftChild = null; // 要删除的节点为右孩子节点 else parent.rightChild = null; } // 要删除的节点有左孩子节点,没有右孩子节点 else if (current.rightChild == null) { // 要删除的节点为根节点 if (current == null) root = current.leftChild; // 要删除的节点为左孩子节点 else if (isLeftChild) parent.leftChild = current.leftChild; // 要删除的节点为右孩子节点 else parent.rightChild = current.leftChild; } // 要删除的节点没有左孩子节点,有右孩子节点 else if (current.leftChild == null) { // 要删除的节点为根节点 if (current == root) root = root.rightChild; // 要删除的节点为左孩子节点 else if (isLeftChild) parent.leftChild = current.rightChild; // 要删除的节点为右孩子节点 else parent.rightChild = current.rightChild; } // 要删除的接节点既有左孩子节点又有右孩子节点 else { Node successor = getSuccessor(current); // 要删除的节点为根节点 if (current == root) root = successor; // 要删除的节点为左孩子节点 else if (isLeftChild) parent.leftChild = successor; // 要删除的节点为右孩子节点 else parent.rightChild = successor; } return true; } // 找到要删除节点的替补节点 private Node getSuccessor(Node delNode) { // 替补节点的父节点 Node successorParent = delNode; // 删除节点的替补节点 Node successor = delNode; Node current = delNode.rightChild; while (current != null) { // successorParent指向当前节点的上一个节点 successorParent = successor; // successor变为当前节点 successor = current; current = current.leftChild; } // 替补节点的右孩子节点不为空 if (successor != delNode.rightChild) { successorParent.leftChild = successor.rightChild; successor.rightChild = delNode.rightChild; } return successor; } } public class TreeApp { public static void main(String[] args) { Tree tree = new Tree(); tree.insert(8); tree.insert(50); tree.insert(45); tree.insert(21); tree.insert(32); tree.insert(18); tree.insert(37); tree.insert(64); tree.insert(88); tree.insert(5); tree.insert(4); tree.insert(7); System.out.print("PreOrder : "); tree.traverse(1); System.out.println(); System.out.print("InOrder : "); tree.traverse(2); System.out.println(); System.out.print("PostOrder : "); tree.traverse(3); System.out.println(); System.out.println(tree.delete(7)); System.out.print("PreOrder : "); tree.traverse(1); System.out.println(); System.out.print("InOrder : "); tree.traverse(2); System.out.println(); System.out.print("PostOrder : "); tree.traverse(3); System.out.println(); } }
原文:http://yongsky.iteye.com/blog/130878
发表评论
-
Java添加UTF-7字符集支持(转)
2014-08-16 16:20 814这段时间在做PushServer时,需要对编码过的邮件标题及 ... -
问题记录
2012-05-02 20:58 451. 如何使java打印byte类型数据? 如: / ... -
利用java反射机制实现IoC容器
2011-07-05 17:44 0P717 -- P719 -
网址资源保存
2011-05-18 18:20 90xwork 下载地址: http://release.ope ... -
JAVA工具类(暂保存草稿,如果发表的话需要分别修改验证工具类内容)
2010-09-15 00:02 0(暂保存草稿,如果发表的话需要分别修改验证工具类内容) ... -
Collection之映射表(Maps)
2010-09-07 11:08 1319映射表(map)用来存放键/值对,如果提供了键,就能够找到值, ... -
Collection之双端队列与优先级队列(Priority queue)
2010-09-06 10:28 1938双端队列 在Java SE6中,引入了Deque接口,并由A ... -
Collection之树集(TreeSet)
2010-09-04 23:50 1065TreeSet与HashSet类似,不过TreeSet是一个有 ... -
Collection之散列表(hash table)
2010-09-04 22:10 869链表和数组中元素是按一定次序进行排列的,散列表不在意元素的顺序 ... -
Collection之数组列表
2010-09-02 17:52 845数组列表(ArrayList)和上文中介绍的链表(Li ... -
Collection之链表
2010-09-02 11:00 869在Java语言中,所有的链表都是双向链接的(doubly li ... -
Concrete Collection集合概要
2010-09-02 00:22 748Java类库中的具体的集合: ArrayList 一种可以 ... -
泛型代码与虚拟机
2010-08-31 22:27 824虚拟机没有泛型对象,所有对象都属于普通类,使用当前Sun的编译 ... -
JAVA集合接口
2010-08-31 16:49 1245集合接口,JAVA集合类库 ... -
JAVA静态成员和静态内部类
2010-08-29 10:45 2145静态类(static class)即定义了静态方法,静 ...
相关推荐
java数据结构和算法--第二版
Java数据结构和算法-带书签目录扫描版 带完整目录书签的清晰扫描版本
Java数据结构和算法.(第二版).pdf Java数据结构和算法-第二版-高清扫描版-带目录书签
国外经典计算机科学教材,中文版,【美】Robert Lafore著,计晓云,赵研等翻译。JAVA数据结构与算法-第二版。
Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
主要内容包括:面向对象编程的基本原理,判定算法效率的方法,堆栈、队列及其应用,对于多种递归的详细讨论,二叉树、B树、2-4树等的查找和遍历等,分析排序、散列等数据结构的应用,图、NP完整性,数据压缩算法、...
JAVA数据结构和算法,帮助您无忧入门JAVA
Java数据结构和算法.pdf
数据结构与算法--Java语言描述,打好基础必备,提高自己的代码水平
Java数据结构和算法第七讲.avi Java数据结构和算法第三十一讲.avi Java数据结构和算法第三十七讲.avi Java数据结构和算法第三十三讲.avi Java数据结构和算法第三十九讲.avi Java数据结构和算法第三十二讲.avi Java...
《Java数据结构和算法》(第2版)介绍了计算机编程中使用的数据结构和算法,对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和...
虽然有许许多多关于数据结构与算法的书籍,但是这些书籍通常都是大学教材,而且是用在大学里经典讲授的Java语言或C++语言编写的。C#语言正在成为一种广受欢迎的编程语言。这本书为C#语言程序员提供了学习基础数据...
javalist数据结构_Java数据结构-------List 三种List:ArrayList,Vector,LinkedList 类继承关系图 ArrayList和Vector通过数组实现,⼏乎使⽤了相同的算法;区别是ArrayList不是线程安全的,Vector绝⼤多数⽅法做了...
数据结构与算法分析--java语言描述.pdf
java 数据结构和算法, 排序算法, 数组,链表,二叉树
数据结构、算法
包含了各种数据结构和算法(java)的实现方式和详解(图解),包括单双链表、环形链表(约瑟夫问题)、栈、后缀表达式、中缀表达式转后缀表达式、迷宫问题、八大排序算法、多种查找算法、哈希表、二叉树实现以及操作...