J'ai travaillé avec Binary Search Trees pendant mon temps libre, et je veux pouvoir supprimer des noeuds d'un arbre.Binary Search Arbres, comment trouvez-vous le maximum?
Pour que cela fonctionne, j'ai besoin de trouver la valeur maximale. Comment allez-vous faire cela? Pseudo-code ou des indices seraient appréciés. Je suis coincé et je ne sais pas trop comment commencer.
Un arbre binaire de recherche a les propriétés suivantes:
Le sous-arbre gauche d'un noeud ne contient que des nœuds avec des clés moins que la clé du nœud. La sous-arborescence droite d'un nœud contient uniquement des nœuds avec des clés supérieures à la clé du nœud. Les sous-arbres gauche et droit doivent également être des arbres de recherche binaires.
Avec cette définition à l'esprit, il devrait être très facile de trouver le maximum.
Cela a beaucoup aidé. Merci beaucoup! –
en effet - continuez juste à droite. Le noeud sans noeud enfant-droit contient la valeur max. –
Un pseudocode simple serait ceci. Il est indépendant de la recherche binaire je pense. facilement
int maxi = 0
foreach(array as item) // or any other loop
if item>maxi then maxi = item
répondu par la recherche ... http://duckduckgo.com/?q=%22binary+tree%22+find+maximum&kl=au-en –
Pourquoi avez-vous besoin de trouver la valeur maximale pour supprimer des nœuds de l'arbre? (Et ... pardonnez-moi mon scepticisme, mais est-ce vraiment dans votre temps libre ou est-ce le devoir? Cela * ressemble * beaucoup à des devoirs.) –
Certainement temps libre. J'ai fait une mission à ce sujet il y a quelque temps et je n'avais rien à faire avec la suppression. Je regardais autour de moi sur le site Web de mon professeur et j'ai vu qu'il avait un échantillon référençant 'trouver max'. Je voulais apprendre à le faire moi-même puisque je n'avais pas l'impression d'avoir moi-même saisi le concept dans sa totalité. –