Binärer Suchbaum - Size als Variabel in innerer Klasse speichern

[skuki]

Hallo,

ich habe einen Binären Suchbaum mit innerer Node Klasse.

Zuerst habe ich eine Methode im Suchbaum selbst geschrieben die mir die Anzahl der Nodes im Unterbaum darstellt.

	 public int size() {
		 if(root==null)
			 return 0;
		 
			 return findSize(this.root) -1;
	 }
	 
	 public int findSize(Node root){
		 if(root == null)
			 return 0;
		 
		 return findSize(root.leftChild) + findSize(root.rightChild) +1;
	 }

Ich greife öfters mit anderen Methoden auf diesen Wert zu, deshalb möchte ich ihn als Variabel für jede Node selbst abspeichern. Wie würdet ihr das machen? Müsste size ja beim Erstellen bzw. beim Insert der Node im Konstruktor angeben oder? Stehe da leider etwas am Schlauch ???:L


Klasse Tree sieht im Grundgerüst so aus:

public class Tree {
	Node root;
           
       public void insert(int key){
		Node newNode = new Node(key);
		
		if(root == null){
			root = newNode; 
		}else{
			Node focusNode = root;
			Node parent;
			
			while(true){
				parent = focusNode;
				
				if(key < focusNode.key){
					focusNode = focusNode.leftChild;
					
					if(focusNode == null){
						parent.leftChild = newNode;
						return;
					}
				} else{
					
					focusNode = focusNode.rightChild;
					
					if(focusNode == null){
						parent.rightChild = newNode;
						return;
					}
					
				}
				
			}
		}
	}
        
class Node{
		int size;
		int key; 
		Node leftChild;
		Node rightChild;
}
}

Vielen Dank!

 

[ARadauer]

evtl nach jeder veränderung vom baum ein findSize machen

public int findSize(Node root){
if(root == null){
size = 0;
return 0;
}

size= findSize(root.leftChild) + findSize(root.rightChild) +1;
return size;
}

und alternativ noch eine getSize anbieten
public int getSize(){
return size;
}

 

[CSHW89]

Warum als Variable in der Node-Klasse? Ich würde eine size-Variable in der Klasse Tree erstellen, und im Tree-Konstruktor auf 0 setzen. Dann bei jedem insert size um eins erhöhen, wenn wirklich ein Element eingefügt wird. Beim Löschen demendsprechend.

public class Tree {
	Node root;
        int size;
       
       public Tree() {
              root = null;
              size = 0;
       }
           
       public void insert(int key){
		Node newNode = new Node(key);
		
		if(root == null){
			root = newNode; 
                        size = 1;
		}else{
			Node focusNode = root;
			Node parent;
			
			while(true){
				parent = focusNode;
				
				if(key < focusNode.key){
					focusNode = focusNode.leftChild;
					
					if(focusNode == null){
						parent.leftChild = newNode;
                                                size++;
						return;
					}
				} else{
					
					focusNode = focusNode.rightChild;
					
					if(focusNode == null){
						parent.rightChild = newNode;
                                                size++;
						return;
					}
					
				}
				
			}
		}
	}

lg Kevin