本文主要是介绍《Java语言程序设计与数据结构》编程练习答案（第二十五章）（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
《Java语言程序设计与数据结构》编程练习答案（第二十五章）（二）
英文名：Introduction to Java Programming and Data Structures, Comprehensive Version, 11th Edition
25.7
//exercise 25.7public int getNumberOfNonLeaves(){return getNumberOfNonLeaves(root);}private int getNumberOfNonLeaves(TreeNode<T> root){if(root == null)return 0;return getNumberOfNonLeaves(root.right) + getNumberOfNonLeaves(root.left) + 1;}
25.8
//exercise 25.8private class DoubleIterator implements ListIterator<T>{private ArrayList<T> list = new ArrayList<>();private int current = 0;public DoubleIterator(){inorder();}private void inorder(){inorder(root);}private void inorder(TreeNode<T> root){if(root == null)return;inorder(root.left);list.add(root.element);inorder(root.right);}@Overridepublic boolean hasNext() {return current < list.size();}@Overridepublic T next() {return list.get(current++);}@Overridepublic boolean hasPrevious() {return current >= 0;}@Overridepublic T previous() {return list.get(current--);}@Overridepublic int nextIndex() {return current+1;}@Overridepublic int previousIndex() {return current-1;}@Overridepublic void remove() {BST.this.remove(list.get(current));}@Overridepublic void set(T t) {BST.this.delete(list.get(current));BST.this.insert(t);}@Overridepublic void add(T t) {BST.this.add(t);}}
25.9
//exercise 25.9@Overridepublic BST<T> clone(){BST<T> cloneTree = new BST<>();cloneTree.root = clone(this.root);cloneTree.size = this.size;return cloneTree;}private TreeNode<T> clone(TreeNode<T> root){if(root == null){return null;}TreeNode<T> cloneRoot = new TreeNode<>(root.element);cloneRoot.left = clone(root.left);cloneRoot.right = clone(root.right);return cloneRoot;}@Overridepublic boolean equals(Object o){BST<T> treeToBeCompared = (BST<T>) o;if(this.size == treeToBeCompared.size){for(T t : treeToBeCompared){if(!this.search(t)){return false;}}return true;}else{return false;}}
25.10
//exercise 25.10Iterator<T> preorderIterator(){return new preorderIerator();}private class preorderIerator implements Iterator<T>{private ArrayList<T> list = new ArrayList<>();private int current = 0;public preorderIerator(){preorder();}private void preorder(){preorder(root);}private void preorder(TreeNode<T> root){if(root == null)return;list.add(root.element);preorder(root.left);preorder(root.right);}@Overridepublic boolean hasNext() {return current < list.size();}@Overridepublic T next() {return list.get(current++);}}
25.11
🐎
25.12
public class book {public static void main(String[] args) {Scanner input = new Scanner(System.in);BST<Integer> test = new BST<>();for(int i=0;i<20;i++){test.add((int)(100*Math.random()));}BST<Integer> cloneTest = test.clone();for(int i: test){System.out.print(i+" ");}System.out.print("\n");for(int i: cloneTest){System.out.print(i+" ");}System.out.println(test.equals(cloneTest));}
}interface Tree<T> extends Collection<T>{public boolean search(T e);public boolean insert(T e);public boolean delete(T e);public int getSize();public default void inorder(){}public default void postorder(){}public default void preorder(){}@Overridepublic default boolean isEmpty(){return size() == 0;}@Overridepublic default boolean contains(Object e){return search((T) e);}@Overridepublic default boolean add(T e){return insert(e);}@Overridepublic default boolean remove(Object e){return delete((T) e);}@Overridepublic default int size(){return getSize();}@Overridepublic default boolean containsAll(Collection<?> c){return false;}@Overridepublic default boolean addAll(Collection<? extends T> c){return false;}@Overridepublic default boolean removeAll(Collection<?> c){return false;}@Overridepublic default boolean retainAll(Collection<?> c){return false;}@Overridepublic default Object[] toArray(){return null;}@Overridepublic default <T> T[] toArray(T[] array){return null;}
}class BST<T extends Comparable<T>> implements Tree<T>{protected TreeNode<T> root;protected int size = 0;public BST(){}public BST(T[] objects){for(T o: objects){add(o);}}@Overridepublic boolean search(T e) {TreeNode<T> current = root;while (current != null){if(e.compareTo(current.element) < 0){current = current.left;}else if(e.compareTo(current.element) > 0){current = current.right;}else{return true;}}return false;}@Overridepublic boolean insert(T e) {if(root == null){root = createNewNode(e);}else{TreeNode<T> parent = null;TreeNode<T> current = root;while (current != null){if(e.compareTo(current.element) < 0){parent = current;current = current.left;}else if(e.compareTo(current.element) > 0){parent = current;current = current.right;}else{return false;}}if(e.compareTo(parent.element) < 0){parent.left = createNewNode(e);}else{parent.right = createNewNode(e);}}size++;return true;}protected TreeNode<T> createNewNode(T e){return new TreeNode<>(e);}@Overridepublic void inorder(){inorder(root);}protected void inorder(TreeNode<T> root){if(root == null){return;}inorder(root.left);System.out.print(root.element+" ");inorder(root.right);}@Overridepublic void postorder(){postorder(root);}protected void postorder(TreeNode<T> root){if(root == null){return;}postorder(root.left);postorder(root.right);System.out.print(root.element+" ");}@Overridepublic void preorder(){preorder(root);}protected void preorder(TreeNode<T> root){if(root == null){return;}System.out.print(root.element+" ");preorder(root.left);preorder(root.right);}@Overridepublic boolean delete(T e) {TreeNode<T> parent = null;TreeNode<T> current = root;while(current != null){if(e.compareTo(current.element) < 0){parent = current;current = current.left;}else if(e.compareTo(current.element) > 0){parent = current;current = current.right;}else{break;}}if(current == null){return false;}if(current.left == null){if(parent == null){root = current.right;}else{if(e.compareTo(parent.element) < 0){parent.left = current.right;}else{parent.right = current.right;}}}else{TreeNode<T> parentOfRightMost = current;TreeNode<T> rightMost = current.left;while(rightMost.right != null){parentOfRightMost = rightMost;rightMost = rightMost.right;}current.element = rightMost.element;if(parentOfRightMost.right == rightMost){parentOfRightMost.right = rightMost.left;}else{parentOfRightMost.left = rightMost.left;}}size--;return true;}@Overridepublic int getSize() {return size;}@Overridepublic Iterator<T> iterator() {return new InorderIterator();}private class InorderIterator implements Iterator<T>{private ArrayList<T> list = new ArrayList<>();private int current = 0;public InorderIterator(){inorder();}private void inorder(){inorder(root);}private void inorder(TreeNode<T> root){if(root == null)return;inorder(root.left);list.add(root.element);inorder(root.right);}@Overridepublic boolean hasNext(){return current < list.size();}@Overridepublic T next(){return list.get(current++);}}//exercise 25.10Iterator<T> preorderIterator(){return new preorderIerator();}private class preorderIerator implements Iterator<T>{private ArrayList<T> list = new ArrayList<>();private int current = 0;public preorderIerator(){preorder();}private void preorder(){preorder(root);}private void preorder(TreeNode<T> root){if(root == null)return;list.add(root.element);preorder(root.left);preorder(root.right);}@Overridepublic boolean hasNext() {return current < list.size();}@Overridepublic T next() {return list.get(current++);}}//exercise 25.8private class DoubleIterator implements ListIterator<T>{private ArrayList<T> list = new ArrayList<>();private int current = 0;public DoubleIterator(){inorder();}private void inorder(){inorder(root);}private void inorder(TreeNode<T> root){if(root == null)return;inorder(root.left);list.add(root.element);inorder(root.right);}@Overridepublic boolean hasNext() {return current < list.size();}@Overridepublic T next() {return list.get(current++);}@Overridepublic boolean hasPrevious() {return current >= 0;}@Overridepublic T previous() {return list.get(current--);}@Overridepublic int nextIndex() {return current+1;}@Overridepublic int previousIndex() {return current-1;}@Overridepublic void remove() {BST.this.remove(list.get(current));}@Overridepublic void set(T t) {BST.this.delete(list.get(current));BST.this.insert(t);}@Overridepublic void add(T t) {BST.this.add(t);}}@Overridepublic void clear() {root = null;size = 0;}public static class TreeNode<T>{protected T element;protected TreeNode<T> left;protected TreeNode<T> right;public TreeNode(T e){element = e;}}//exercise 25.1public void breadthFirstTraversal(){ArrayList<TreeNode<T>> list = new ArrayList<>();if(root == null)return;list.add(root);while(!list.isEmpty()){TreeNode<T> current = list.remove(0);System.out.print(current.element+" ");if(current.left != null)list.add(current.left);if(current.right != null)list.add(current.right);}}public int height(){return height(root);}private int height(TreeNode<T> root){if(root == null)return 0;else{if(height(root.left) > height(root.right)){return height(root.left) + 1;}else{return height(root.right) + 1;}}}//exercise 25.2public boolean isPerfectBST(){return size == (int)(Math.pow(2,height())-1);}//exercise 25.3public void inorderUsingStack(){inorderUsingStack(root);}private void inorderUsingStack(TreeNode<T> root){if(root == null)return;Stack<TreeNode<T>> stack = new Stack<>();TreeNode<T> current = root;while(current != null || !stack.isEmpty()){if(current != null){stack.push(current);current = current.left;}else{current = stack.pop();System.out.print(current.element+" ");current = current.right;}}}//exercise 25.4public void preorderUsingStack(){preorderUsingStack(root);}private void preorderUsingStack(TreeNode<T> root){if(root == null)return;Stack<TreeNode<T>> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode<T> current = stack.pop();System.out.print(current.element+" ");if(current.right != null){stack.push(current.right);}if(current.left != null){stack.push(current.left);}}}//exercise 25.5public void postorderUsingStack(){postorderUsingStack(root);}private void postorderUsingStack(TreeNode<T> root){if(root == null)return;Stack<TreeNode<T>> stack = new Stack<>();TreeNode<T> current = root;TreeNode<T> pre = null;while(current != null){stack.push(current);current = current.left;}while(!stack.empty()){current = stack.pop();if(current.right != null && current.right != pre){stack.push(current);current = current.right;while (current != null){stack.push(current);current = current.left;}}else{System.out.print(current.element+" ");pre = current;}}}//exercise 25.6public int getNumberOfLeaves(){return getNumberOfLeaves(root);}private int getNumberOfLeaves(TreeNode<T> root){if(root.left == null && root.right == null){return 1;}else if(root.left == null){return getNumberOfLeaves(root.right);}else if(root.right == null){return getNumberOfLeaves(root.left);}else{return getNumberOfLeaves(root.left) + getNumberOfLeaves(root.right);}}//exercise 25.7public int getNumberOfNonLeaves(){return getNumberOfNonLeaves(root);}private int getNumberOfNonLeaves(TreeNode<T> root){if(root == null)return 0;return getNumberOfNonLeaves(root.right) + getNumberOfNonLeaves(root.left) + 1;}//exercise 25.9@Overridepublic BST<T> clone(){BST<T> cloneTree = new BST<>();cloneTree.root = clone(this.root);cloneTree.size = this.size;return cloneTree;}private TreeNode<T> clone(TreeNode<T> root){if(root == null){return null;}TreeNode<T> cloneRoot = new TreeNode<>(root.element);cloneRoot.left = clone(root.left);cloneRoot.right = clone(root.right);return cloneRoot;}@Overridepublic boolean equals(Object o){BST<T> treeToBeCompared = (BST<T>) o;if(this.size == treeToBeCompared.size){for(T t : treeToBeCompared){if(!this.search(t)){return false;}}return true;}else{return false;}}
}
25.13
//exercise 25.13private ArrayList<T> inorderList = new ArrayList<>();private ArrayList<T> preorderList = new ArrayList<>();private ArrayList<T> postorderList = new ArrayList<>();public List<T> inorderList(){addInorderList(root);return inorderList;}private void addInorderList(TreeNode<T> root){if(root == null)return;addInorderList(root.left);inorderList.add(root.element);addInorderList(root.right);}public List<T> preorderList(){addPreorderList(root);return preorderList;}private void addPreorderList(TreeNode<T> root){if(root == null)return;preorderList.add(root.element);addPreorderList(root.left);addPreorderList(root.right);}public List<T> postorderList(){addPostorderList(root);return postorderList;}private void addPostorderList(TreeNode<T> root){if(root == null)return;addPostorderList(root.left);addPostorderList(root.right);postorderList.add(root.element);}
25.14
🐎
25.15
public class book {public static void main(String[] args) {Scanner input = new Scanner(System.in);ArrayList<Integer> integers = new ArrayList<>();BST<Integer> test = new BST<>();System.out.println("Enter 10 integers:");for(int i=0;i<10;i++){int tmp = input.nextInt();integers.add(tmp);test.add(tmp);}test.delete(integers.get(0));integers.remove(0);for(int i: integers){if(test.isLeaf(i)){System.out.println(Arrays.toString(test.getPath(i).toArray()));}}}
}interface Tree<T> extends Collection<T>{public boolean search(T e);public boolean insert(T e);public boolean delete(T e);public int getSize();public default void inorder(){}public default void postorder(){}public default void preorder(){}@Overridepublic default boolean isEmpty(){return size() == 0;}@Overridepublic default boolean contains(Object e){return search((T) e);}@Overridepublic default boolean add(T e){return insert(e);}@Overridepublic default boolean remove(Object e){return delete((T) e);}@Overridepublic default int size(){return getSize();}@Overridepublic default boolean containsAll(Collection<?> c){return false;}@Overridepublic default boolean addAll(Collection<? extends T> c){return false;}@Overridepublic default boolean removeAll(Collection<?> c){return false;}@Overridepublic default boolean retainAll(Collection<?> c){return false;}@Overridepublic default Object[] toArray(){return null;}@Overridepublic default <T> T[] toArray(T[] array){return null;}
}class BST<T extends Comparable<T>> implements Tree<T>{protected TreeNode<T> root;protected int size = 0;public BST(){}@Overridepublic boolean search(T e) {return false;}@Overridepublic boolean insert(T e) {if(root == null)root = createNewNode(e);else{TreeNode<T> parent = null;TreeNode<T> current = root;while(current != null)if(e.compareTo(current.element) < 0){parent = current;current = current.left;}else if(e.compareTo(current.element) > 0){parent = current;current = current.right;}elsereturn false;if(e.compareTo(parent.element) < 0){parent.left = createNewNode(e);(parent.left).parent = parent;}else{parent.right = createNewNode(e);(parent.right).parent = parent;}}size++;return true;}@Overridepublic boolean delete(T e) {TreeNode<T> parent = null;TreeNode<T> current = root;while(current != null){if(e.compareTo(current.element) < 0){parent = current;current = current.left;}else if(e.compareTo(current.element) > 0){parent = current;current = current.right;}elsebreak;}if(current == null)return false;if(current.left == null){if(parent == null){root = current.right;root.parent = null;}else{if(e.compareTo(parent.element) < 0){parent.left = current.right;if(parent.left != null) {(parent.left).parent = parent;}}else{parent.right = current.right;if(parent.right != null) {(parent.right).parent = parent;}}}}else{TreeNode<T> parentOfRightMost = current;TreeNode<T> rightMost = current.left;while(rightMost.right != null){parentOfRightMost = rightMost;rightMost = rightMost.right;}current.element = rightMost.element;if(parentOfRightMost.right == rightMost){parentOfRightMost.right = rightMost.left;if(parentOfRightMost.right != null) {(parentOfRightMost.right).parent = parentOfRightMost;}}else{parentOfRightMost.left = rightMost.left;if(parentOfRightMost.left != null) {(parentOfRightMost.left).parent = parentOfRightMost;}}}size--;return true;}private TreeNode<T> getNode(T element){return findNode(element, root);}private TreeNode<T> findNode(T element, TreeNode<T> root){if(root == null)return null;if(root.element.equals(element)){return root;}if(findNode(element, root.left) != null){return findNode(element, root.left);}if(findNode(element, root.right) != null){return findNode(element, root.right);}return null;}public boolean isLeaf(T element){TreeNode<T> current = getNode(element);if(current == null)return false;return current.left == null && current.right == null;}public ArrayList<T> getPath(T e){ArrayList<T> ret = new ArrayList<>();TreeNode<T> current = getNode(e);while (!current.element.equals(root.element)){ret.add(current.element);current = current.parent;}ret.add(root.element);return ret;}@Overridepublic int getSize() {return size;}@Overridepublic Iterator<T> iterator() {return null;}@Overridepublic void clear() {}protected TreeNode<T> createNewNode(T e){return new TreeNode<>(e);}public static class TreeNode<T>{protected T element;protected TreeNode<T> left;protected TreeNode<T> right;protected TreeNode<T> parent;public TreeNode(T e){this.element = e;}}
}
第二十五章 完
这篇关于《Java语言程序设计与数据结构》编程练习答案（第二十五章）（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
