Obtenir des informations à partir des nœuds de l'arbre

Question

Je travaille avec la structure de données arborescentes et j'essaie de trouver un moyen de calculer les informations que je peux obtenir des nœuds de l'arbre. Je me demande s'il existe des techniques qui peuvent assigner une plus grande importance numérique à un nœud qui apparait moins fréquemment au niveau inférieur (Distance de la racine de l'arbre) que les mêmes nœuds apparaissant au niveau supérieur et haute fréquence.

Pour donner un exemple, je veux donner plus de signification au nœud Book, au niveau 2 apparaissant une fois, puis au niveau 3 apparaissant trois fois.

Appréciera toutes les suggestions/pointeurs vers des techniques qui réalisent quelque chose de similaire.

Merci,

Prateek

Answer 1

Une mesure que je viens de penser est la suivante: pour une étiquette k, laissez-est « valeur » est la somme des niveaux qu'elle figure à. Donc, s'il apparaît à la racine et à l'enfant gauche de la racine, laissez sa valeur être 1.

Ensuite, vos étiquettes les plus «importantes» sont celles qui ont la valeur la plus faible.

EDIT: Cela rendra la racine plus importante que l'étiquette de ses enfants, même s'ils sont tous les deux identiques. Ainsi, une mise à l'échelle par nombre d'occurrences pourrait être en ordre.

Answer 2

Cela dépend de la signification que vous voulez donner à chaque niveau. Il suffit de multiplier par un nombre qui diminue à mesure que vous descendez les niveaux de l'arbre. Par exemple, n_nodes * 1/(3^n), où n est le niveau de l'arbre. Ainsi, un nœud sur le niveau 2 obtient une valeur de 1/4, et 3 nœuds sur le niveau 3 ont une valeur de 1/9. Ainsi, le noeud unique au niveau 2 est plus significatif.

Ajustez le dénominateur à votre convenance. Tant qu'il augmente avec n, il donnera plus de signification aux nœuds supérieurs de l'arbre.