Génération d'un arbre de recherche binaire à partir d'un index croissant

Question

J'ai un vecteur de pointeurs parents [0 1 1 2 2 3 3 5 5 ....] qui est fondamentalement un arbre binaire. L'index est l'enfant et la valeur correspondante représente l'indice de son parent dans le même vecteur. Par exemple: dans le vecteur ci-dessus, si vous comptez pour indexer 5, l'élément est 2, ce qui signifie que son parent se trouve à l'index 2. Toujours à l'index 2, l'élément est 1 A l'index 1, l'élément est 0 qui est le nœud racine.

Comment puis-je créer un arbre de recherche binaire à partir de cela?

OU,

Je générer des données au format arbre binaire dans lequel je connais les parents et les enfants correspondant, comment puis-je les stocker dans un arbre de recherche binaire?

L'index pour les enfants sera toujours supérieur au parent, comme indiqué dans le vecteur ci-dessus. Un exemple est: Je prends le nœud 1, le divise en deux nœuds, 2 et 3. Ensuite, prends le nœud 2 et divise-le en 4 et 5. Puis je prends le nœud 4 et le divise en 6 et 7 et ainsi de suite. Je souhaite conserver la relation parent-enfant dans l'arborescence de recherche binaire.

Cordialement

Wajahat

Answer 1

Générer un arbre binaire avec des éléments vides selon vous spécifications dans le vecteur. Lors de l'arrivée d'un nouvel élément, recherchez un emplacement: parcourez l'arbre selon les règles de l'arbre de recherche binaire - tous les enfants du sous-arbre gauche sont plus petits qu'un élément et tous les enfants du sous-arbre sont plus grands. Remplissez le noeud correspondant à l'élément dans l'arbre binaire. Par exemple, si vous avez cet arbre à un moment donné du temps:

et nouvelle valeur 3 arrive, il remplira l'enfant droit de nœud avec la valeur 2. Toutefois, si 5 arrive, il n'y a pas de place pour mettez-le dans la structure arborescente prédéfinie.