Teilbäume

[DevEye]

Ich soll für die UNI gucken, ob in einem Baum ein anderer Baum komplett vorhanden ist.
Hab mir paar Gedanken gemacht, aber komme nicht wirklich auf eine Lösung! istTEilbaum soll den wiedergabewert Knoten liefern in dem der Knoten steht an dem der Baum anfängt...

Hier mein Code (es geht bestimmt super einfach und ich habe zuviel nachgedacht ):

/////       PROGRAMM BAUM                  /////
////--------------------------------------/////
public class b4kg
{
	 /////          KLASSSE MAIN          /////
	/////--------------------------------/////
	public static void main (String [] egal)
	{
		//erstelle Baum 1
		Knoten b1_k1 = new Knoten(2);
		Knoten b1_k2 =new Knoten(507,new Knoten(11),new Knoten(-103));
		Knoten b1_wurzel = new Knoten (-3, b1_k1, b1_k2);
		Baum b1 = new Baum (b1_wurzel);
		
		//erstelle Baum 2
		Knoten b2_k1 = new Knoten(15, new Knoten(23), new Knoten(80));
		Knoten b2_k2 = new Knoten(11, new Knoten(5), new Knoten(3));
		Knoten b2_k3 = new Knoten(507, b2_k2, new Knoten(-103));
		Knoten b2_k4 = new Knoten(-3, new Knoten(2), b2_k3);
		Knoten b2_k5 = new Knoten(93, b2_k4, new Knoten (-2));
		Knoten b2_wurzel = new Knoten (-3, b2_k1, b2_k5);
		Baum b2 = new Baum(b2_wurzel);	
		
		//Kontrolliere, ob es ein Teilbaum ist
		Knoten pos = b2.istTeilbaum(b1);
		
		//Ausgabe der Stelle bzw. Null
		if (pos != null)
		{
			System.out.println("\nAm Knoten mit der Zahl: "+pos.Zahl);
		}
		else
		{
			System.out.println("null");
		}
	}
}


 /////           Klasse Baum           /////
/////---------------------------------/////
class Baum
{
	Knoten Wurzel;
	
	Baum (){Wurzel = null;}
	Baum (Knoten Wurzel) {this.Wurzel = Wurzel;}
	
	int eInB()
	{
		return eInB(0, Wurzel);
	}
	
	int eInB(int x, Knoten k)
	{
		if (k != null)
		{
			x++;
			x = eInB(x, k.links);
			x = eInB(x, k.rechts);
		}
		return x;
	}
	
	
	// METHODE TEILBAUM //
	//------------------//
	Knoten istTeilbaum(Baum uBaum)
	{
		Knoten uK = uBaum.Wurzel; int equal = 0; Knoten pos = null;
		return istTeilbaum(uBaum, uBaum.eInB(), equal, Wurzel, uK, pos);
	}
	
	 // METHODEN "Konstruktor"//
	//-----------------------//
	Knoten istTeilbaum(Baum uBaum, int x, int equal, Knoten k, Knoten uK, Knoten pos)
	{			
		if (uK != null && k != null)
		{
			if (uK.Zahl != k.Zahl)
			{
				pos = null;
				System.out.println("X1 Es muessen noch: "+(x)+" Richtige da sein!");
				System.out.println("---------------------------------------------");
				if (k.links != null)
				{
					pos = istTeilbaum(uBaum, x, 0, k.links, uBaum.Wurzel, pos);
				}	
				if (k.rechts != null)
				{
					pos = istTeilbaum(uBaum, x, 0, k.rechts, uBaum.Wurzel, pos);
				}
				return pos;
			}
			else
			{
				equal++;
				
				if (equal == 1)
				{
					pos = k;	
				}
				System.out.println("X2 Es muessen noch: "+(x-equal)+" Richtige da sein!");
				if (k.links != null)
				{
					pos = istTeilbaum(uBaum, x, equal, k.links, uK.links, pos);
				}
				if (k.rechts != null)
				{ 
					pos = istTeilbaum(uBaum, x, equal+1, k.rechts, uK.rechts, pos);
				}
				return pos;
			}
		}
		return pos;
	}
}

 /////        Klasse Knoten         /////
/////------------------------------/////
class Knoten
{
	int Zahl; Knoten links, rechts;
	
	Knoten (int Zahl){this.Zahl = Zahl; links = rechts = null;}
	Knoten (int Zahl, Knoten links, Knoten rechts)
	{
		this.Zahl = Zahl; this.links = links; this.rechts = rechts;
	}
}

Achja, der zählt auch durch, doch am Ende sagt er wieder, dass noch X Knoten gebraucht werden...

 

[Thomas Darimont]

Hallo!

Schau doch mal hier:

/**
  * 
  */
 package de.tutorials;
 
 import java.util.Stack;
 
 /**
  * @author Tom
  * 
  */
 public class TreeExample {
 
 	/**
 	 * @param args
 	 */
 	public static void main(String[] args) {
 		Node root = new Node("root");
 		root.leftChild = new Node("L");
 		root.rightChild = new Node("R");
 		root.leftChild.leftChild = new Node("L_L");
 		root.leftChild.rightChild = new Node("L_R");
 		root.leftChild.rightChild.leftChild = new Node("L_R_L");
 		root.leftChild.rightChild.rightChild = new Node("L_R_R");
 
 		Node subTreeRoot = new Node("L_R");
 		subTreeRoot.leftChild = new Node("L_R_L");
 		subTreeRoot.rightChild = new Node("L_R_R");
 		// partTreeRoot.rightChild.leftChild = new Node("L_R_R_L");
 
 		System.out.println(root.hasSubTree(subTreeRoot));
 		System.out.println(subTreeRoot.equals(root.leftChild.rightChild));
 	}
 
 	static class Node {
 		String data;
 		Node leftChild;
 		Node rightChild;
 
 		public Node(String data) {
 			this.data = data;
 		}
 
 		boolean hasSubTree(Node subTreeRoot) {
 			Node matchingRootItem = searchMatchingRootItemFor(subTreeRoot);
 			return matchingRootItem != null
 		    		&& matchingRootItem.equals(subTreeRoot);
 		}
 
 		private Node searchMatchingRootItemFor(Node subTreeRoot) {
 			Stack stack = new Stack();
 			stack.push(this);
 			Node matchingRootItem = null;
 			while (!stack.isEmpty()) {
 				Node currentNode = (Node) stack.pop();
 				if (currentNode.data.equals(subTreeRoot.data)) {
 					matchingRootItem = currentNode;
 					break;
 				}
 				if (currentNode.rightChild != null) {
 		    	    stack.push(currentNode.rightChild);
 				}
 				if (currentNode.leftChild != null) {
 		    		stack.push(currentNode.leftChild);
 				}
 			}
 			stack.clear();
 			return matchingRootItem;
 		}
 
 		public boolean equals(Object o) {
 			if (!(o instanceof Node)) {
 				return false;
 			}
 
 			if (o == null) {
 				return false;
 			}
 
 			Node otherNode = (Node) o;
 
 			boolean isDataEqual = this.data.equals(otherNode.data);
 			boolean isLeftBranchEqual = false;
 			boolean isRightBranchEqual = false;
 
 			if (this.leftChild != null) {
 		    	isLeftBranchEqual = this.leftChild.equals(otherNode.leftChild);
 			} else {
 				isLeftBranchEqual = otherNode.leftChild == null;
 			}
 
 			if (this.rightChild != null) {
 				isRightBranchEqual = this.rightChild
 		    		    .equals(otherNode.rightChild);
 			} else {
 				isRightBranchEqual = otherNode.rightChild == null;
 			}
 
 			return isDataEqual && isLeftBranchEqual && isRightBranchEqual;
 		}
 
 		public int hashCode() {
 			return this.data.hashCode()
 					+ 37
 		    		* (leftChild != null ? leftChild.hashCode() : -"NULL"
 		    		    	.hashCode())
 					+ 37
 		    		* (rightChild != null ? rightChild.hashCode() : "NULL"
 		    		    	.hashCode());
 		}
 
 		public String toString() {
 			return this.data;
 		}
 	}
 }

... ich bin mir nur nicht sicher ob meine equals/hashCode Implementierung die dafür geforderten Eigenschaften (reflexiv, transitiv, symetrisch,konsistent) besitzt, aber vielleicht ists ein kleiner Denkanstoß ;-)

Gruss Tom

 

[DevEye]

thx, hat mir geholfen!