Subato 562/BinTreeCompleteness

Resource Files

exercise1289.zip
.BinTreeCompleteness.java
Solution Template
BinTreeCompletenessTest.java

BinTreeCompleteness

Vollständigkeitsprüfung für Bäume

Ergänzen Sie die Klasse BinTree um eine Methode isCompleteOrAlmostComplete(). Diese soll genau dann true zurückliefern wenn der Baum vollständig oder fast vollständig ist.

Hinweise:

Um zu entscheiden ob ein Baum vollständig/fast vollständig ist, macht es Sinn die Vollständigkeit und die Höhe seiner beiden Teilbäume zu betrachten.
Es hilft, zunächst auf Papier Fälle zu skizzieren, in denen Vollständigkeit bzw. Fast-Vollständigkeit vorliegt.

Fold all Unfold all Fullscreen Settings Help

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package de.hsrm.ads;
public class BinTreeCompleteness {
  Node root;
  static class Node {
    Node left;
    Node right;
    int value;
    Node(int value) {
      this.value = value;
    }
    Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
    
  } 
    
  
  public BinTreeCompleteness() {
    root = null;
  }
  public BinTreeCompleteness(Node root) {
    this.root = root;
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

java

package de.hsrm.ads;

public class BinTreeCompleteness {

Node root;

static class Node {

Node left;
		Node right;
		int value;

Node(int value) {
			this.value = value;
		}

Node(int value, Node left, Node right) {
			this.value = value;
			this.left = left;
			this.right = right;
		}
		
	}	
		
	
	public BinTreeCompleteness() {
		root = null;
	}

public BinTreeCompleteness(Node root) {
		this.root = root;
	}

public int height() {
		// FIXME
	}
	
	public boolean isCompleteOrAlmostComplete() {
		// FIXME
	}
		
	public static void main(String[] args) {
		/*
		 *  an incomplete sample tree
		 * (not fully complete, not almost complete)
		 * 
		 * 1
		 * |_ 2
		 *    |_ 4
		 *    |_ 5
		 *       |_ 7
		 *       |_
		 *    
		 * |_ 3
		 *    |_
		 *    |_ 6
		*/
		BinTreeCompleteness.Node n7 = new BinTreeCompleteness.Node(7);
		BinTreeCompleteness.Node n6 = new BinTreeCompleteness.Node(6);
		BinTreeCompleteness.Node n5 = new BinTreeCompleteness.Node(5, n7, null);
		BinTreeCompleteness.Node n4 = new BinTreeCompleteness.Node(4);
		BinTreeCompleteness.Node n3 = new BinTreeCompleteness.Node(3, null, n6);
		BinTreeCompleteness.Node n2 = new BinTreeCompleteness.Node(2, n4, n5);
		BinTreeCompleteness.Node n1 = new BinTreeCompleteness.Node(1, n2, n3);		
		BinTreeCompleteness tree = new BinTreeCompleteness(n1);
		// should be false!
		System.out.println(tree.isCompleteOrAlmostComplete());
	}

}

You are not logged in and therefore you cannot submit a solution.