Ερωτήσεις για C

[nik324]

int isComplete(NODE * n) {
	int ld, rd;

	if (n == NULL )
		return 1;

	ld =  Depth(n->lc);
	rd =  Depth(n->rc);

	return (ld == rd && isComplete(n->lc) && isComplete(n->rc));

}

Προσπαθω να φτιαξω ενα προγραμμα για να βρισκει αν ενα δεντρο ειναι complete η οχι...Εκανα το παραπανω αλλα δεν δουλευει...

[albNik]

Ενας άλλος τρόπος

1. βρες το depth του tree.

2. κάνε ένα traverse  (post, pre, in ..)

 

έλεγξε αν όλοι οι κόμβοι < depth έχουν 2 παιδια,

και αν ολοι οι κόμβοι =depth  δεν έχουν παιδιά.  αυτό ειναι περιττό , αν ειχαν παιδια το depth θα ηταν μεγαλύτερο

[nik324]

Δεν καταλαβα τι εννοεις...

 

ελεγχω αν ολοι οι κομβοι εχουν βαθος < απο το συνολικο βαθος του δεντρου εχουν δυο παιδια

και αν ολοι οι κομβοι με βαθος  = συνολικο βαθος του δεντρου δεν εχουν κανενα παιδι;;

[albNik]

Μονο τον πρώτο έλεγχο κάνε.

Διασχίζοντας το δεντρο σε κάθε αναδρομή αυξάνεις το βαθος (το οποίο το περνάς σαν παράμετρο) κατά ένα,

όσο το βάθος ειναι < depth πρεπει (n->lc != NULL && n->rc != NULL)

[nik324]

int func(struct node *root, int *height) {
	int lh = 0, rh = 0;
	if (!root) {
		*height = 0;
		return 1;
	}
	c = func(root->left, &lh);
        c = func(root->right, &rh);

	if (lh > rh || rh > lh)
		return 0;
	*height = lh;
	return 1;
}

Δεν μου δουλευει ουτε αυτο...

[albNik]

Εγω θα το έγραφα έτσι 

int Height;  //tree height
int func(struct node *root, int h) 
{
   if(h==Height) return 1;
   if(root->left==NULL || root->right==NULL) return 0;
   return func(root->left, h+1) && func(root->right, h+1);

}

[nik324]

Το Heght ειναι το συνολικο υψος του δεντρου και το h ειναι το βαθος καθε κομβου σωστα?

Η κληση της συναρτησης θα γινει με h=0?

εχω την εντυπωση τωρα που κοιταω τον αλγοριθμο ξανα...οτι δεν ειναι για πληρες δεντρο...ειναι για full tree...

[albNik]

Αν εννοεις τη διαφορα  full vs complete

http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

 

 

 αλλαξε την πρώτη if 

if(h==Height || h==Height-1)return 1;

Η διαφορά είναι  στους κόμβους με βάθος Height-1

στο complete μπορουν να έχουν 0,1,ή 2 παιδιά. 

στο full εχουν πάντα 2

 

 

*Αυτό τωρα το προσεξα, 

Στα complete η τελευταία σειρα (h=Height) πρέπει να είναι όσο το δυνατόν πιο αριστερά.

δεν το ελεγχει  ...

 

 

[nik324]

δηλαδη ουτε με την καταλληλη αλαγη της if δεν θα το ελεγχει;

 

δεν καταλαβα..

[albNik]

Δεν αρκεί το if ...

Πρέπει οι κόμβοι της τελευταίας σειρας να ειναι συγκεντρωμενοι αριστερά όπως (H, I, J, K, L) στην εικόνα.

[nik324]

Αν διατρεχαμε το δεντρο ανα επιπεδα και καναμε καποιο σχετικο ελεγχο;

 

Ειναι εφικτη η lever-order traversal μονο αναδρομικα χωρις βοηθητικες δομες;

[albNik]

Ίσως θα μπορούσες εκτος απο βαθος (υψος) για κάθε κομβο να κοιτάς και το πόσο αριστερά ειναι (κατι σαν x-y)

δλδ το L είναι στη θέση (x=4, h=3) .

Μετα αποθηκεύεις την τελευταία σειρα σε ένα πίνακα και κοιτας να είναι γεματος απο αριστερά.

 

Δεν ξέρω πόσο εύκολο είναι το παραπάνω, μπορεί να υπάρχει και πιο εύκολος τρόπος.

[nik324]

οκ ευχαριστω θα το σκεφτω περισσοτερο

[albNik]

Ξεχνα τα x-y  .

Τη σειρα Heigh-1 (και κάθε σειρα) τη διασχίζεις απο αριστερα προς τα δεξιά.

Δες αν τα παιδια των κόμβων της έχουν συνέχεια απο αριστερα....

[nik324]

Αναδρομικα ειναι εφικτο;

 

 

Πως θα εχω ενα αλγοριθμο που αναδρομικα στην ουσια θα "κανει κατι" (θα ελεγχει τα παιδια) στο επιπεδο height-1;