文章目录

说明

《数据结构与算法分析-java语言描述》
– 练习4.13

编写TreeSet类的实现程序，其中相关的迭代器使用二叉树查找树。
<mark>在每个节点上添加通向下一个最小节点和下一个最大节点的链。</mark>
为使所编程序更简单，<mark>添加头节点和尾节点</mark>，它们不属于二叉树的一部分，但有助于使得程序的链表部分更简单。

理解

其实就是在每个树节点上添加双向链表信息。
树种记录收尾节点

（我的）代码

package cn.edut.tree;

import java.util.Iterator;

import org.junit.Test;

public class MyTreeSet3 <T extends Comparable<? super T> > {
	
	
	
	private BinaryNode<T> root ; 
	private BinaryNode<T> first ; 
	private BinaryNode<T> last ;
	private int size; 
	private int modCount ; 
		
	
	
	public void insert(T e ) {
		root = insert(e,root , null  , null);
	}
	public void print() {
		System.out.print("[ ");
		BinaryNode<T> next = first ; 
		for(int index=0 ; index<size ; index++) {
			System.out.print(next.elementData);
			if(index<size-1) {
				System.out.print(", ");
			}
			next = next.next ;
		}
		System.out.println("]");
	}
	
	public Iterator<T> iterator() {
		return new Itr() ; 
	}
	
	public void listAll() {
		listAll_mid(root , 0);
	}
	
	public void remove(T e) {
		root = remove(e, root ,null , null);
	}
	
	public int size() {
		return size ; 
	}
	public boolean isEmpty() {
		return size == 0 ; 
	}
	

	
	
	private BinaryNode<T> remove(T e , BinaryNode<T> currentNode , 
			BinaryNode<T> prevNode , BinaryNode<T> nextNode){
		if(currentNode == null) {
			return null; 
		}
		int flag = e.compareTo(currentNode.elementData);
		if(flag<0) {
			currentNode.left = remove(e, currentNode.left , currentNode.prev , currentNode);
		}else if(flag>0) {
			currentNode.right = remove(e, currentNode.right, currentNode, currentNode.next);
		}else {//找到 相同的，进行删除
			if(currentNode.left!=null&&currentNode.right!=null) {
				BinaryNode<T> minNode = finMax(currentNode.right) ; 
				currentNode.elementData = minNode.elementData ; 
				currentNode.right = remove(minNode.elementData,currentNode.right , 
						currentNode , currentNode.next);
			}else {
				if(prevNode!=null) {
					prevNode.next = nextNode;
				}
				if(nextNode!=null) {
					nextNode.prev = currentNode.prev ;
				}
				currentNode.next=null;
				currentNode.prev=null;
				
				currentNode = currentNode.left!=null?currentNode.left:currentNode.right;
				modCount++;
				size--;
			}
			
		}
		return currentNode ; 
	}
	private void listAll_mid(BinaryNode<T> currentNode , int depth) {
		if(currentNode.right!=null) {
			listAll_mid(currentNode.right , depth+1);
		}
		System.out.print("[");
		for(int i=0 ; i<depth ; i++)
		{
			System.out.print("~~~ ");
		}
		System.out.println(currentNode.elementData+" : ");
		if(currentNode.left!=null) {
			listAll_mid(currentNode.left , depth+1);
		}
	}

	private BinaryNode<T> finMax(BinaryNode<T> currentNode){
		return last ; 
	}
	private BinaryNode<T> finMin(BinaryNode<T> currentNode){
		return first ; 
	}
	
	/** * 添加， * 空时候，添加节点 * @param e */
	private BinaryNode<T> insert(T e , BinaryNode<T> currentNode ,BinaryNode<T> prevNode , BinaryNode<T> nextNode){
		//空
		if(currentNode==null) {
			currentNode = new BinaryNode<T>(e,null,null,prevNode,nextNode);
			//链表的头
			if(prevNode!=null){
				prevNode.next = currentNode ; 
			}else {
				first = currentNode ; 
			}
			if(nextNode!=null) {
				nextNode.prev = currentNode; 
			}else {
				last = currentNode; 
			}
			//添加成功
			modCount++;
			size++;
		}else {
			int flag = e.compareTo(currentNode.elementData);
			if(flag<0) {
				currentNode.left = insert(e, currentNode.left, currentNode.prev , currentNode);
				
			}else if(flag>0) {
				currentNode.right = insert(e, currentNode.right,currentNode , currentNode.next);
			}else {
				
			}
		}
		
		
		return currentNode ; 
	} 
	
	private class Itr implements Iterator<T>{
		private BinaryNode<T> prevNode; 
		private BinaryNode<T> currentNode ; 
		private int expectModCount ; 
		private boolean isOkRemove ;
		
		public  Itr() {
			expectModCount = modCount;
			currentNode = first;
			isOkRemove = false; 
		}
		

		@Override
		public boolean hasNext() {
			return currentNode!=null ; 
		}

		@Override
		public T next() {
			isLegal();
			prevNode = currentNode ; 
			currentNode = currentNode.next; 
			isOkRemove = true; 
			return prevNode.elementData ;
		}
		
		@Override
		public void remove() {
			isLegal();
			if(!isOkRemove) {
				throw new RuntimeException();
			}
			MyTreeSet3.this.remove(prevNode.elementData);
			expectModCount++;
			isOkRemove=false; 
		}
		
		public void isLegal() {
			if(expectModCount!=modCount) {
				throw new RuntimeException(); 
			}
		}
		
	}
	
	private static class BinaryNode<T> {
		
		private T elementData ; 
		private BinaryNode<T> left ; 
		private BinaryNode<T> right; 
		private BinaryNode<T> next ; 
		private BinaryNode<T> prev ; 
		public BinaryNode(T e, BinaryNode<T> l , BinaryNode<T> r , BinaryNode<T> prev,  BinaryNode<T> n  ) {
			elementData= e; 
			left = l ; 
			right = r ; 
			this.prev = prev; 
			next = n ;
		}
	}
}

测试代码

@Test
	public void Test0002() {
		/* * size * print */
		MyTreeSet3<Integer> mt3 = new MyTreeSet3<>();
		System.out.println("size="+mt3.size());
		System.out.print("print:");mt3.print();
		/* * insert */
		mt3.insert(3);
		mt3.insert(-1);
		mt3.insert(2);
		mt3.insert(10);
		mt3.insert(5);
		mt3.insert(6);
		mt3.insert(4);
		/* * 打印 * listAll * print */
		System.out.println("添加：");
		mt3.listAll();
		System.out.print("print:");mt3.print();
		/* * remove * listAll * print * */
		System.out.println("删除：");
		mt3.remove(3);
		mt3.listAll();
		System.out.print("print:");mt3.print();
		/* * Iterator */
		System.out.println("Iterator测试：");
		Iterator<Integer> it = mt3.iterator() ; 
		while(it.hasNext()) {
			System.out.println(it.next());
			it.remove(); 
		}
		System.out.println("size:"+mt3.size);
		System.out.println("测试成功，完结撒花！");
	}

测试结果

size=0
print:[ ]
添加：
[~~~ 10 :
[~~~ ~~~ ~~~ 6 :
[~~~ ~~~ 5 :
[~~~ ~~~ ~~~ 4 :
[3 :
[~~~ ~~~ 2 :
[~~~ -1 :
print:[ -1, 2, 3, 4, 5, 6, 10]
删除：
[~~~ ~~~ 6 :
[~~~ 5 :
[~~~ ~~~ 4 :
[10 :
[~~~ ~~~ 2 :
[~~~ -1 :
print:[ -1, 2, 10, 4, 5, 6]
Iterator测试：
-1
2
10
4
5
6
10
size:0
测试成功，完结撒花！

书的答案

package cn.edut.tree;

import java.util.*;

//This solution does not use header and tail nodes.
class UnderflowException extends Exception {
};

public class MyTreeSet4<AnyType extends Comparable<? super AnyType>> {
	private static class BinaryNode<AnyType> {
		BinaryNode(AnyType theElement) {
			this(theElement, null, null, null, null);
		}

		BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt, BinaryNode<AnyType> nt,
				BinaryNode<AnyType> pv) {
			element = theElement;
			left = lt;
			right = rt;
			next = nt;
			prev = pv;
		}

		AnyType element;
		BinaryNode<AnyType> left;
		BinaryNode<AnyType> right;
		BinaryNode<AnyType> next;
		BinaryNode<AnyType> prev;
	}

	public java.util.Iterator<AnyType> iterator() {
		return new MyTreeSet4Iterator();
	}

	private class MyTreeSet4Iterator implements java.util.Iterator<AnyType> {
		private BinaryNode<AnyType> current = findMin(root);
		private BinaryNode<AnyType> previous;
		private int expectedModCount = modCount;
		private boolean okToRemove = false;
		private boolean atEnd = false;

		public boolean hasNext() {
			return !atEnd;
		}

		public AnyType next() {
			if (modCount != expectedModCount)
				throw new java.util.ConcurrentModificationException();
			if (!hasNext())
				throw new java.util.NoSuchElementException();
			AnyType nextItem = current.element;
			previous = current;
			current = current.next;
			if (current == null)
				atEnd = true;
			okToRemove = true;
			return nextItem;
		}

		public void remove() {
			if (modCount != expectedModCount)
				throw new java.util.ConcurrentModificationException();
			if (!okToRemove)
				throw new IllegalStateException();
			MyTreeSet4.this.remove(previous.element);
			okToRemove = false;
		}
	}

	public MyTreeSet4() {
		root = null;
	}

	public void makeEmpty() {
		modCount++;
		root = null;
	}

	public boolean isEmpty() {
		return root == null;
	}

	public boolean contains(AnyType x) {
		return contains(x, root);
	}

	public AnyType findMin() throws UnderflowException {
		if (isEmpty())
			throw new UnderflowException();
		else
			return findMin(root).element;
	}

	public AnyType findMax() throws UnderflowException {
		if (isEmpty())
			throw new UnderflowException();
		else
			return findMax(root).element;
	}

	public void insert(AnyType x) {
		root = insert(x, root, null, null);
	}

	public void remove(AnyType x) {
		root = remove(x, root);
	}

	public void printTree() {
		if (isEmpty())
			System.out.println("Empty tree");
		else
			printTree(root);
	}

	private void printTree(BinaryNode<AnyType> t) {
		if (t != null) {
			printTree(t.left);
			System.out.println(t.element);
			printTree(t.right);
		}
	}

	private boolean contains(AnyType x, BinaryNode<AnyType> t) {
		if (t == null)
			return false;
		int compareResult = x.compareTo(t.element);
		if (compareResult < 0)
			return contains(x, t.left);
		else if (compareResult > 0)
			return contains(x, t.right);
		else
			return true; // match
	}

	private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
		if (t == null)
			return null;
		else if (t.left == null)
			return t;
		return findMin(t.left);
	}

	private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
		if (t == null)
			return null;
		else if (t.right == null)
			return t;
		return findMax(t.right);
	}

	private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t, BinaryNode<AnyType> nt,
			BinaryNode<AnyType> pv) {
		if (t == null) {
			modCount++;
			BinaryNode<AnyType> newNode = new BinaryNode<AnyType>(x, null, null, nt, pv);
			if (nt != null) {
				nt.prev = newNode;
			}
			if (pv != null) {
				pv.next = newNode;
			}
			return newNode;
		}
		int compareResult = x.compareTo(t.element);
		if (compareResult < 0)
			t.left = insert(x, t.left, t, pv);
		else if (compareResult > 0) {
			t.right = insert(x, t.right, nt, t);
		} else
			; // duplicate
		return t;
	}

	private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
		if (t == null)
			return t; // not found
		int compareResult = x.compareTo(t.element);
		if (compareResult < 0)
			t.left = remove(x, t.left);
		else if (compareResult > 0)
			t.right = remove(x, t.right);
		else if (t.left != null && t.right != null) // two children
		{
			t.element = findMin(t.right).element;
			t.right = remove(t.element, t.right);
		} else {
			modCount++;
			t.prev.next = t.next; // update next and prev links
			t.next.prev = t.prev;
			t = (t.left != null) ? t.left : t.right;
		}
		return t;
	}

	private BinaryNode<AnyType> root;
	int modCount = 0;

}