使用JAVA中的List构建二叉排序树。其中,iterator方法不知道怎么样写,请大伙支援?代码如下:
import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class BinaryTreeList<E> extends AbstractSingleLinkedList<E> implements List<E> ,java.io.Serializable { private static final long serialVersionUID = -5672690815694732101L; private Entry<E> root; private int size ; public BinaryTreeList() { this.root = null; } public boolean add(E e) { Entry<E> newEntry = new Entry<E>(e,null,null); if (this.root == null) { this.root = newEntry; } else { Comparable<? super E> k = (Comparable<? super E>) e; Entry<E> currentEntry = this.root; Entry<E> parentEntry = null; int result = 0; while (currentEntry != null) { result = k.compareTo(currentEntry.data); parentEntry = currentEntry; if (result > 0) { currentEntry = currentEntry.rigthChild; } else { currentEntry = currentEntry.leftChild; } } if (result > 0) { parentEntry.rigthChild = newEntry; } else { parentEntry.leftChild = newEntry; } } size ++; return true; } public Entry<E> getRoot() { return this.root; } /** * 使用递归遍历tree * @param tree * @param result * @return */ private void preOrder(Entry<E> tree,List<E> result) { if (tree != null) { preOrder(tree.leftChild,result); result.add(tree.data); preOrder(tree.rigthChild,result); } } public List<E> showTree() { List<E> result = new ArrayList<E>(size); preOrder(getRoot(),result); return result; } @Override public Iterator<E> singleListIterator() { /** * 这个地方怎么样实现呢 ? * 就是怎么样把递归写成循环? */ return new Iterator<E>() { private Entry<E> current = root; @Override public boolean hasNext() { return false; } @Override public E next() { return null; } @Override public void remove() { throw new UnsupportedOperationException("can not remove"); } }; } @Override public E get(int index) { throw new UnsupportedOperationException("can not get"); } @Override public int size() { return size; } public static class Entry<E>{ E data; Entry<E> leftChild; Entry<E> rigthChild; public Entry(E e,Entry<E> leftChild,Entry<E> rigthChild) { this.data = e; this.leftChild = leftChild; this.rigthChild = rigthChild; } } }
测试类如下:
import junit.framework.TestCase; import org.junit.Test; public class BinaryTreeListTest extends TestCase { @Test public void testAdd() { BinaryTreeList<Integer> list = new BinaryTreeList<Integer>(); list.add(381); list.add(12); list.add(410); list.add(9); list.add(40); list.add(394); list.add(540); list.add(35); list.add(190); list.add(476); list.add(760); list.add(146); list.add(445); list.add(600); list.add(800); //preOrder(list.getRoot()); for (Integer val : list.showTree()) { System.out.print(val); System.out.print('\t'); } } /* public static void preOrder(BinaryTreeList.Entry<Integer> tree) { if (tree != null) { preOrder(tree.leftChild); System.out.print(tree.data); System.out.print('\t'); preOrder(tree.rigthChild); } } */ }
输出结果:
9 12 35 40 146 190 381 394 410 445 476 540 600 760 800
不足之处:BinaryTreeList 的对象不能使用foreach遍历出结果,必须先调用 list.showTree() 生成一个arrayList。求教:iterator怎么实现呢?
相关推荐
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...
理解使用递归方法构建二叉排序树,前序、中序、后序遍历二叉树。 学习ArrayList与LinkedList类,理解封装数组和链表两种方式定义集合类。 可以使用迭代器Iterator遍历集合的元素。 [*]理解...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
Java服务器端开发面试题篇3 数据结构,线性列表,二叉树,完全二叉平衡树,B+树,图的表示。 树的先序,中序,后序,层序遍历。能手写代码,递归和循环实现。 栈的使用 排序 常用的排序算法, 选择,冒泡,快排,堆...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
java5 1.4.1 使用object表示泛型 1.4.2 基本类型的包装 1.4.3 使用接口类型表示泛型 1.4.4 数组类型的兼容性 1.5 利用java5泛性实现泛型特性成分 1.5.1 简单的泛型类和接口 1.5.2 自动装箱/拆箱....
java5 1.4.1 使用object表示泛型 1.4.2 基本类型的包装 1.4.3 使用接口类型表示泛型 1.4.4 数组类型的兼容性 1.5 利用java5泛性实现泛型特性成分 1.5.1 简单的泛型类和接口 1.5.2 自动装箱/拆箱....
二叉搜索树是一棵二叉树,其节点排序使得对于树中的每个节点 N: 左子树只包含值小于 N 中的值的节点 右子树只包含值大于 N 中的值的节点 这是一个有效的二叉搜索树。 B 树是二叉搜索树的推广,其中每个节点有n 个...
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...
第3课 常见Java集合的实现细节 3.1 Set和Map 3.1.1 Set和Map的关系 3.1.2 HashMap和HashSet 3.1.3 TreeMap和TreeSet 3.2 Map和List 3.2.1 Map的values()方法 3.2.2 Map和List的关系 3.3 ArrayList和...
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...
17循环链表 18双项链表 19链式栈 20链式队列 21STL_list类 22基数排序 23属 24二叉树 25二叉树找数 26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36...