Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.TreeMap;
- public class Quiz_4<K extends Comparable<K>, V> {
- private class Node {
- private K key;
- private V data;
- private Node left, right;
- public Node(K key, V data) {
- this.key = key;
- this.data = data;
- }
- }
- private Node root;
- public Quiz_4() {
- root = null;
- }
- public void add(K key, V data) {
- root = addAux(key, data, root);
- }
- public Node addAux(K key, V data, Node tree) {
- if (tree == null) {
- return new Node(key, data);
- }
- if (key.compareTo(tree.key) == 0) {
- tree.data = data;
- return tree;
- }
- if (key.compareTo(root.key) < 0) {
- tree.left = addAux(key, data, tree.left);
- return tree;
- }
- tree.right = addAux(key, data, tree.right);
- return tree;
- }
- public int size() {
- return sizeAux(root);
- }
- public int sizeAux(Node tree) {
- return tree == null ? 0 : 1 + sizeAux(tree.right) + sizeAux(tree.left);
- }
- public V maxNonRec() {
- if (root == null) {
- return null;
- }
- Node n = root;
- while (n.right != null) {
- n = n.right;
- }
- return n.data;
- }
- public V max() {
- return root == null ? null : maxAux(root);
- }
- public V maxAux(Node tree) {
- return tree.right == null ? tree.data : maxAux(tree.right);
- }
- public V min() {
- return root == null ? null : minAux(root);
- }
- public V minAux(Node tree) {
- return tree.left == null ? tree.data : minAux(tree.left);
- }
- public String postOrderTraversal() {
- return postAux(root);
- }
- public String postAux(Node tree) {
- return tree == null ? "" : postAux(tree.left) + postAux(tree.right) + tree.key;
- }
- public int getNumInteriorNodes() {
- return interiorAux(root);
- }
- public int interiorAux(Node tree) {
- if(tree == null) {
- return 0;
- }
- return tree.right == null && tree.left == null ? 0 : 1 + interiorAux(tree.right) + interiorAux(tree.left);
- }
- public int getHeight() {
- return heightAux(root);
- }
- public int heightAux(Node tree) {
- return tree == null ? 0 : 1 + Math.max(heightAux(tree.left), heightAux(tree.right));
- }
- public void leaves(ArrayList<K> L) {
- L = leavesAux(root, L);
- }
- public ArrayList<K> leavesAux(Node tree, ArrayList<K> list) {
- if(tree == null) {
- return list;
- }
- if (tree.left == null && tree.right == null) {
- list.add(tree.key);
- return list;
- }
- list = leavesAux(tree.left, list);
- list = leavesAux(tree.right, list);
- return list;
- }
- public ArrayList<V> getDecreasingOrderList() {
- ArrayList<V> list = new ArrayList<V>();
- return decreasingListAux(root, list);
- }
- public ArrayList<V> decreasingListAux(Node tree, ArrayList<V> list) {
- if (tree == null) {
- return list;
- }
- list = decreasingListAux(tree.right, list);
- list.add(tree.data);
- list = decreasingListAux(tree.left, list);
- return list;
- }
- public void getDataOneChildNodes(ArrayList<V> L) {
- L = oneChildPolicy(root, L);
- }
- public ArrayList<V> oneChildPolicy(Node tree, ArrayList<V> L) {
- if (tree != null) {
- if (tree.left == null ^ tree.right == null) {
- L.add(tree.data);
- }
- L = oneChildPolicy(tree.left, L);
- L = oneChildPolicy(tree.right, L);
- }
- return L;
- }
- public ArrayList<K> getKeyNodesAtLevel(int targetLevel) {
- ArrayList<K> list = new ArrayList<K>();
- return nodesAtLevelAux(targetLevel, root, list);
- }
- public ArrayList<K> nodesAtLevelAux(int level, Node tree, ArrayList<K> list) {
- if (tree == null) {
- return list;
- }
- if(level == 1) {
- list.add(tree.key);
- return list;
- }
- list = nodesAtLevelAux(level-1, tree.right, list);
- list = nodesAtLevelAux(level-1, tree.left, list);
- return list;
- }
- public TreeMap<K,V> placeKeysValues() {
- TreeMap<K,V> map = new TreeMap<K,V>();
- return placeKeysValuesAux(root, map);
- }
- public TreeMap<K,V> placeKeysValuesAux(Node tree, TreeMap<K,V> map) {
- if(tree == null) {
- return map;
- }
- map = placeKeysValuesAux(tree.left, map);
- map.put(tree.key,tree.data);
- map = placeKeysValuesAux(tree.right, map);
- return map;
- }
- public static void main(String[] args) {
- Quiz_4<Integer, String> tree = new Quiz_4<Integer,String>();
- System.out.println("tree "+tree.postOrderTraversal());
- tree.add(1, "1");
- System.out.println("tree "+tree.postOrderTraversal());
- tree.add(2, "2");
- System.out.println("tree "+tree.postOrderTraversal());
- tree.add(3, "3");
- System.out.println("tree "+tree.postOrderTraversal());
- tree.add(4, "4");
- System.out.println("tree "+tree.postOrderTraversal());
- tree.add(10, "10");
- System.out.println("tree "+tree.postOrderTraversal());
- tree.add(0, "0");
- System.out.println("tree "+tree.postOrderTraversal());
- System.out.println(tree.size());
- ArrayList<Integer> list = new ArrayList<Integer>();
- tree.leaves(list);
- System.out.println(list);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement