package com.test.tree;import java.util.Iterator;/*** 編寫TreeSet類的實現程序，其中相關的迭代器使用二叉查找樹。* 在每個節點上添加一個指向其父節點的鏈* @author wyl* @param <T>*/ public class MyTreeSet<T extends Comparable<? super T>> {private BinaryNode<T> root; //根節點int modCount = 0; //記錄調整樹結構的次數public MyTreeSet(){root = null;}/*** 定義二叉查找樹的節點*/private class BinaryNode<T>{T data; //節點的值BinaryNode<T> left; //節點的左節點BinaryNode<T> right; //節點右節點BinaryNode<T> parent; //節點的父節點public BinaryNode(T data){this(data, null, null, null);}public BinaryNode(T data, BinaryNode<T> lt, BinaryNode<T> rt, BinaryNode<T> pt) {this.data = data;this.left = lt;this.right = rt;this.parent = pt;}}/*** 定義TreeSet的迭代器* @return*/public Iterator iterator(){return new MyTreeSetIterator();}private class MyTreeSetIterator implements Iterator {private BinaryNode<T> current = findMin(root);private BinaryNode<T> previous;private int expectedModCount = modCount;private boolean okToRemove = false;private boolean atEnd = false;@Overridepublic boolean hasNext() {// TODO Auto-generated method stubreturn !atEnd;}@Overridepublic T next() {// TODO Auto-generated method stubif(modCount != expectedModCount){try {throw new CurrentModificationException();} catch (CurrentModificationException e) {// TODO Auto-generated catch block e.printStackTrace();}}if(!hasNext()){try {throw new NoSuchElementException();} catch (NoSuchElementException e) {// TODO Auto-generated catch block e.printStackTrace();}}T nextItem = current.data;previous = current;if(current.right != null){current = findMin(current.right);}else{BinaryNode<T> child = current;current = current.parent;while(current != null && current.left != child){child = current;current = current.parent;}if(current == null){atEnd = true;}}okToRemove = true;return nextItem;}@Overridepublic void remove(){// TODO Auto-generated method stubif(modCount != expectedModCount){try {throw new CurrentModificationException();} catch (CurrentModificationException e) {// TODO Auto-generated catch block e.printStackTrace();}}if(!okToRemove){throw new IllegalStateException();}try {MyTreeSet.this.remove(previous.data);} catch (UnderflowException e) {// TODO Auto-generated catch block e.printStackTrace();}okToRemove = false;}}public void makeEmpty(){modCount++ ;root = null;}public boolean isEmpty(){return root == null;}public boolean contains(T x){return contains(x, root); }public boolean contains(T x, BinaryNode<T> t){if(t == null){return false;}int compareResult = x.compareTo(t.data);if(compareResult < 0){return contains(x, t.left);}else if(compareResult > 0){return contains(x, t.right);}else{return true;}}public T findMin(){if(isEmpty()){try {throw new UnderflowException();} catch (UnderflowException e) {// TODO Auto-generated catch block e.printStackTrace();}}return findMin(root).data;}public T findMax(){if(isEmpty()){try {throw new UnderflowException();} catch (UnderflowException e) {// TODO Auto-generated catch block e.printStackTrace();}}return findMax(root).data;}public void insert(T x){root = insert(x, root, null);}public void remove(T x) throws UnderflowException{root = remove(x, root);}public void printTree(){if(isEmpty()){System.out.println("Empty tree");}else{printTree(root);}}public void printTree(BinaryNode<T> t){if(t != null){printTree(t.left);System.out.println(t.data);printTree(t.right);}}public BinaryNode<T> remove(T x, BinaryNode<T> t){if(t == null){try {throw new UnderflowException();} catch (UnderflowException e) {// TODO Auto-generated catch block e.printStackTrace();}}int compareResult = x.compareTo(t.data);if(compareResult < 0){t = remove(x, t.left);}else if(compareResult > 0){t = remove(x, t.right);}else if(t.left != null && t.right != null){//要刪除的節點是含有左右子樹的節點t.data = findMin(t.right).data;//將右子樹的最小值作為根節點t.right = remove(t.data, t.right);}else{modCount++ ;BinaryNode<T> oneChild;oneChild = (t.left == null)?t.left:t.right;oneChild.parent = t.parent;t = oneChild;}return t;}public BinaryNode<T> insert(T x, BinaryNode<T> t, BinaryNode<T> parent){if(t == null){modCount++ ;//空樹return new BinaryNode(x, null, null, parent);}int compareResult = x.compareTo(t.data);if(compareResult < 0){//要插入的數小于節點值，插入到左子樹t.left = insert(x, t.left, t);}else if(compareResult > 0){//要插入的數小于節點值，插入到左子樹t.right = insert(x, t.right, t);}else{}return t;}public BinaryNode<T> findMin(BinaryNode<T> t){// TODO Auto-generated method stubif(t == null){try {throw new UnderflowException();} catch (UnderflowException e) {// TODO Auto-generated catch block e.printStackTrace();}}else if(t.left == null){return t;}return findMin(t.left);}public BinaryNode<T> findMax(BinaryNode<T> t){// TODO Auto-generated method stubif(t == null){try {throw new UnderflowException();} catch (UnderflowException e) {// TODO Auto-generated catch block e.printStackTrace();}}else if(t.right == null){return t;}return findMax(t.right);}public static void main(String[] args) {MyTreeSet<Integer> myTreeSet = new MyTreeSet<Integer>();myTreeSet.insert(24);myTreeSet.insert(23);myTreeSet.insert(16);myTreeSet.insert(20);myTreeSet.insert(28);myTreeSet.insert(29);System.out.println("最小值： "+ myTreeSet.findMin());System.out.println("最大值： "+ myTreeSet.findMax());Iterator iter = myTreeSet.iterator();while(iter.hasNext()){System.out.print(iter.next() + "、");}} } class UnderflowException extends Exception{} class CurrentModificationException extends Exception{} class NoSuchElementException extends Exception{}

?

轉載于:https://www.cnblogs.com/studyDetail/p/7155989.html

總結

以上是生活随笔為你收集整理的编写TreeSet类的实现程序，其中相关的迭代器使用二叉查找树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。