[C#] problema alberi

[ideafissa]

Ciao ragazzi, volevo chiedervi se potreste aiutarmi, devo fare un progettino in Visual Studio 2010 che implementa in modo semplice in C# i due problemini qui sotto. Va bene un progetto console UI.

Allora, supponiamo di avere una struttura ad albero (per esempio un albero genealogico), mi servrebbe una routine che conta i nodi. Inoltre mi servirebbe anche una routine che elenca i nodi livello per livello per esempio: tutti i bisnonni, tutti i nonni, tutti i genitori e tutta la generazione corrente.

Mi dareste una mano? grazi

[nikel]

non so se si possano fare in c#

ma io direi.... liste!

una volta che hai definito il tuo "tipo"

per contare i nodi / i nodi allo stesso livello

ti basta contare i puntatori diversi da null ;)

[ideafissa]

ops doppio post...

[ideafissa]

Ho buttato giù questo codice... ditemi cosa ne pensate e dove sono gli eventuali errori... Grazie!!!

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication7
{
class Program
{
public struct TreeNode
{
int item; // The data in this node.
public TreeNode* left; // Pointer to the left subtree.
public TreeNode* right; // Pointer to the right subtree.
}

unsafe int countNodes(TreeNode* root)
{
// Count the nodes in the binary tree to which
// root points, and return the answer.
if (root == null)
return 0; // The tree is empty. It contains no nodes.
else
{
int count = 1; // Start by counting the root.
count += countNodes(root->left); // Add the number of nodes in the left subtree.
count += countNodes(root->right); // Add the number of nodes in the right subtree.
return count; // Return the total.
}
}
int Max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
unsafe int TreeDeep(TreeNode* root)
{
int l, r;

if (root == null)
{
return 0; // Tree is empty => TreeDeep = 0
}
else
{
l = TreeDeep(root->left); // Calculation of depth of left subtree
r = TreeDeep(root->right); // Calculate of depth of right subtree
return (Max(l, r)+1); // Tree's overall depth is > 1
}
}

unsafe int contNodeSameLevel(TreeNode* root, int h)
{

if (root == null)
{
return 0;
}
if (h == 0)
{
return 1;
}
else
{
return contNodeSameLevel(root->left, h - 1) + contNodeSameLevel(root->right, h - 1);
}
}

static void Main(string[] args)
{
}
}
}

[WarDuck]

Ti dico solo una cosa, non c'è alcun bisogno di usare unsafe, né i puntatori.

Se non sbaglio puoi creare la struttura nell'heap e usare i riferimenti ad essa, usando il costrutto new, tipo:

var root = new TreeNode();

[ideafissa]

Ti dico solo una cosa, non c'è alcun bisogno di usare unsafe, né i puntatori.

Se non sbaglio puoi creare la struttura nell'heap e usare i riferimenti ad essa, usando il costrutto new, tipo:

var root = new TreeNode();

Spiegami meglio questa cosa, sono nuovo di c#...

[WarDuck]

Spiegami meglio questa cosa, sono nuovo di c#...

Gli oggetti in C# si gestiscono tramite riferimenti ad essi.

Ad esempio:


class Person {
string nome;
string cognome;
}

f(Person p) {
p.nome = "A";
p.cognome = "B";
}

main() {
Person p = new Person(); // p è un riferimento all'oggetto Person creato nell'heap

f(p); // si passa il riferimento p

// p.nome varrà "A"
// p.cognome varrà "B"
}


La struct è un oggetto più leggero... EDIT

http://msdn.microsoft.com/en-us/library/aa288471%28VS.71%29.aspx

A quanto leggo viene sempre allocato nello stack e il suo passaggio avviene sempre per valore (quindi quando la passi ad un metodo viene fatta una copia, le modifiche si riflettono solo all'interno del metodo).

Cmq per il tuo scopo forse è il caso di usare una classe.

[ideafissa]

grazie, mi metto subito all'opera!

[ideafissa]

Ho prodotto questo codice:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication7
{

class TreeNode// Un albero binario che memorizza un elemento ed è collegato ad altri tre nodi, 2 figli e un genitore
{
private int value;
private TreeNode leftChild;
private TreeNode rightChild;
private TreeNode parent;
private BinaryTree tree;

public virtual int Value
{
get { return value; }
set { this.value = value; }
}

public virtual TreeNode LeftChild //Recupera o setta il valore del nodo sinistro
{
get { return leftChild; }
set { leftChild = value; }
}

public virtual TreeNode RightChild //Recupera o setta il valore del nodo destro
{
get { return rightChild; }
set { rightChild = value; }
}


public virtual TreeNode Parent //Recupera o setta il valore del nodo genitore
{
get { return parent; }
set { parent = value; }
}

/// <summary>
/// Gets or sets the Binary Tree the node belongs to
/// </summary>
public virtual BinaryTree Tree
{
get { return tree; }
set { tree = value; }
}

public TreeNode(int value) // Istanzia un nuovo nodo
{
this.value = value;
}
}

class BinaryTree //Struttura dati
{
private TreeNode head;
private int size;

public virtual int Count //Restituisce il numero di elementi contenuti
{
get { return size; }
}

public BinaryTree() //Istanzia un nuovo albero
{
head = null;
size = 0;
}

public virtual void Add(TreeNode node) //Inserisce un nuovo nodo nell'albero
{
if (this.head == null)
{
this.head = node;
node.Tree = this;
size++;
}
else
{
if (node.Parent == null)
node.Parent = head;

if (node.Value < node.Parent.Value) //Se il valore del nodo é inferiore a quello del genitore inserisce il nuovo nodo a sinistra
{
if (node.Parent.LeftChild == null)
{
node.Parent.LeftChild = node;
size++;
node.Tree = this;
}
else
{
node.Parent = node.Parent.LeftChild;
this.Add(node);
}
}
else //Inserisce il nodo a destra
{
if (node.Parent.RightChild == null)
{
node.Parent.RightChild = node;
size++;
node.Tree = this;
}
else
{
node.Parent = node.Parent.RightChild;
this.Add(node);
}
}
}
}

int Height (TreeNode root) // Restituisce l'altezza del'albero
{
if (root == null) return -1;

int Hl = Height(Left(root));
int Hr = Height(Right(root));
if (Hl > Hr) return (1 + Hl);
else return (1+Hr);
}

int NodeCounter (TreeNode root)
{
if (root == null) return (0);
// Per ogni nodo visitato somma 1 alle chiamate ricorsive
else return (1 + NodeCounter(Left(root)) + NodeCounter(Right(root)));
}

TreeNode Left(TreeNode root) // Restituisce il sottoalbero sinistro
{
if (root == null) return (null);
else return (root.LeftChild);
}

TreeNode Right(TreeNode root) // Restituisce il sottoalbero destro
{
if (root == null) return (null);
else return (root.RightChild);
}
}
}


cosa ne pensate? se il contanodi é corretto mi manca "solo" la routine che elenca i nodi livello per livello per esempio: tutti i bisnonni, tutti i nonni, tutti i genitori e tutta la generazione corrente.

L'ho implementata così...

int countNodeSameLevel(TreeNode root, int h) //// Restituisce il numero di nodi di un determinato livello h
{

if (root == null)
{
return 0;
}
if (h == 0)
{
return 1;
}
else
{
return countNodeSameLevel(root.LeftChild, h - 1) + countNodeSameLevel(root.RightChild, h - 1);
}
}

[Badrepent]

Ciao Daniele, sono Luca :)
allora ti posto la soluzione al problema che hai posto (testa tutto per controllare bene che funzioni, ho fatto delle semplici prove e non ho sviluppato usando tdd). Il codice che avevi postato utilizzava un albero binario di ricerca, per il tuo contesto secondo me non è adatto in quanto ad esempio il numero di figli potrebbe essere pari a 1,2,3,4 etc quindi ho creato un albero non binario non di ricerca ma semplicemente un albero con numero variabile di figli.
Ho utilizzato diverse stili nel codice, ovvero alcune funzionalità le ho implementate seguendo un approccio classico senza ricorrere a particolari funzionalità che offre il C#. Per il conteggio dei nodi ad esempio ho utilizzato un passaggio di una value type per riferimento (cosi vedi come la differenza rispetto a c/c++).
Per quanto riguarda la visità per livelli (visita in ampiezza) ho utilizzato la classica coda ed un iteratore che utilizza yield return per congelare la stato di esecuzione...
posto qui i vari files che compongono la console application di prova

Classe Genealogic Tree

public class GenealogicTree
{

private TreeNode root {get;set;}

public GenealogicTree(String ancestorName)
{
root = new TreeNode(ancestorName);
}

public Boolean addDescendant(String name, string parentName)
{
if (parentName.Equals(root.name))
return root.addChild(name);
else
return addDescendant(name, parentName, root);
}

private Boolean addDescendant(string name, string parentName, TreeNode ancestor)
{
if (ancestor.name.Equals(parentName))
return ancestor.addChild(name);

int index = 0;
Boolean found = false;
while ( (index < ancestor.childs.Count) && (found == false) )
{
found = addDescendant(name, parentName, ancestor.childs[index]);
index++;
}
return found;
}

private TreeNode findNode(String ancestorName, TreeNode current)
{
if (current.name.Equals(ancestorName, StringComparison.CurrentCultureIgnoreCase))
return current;
else
{
int i = 0;
Boolean again = true;
TreeNode subTree = null;
while (again == true && i < current.childs.Count)
{
subTree = findNode(ancestorName, current.childs[i]);
if (subTree != null)
again = false;
else
i++;
}
return subTree;
}
}

public IEnumerator<TreeNode> printDescendants(String ancestorName)
{
TreeNode ancestor = findNode(ancestorName, root);
Queue<TreeNode> breadthQueue = new Queue<TreeNode>();
breadthQueue.Enqueue(ancestor);
while (breadthQueue.Count>0)
{
TreeNode actualNode = breadthQueue.Dequeue();
foreach (TreeNode child in actualNode.childs)
breadthQueue.Enqueue(child);
yield return actualNode;
}
}

public int countNode()
{
int count=0;
if (root==null)
count= 0;
else
countInternalNode(root, ref count);
return count+1;
}

private void countInternalNode(TreeNode node, ref int count)
{
foreach (TreeNode n in node.childs)
{
count++;
countInternalNode(n, ref count);
}
}
}



Classe TreeNode

public class TreeNode
{
public String name { get; set; }
public List<TreeNode> childs { get; set; }

public TreeNode(String name)
{
this.name = name;
childs = new List<TreeNode>();
}

public TreeNode getChild(int index)
{
if ((index < 0) || (index >= childs.Count))
throw new Exception("error in retrieving child" + index.ToString());
return childs[index];
}

public Boolean addChild(String childName)
{
childs.Add(new TreeNode(childName));
return true;
}

}


Classe Console App


static void Main(string[] args)
{
GenealogicTree tree = new GenealogicTree("Luca");
tree.addDescendant("Carlo", "Luca");
tree.addDescendant("Cristina", "Luca");
tree.addDescendant("Dario", "Luca");
tree.addDescendant("Ema", "Carlo");
tree.addDescendant("Fra", "Carlo");
tree.addDescendant("Guido", "Carlo");
tree.addDescendant("Emma", "Cristina");
tree.addDescendant("Ingo", "Dario");
tree.addDescendant("Lucia", "Dario");
tree.addDescendant("Manu", "Fra");
tree.addDescendant("Nico", "Fra");
tree.addDescendant("Orazio", "Fra");
tree.addDescendant("Paride", "Fra");
tree.printDescendants("Carlo");
Console.WriteLine("num nodi {0}", tree.countNode());
IEnumerator<TreeNode> enumerator = tree.printDescendants("Carlo");
while (enumerator.MoveNext())
Console.WriteLine(enumerator.Current.name);
Console.Read();

}


Spero ti sia di aiuto, se ci fossero problemi postali pure qui :)
Luca

[ideafissa]

Grazie per l'aiuto ora gli do un'occhiata:)