学号 2018-2019-1 《程序设计与数据结构》实验二报告
学号 2018-2019-1 《程序设计与数据结构》实验二报告课程:《程序设计与数据结构》班级: 1723姓名: 康皓越学号:20172326实验教师:王志强实验日期:2018年11月10日必修/选修: 必修1.实验内容
2. 实验过程及结果实验一
LinkedBinarySearchTree<T> result = new LinkedBinarySearchTree<>(); result.root = root.getRight(); return result; contains方法为判断是否存在目标元素,通过结合find方法,find方法是返回一个boolean值,在此基础上,将找到的结点的元素值返回即可。部分关键代码如下: public boolean contains(T targetElement) { if(find(targetElement)!=null) return true; else return false; } public T find(T targetElement) throws ElementNotFoundException { BinaryTreeNode<T> current = findNode(targetElement,root); if (current == null) throw new ElementNotFoundException("LinkedBinaryTree"); return (current.getElement()); } private BinaryTreeNode<T> findNode(T targetElement,BinaryTreeNode<T> next) { if (next == null) return null; if (next.getElement().equals(targetElement)) return next; BinaryTreeNode<T> temp = findNode(targetElement,next.getLeft()); if (temp == null) temp = findNode(targetElement,next.getRight()); return temp; }
public Iterator<T> iteratorPostOrder() { ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>(); postOrder(root,tempList); return new TreeIterator(tempList.iterator()); } protected void postOrder(BinaryTreeNode<T> node,ArrayUnorderedList<T> tempList) { if (node !=null){ postOrder(node.getLeft(),tempList); postOrder(node.getRight(),tempList); tempList.addToRear(node.getElement()); } } 实验二 中序前序序列构造二叉树
public BinaryTreeNode initTree(String[] preorder,int s1,int e1,String[] inorder,int s2,int e2) {//s1是前序开始值,e1是结束值 if (s1 > e1 || s2 > e2) { return null; } String rootE = preorder[s1];//前序定根 BinaryTreeNode head = new BinaryTreeNode(rootE); int rootG = findRoot(inorder,rootE,s2,e2);//在中序中找到根的位置 BinaryTreeNode left = initTree(preorder,s1 + 1,s1 + rootG - s2,inorder,rootG - 1);//开始使用递归,通过根的索引值确定数组中各个子树的位置,将其分割 BinaryTreeNode right = initTree(preorder,s1 + rootG - s2 + 1,e1,rootG + 1,e2); head.setLeft(left); head.setRight(right); return head; } 实验三 自己设计并实现一颗决策树
public void evaluate() { LinkedBinaryTree<String> current = tree; Scanner scan = new Scanner(System.in); while (current.size() > 1) { System.out.println (current.getRootElement()); if (scan.nextLine().equalsIgnoreCase("N")) current = current.getRight(); else current = current.getLeft(); } System.out.println (current.getRootElement()); } 实验四 表达式树
if(isOp(temp)&&isHighOp(temp)){//有高级符号 BinaryTreeNode current = new BinaryTreeNode(temp); current.setLeft(numlist.remove(numlist.size()-1)); num2 = scan.nextToken(); current.setRight(new BinaryTreeNode(num2)); numlist.add(current); } 实验五 完成pp11.3
public T removeMin() throws EmptyCollectionException { T result = null; if (isEmpty()) throw new EmptyCollectionException("LinkedBinarySearchTree"); else { if (root.left == null) { result = root.element; root = root.right; } else { BinaryTreeNode<T> parent = root; BinaryTreeNode<T> current = root.left; while (current.left != null) { parent = current; current = current.left; } result = current.element; parent.left = current.right; } modCount--; } 红黑树分析TreeMapTreeMap 是一个有序的key-value集合,它是通过红黑树实现的。 // 根据已经一个排好序的map创建一个TreeMap // 将map中的元素逐个添加到TreeMap中,并返回map的中间元素作为根节点。 private final Entry<K,V> buildFromSorted(int level,int lo,int hi,int redLevel,Iterator it,java.io.ObjectInputStream str,V defaultVal) throws java.io.IOException,ClassNotFoundException { if (hi < lo) return null; // 获取中间元素 int mid = (lo + hi) / 2; Entry<K,V> left = null; // 若lo小于mid,则递归调用获取(middel的)左孩子。 if (lo < mid) left = buildFromSorted(level+1,lo,mid - 1,redLevel,it,str,defaultVal); // 获取middle节点对应的key和value K key; V value; if (it != null) { if (defaultVal==null) { Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next(); key = entry.getKey(); value = entry.getValue(); } else { key = (K)it.next(); value = defaultVal; } } else { // use stream key = (K) str.readObject(); value = (defaultVal != null ? defaultVal : (V) str.readObject()); } // 创建middle节点 Entry<K,V> middle = new Entry<K,V>(key,value,null); // 若当前节点的深度=红色节点的深度,则将节点着色为红色。 if (level == redLevel) middle.color = RED; // 设置middle为left的父亲,left为middle的左孩子 if (left != null) { middle.left = left; left.parent = middle; } if (mid < hi) { // 递归调用获取(middel的)右孩子。 Entry<K,V> right = buildFromSorted(level+1,mid+1,hi,defaultVal); // 设置middle为left的父亲,left为middle的左孩子 middle.right = right; right.parent = middle; } return middle; }
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash,table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } private V getForNullKey() { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }
3. 实验过程中遇到的问题和解决过程
public void postfix(){ LinkedBinaryTree lbt = new LinkedBinaryTree(); lbt.root = btnode2; Iterator it = lbt.iteratorPostOrder(); while(it.hasNext()) System.out.print(it.next().toString()+" "); } 问题代码,现在每次都将其实例化,但是却并没有得到存储,随着这个方法的每一次调用,都产生了一个新的树,导致出现了空。 其他(感悟、思考等)
参考资料
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |