convertir l'arbre binaire en arbre de recherche binaire en place en utilisant c

Question

Sans utiliser un espace supplémentaire, convertir l'arbre binaire en arbre de recherche binaire. J'ai trouvé l'algo suivant mais cela ne fonctionne pas.

Bttobst (nœud * root)

1. Si la racine est null retour

2.Else Current = Root

3.Si (courant-> gauche> courant) échange (courant-> gauche, courant)

4 4

5.Current = Current-> gauche

6 Allez à 3 si le courant! = Null Else allez à 4

7. Current = Current-> à droite

Merci d'avance

PS: J'ai vu ce lien mais je n'étais pas beaucoup d'aide !!Convertir l'arbre binaire -> BST (maintenant la forme de l'arbre d'origine)

Answer 1

Vous pouvez échanger les nœuds, y compris les sous-arbres (pas seulement le contenu du nœud) comme dans un arbre AVL http://en.wikipedia.org/wiki/avl_tree

Continuez simplement à échanger tant que les contraintes BST sont violées, redémarrant la première recherche profonde de Root après chaque échange.

Answer 2

Effectuez une traversée post-ordre (ascendante) de l'arbre, en prenant les nœuds visités et en les insérant dans un BST.

«Sans espace supplémentaire» empêche-t-il la récursivité?

Sinon, alors quelque chose comme:

# top level call passes null for bst
bt_to_bst (root, bst)
  # nothing to add to bst; just return it
  if null(root) -> return bst
  # if this is a leaf node, stick it into the BST
  if null(root->left) && null(root->right)
    return bst_insert(bst, root)
  # otherwise add all of left subtree into the bst and then the right tree
  bst = bt_to_bst (root->left, bst);
  return bt_to_bst (root->right, bst);

bt_to_bst est une opération de filtrage; Il prend un BST existant et en renvoie un nouveau avec le nœud donné ajouté.

Ajoutant un nœud feuille au bst est en sécurité parce que nous ne le visiterons plus jamais, nous pouvons donc remplacer son left et right pointeurs.