si j'ai un BST (appelez-le - T) et exécutez PRE-ORDER dessus, comment puis-je montrer/prouver que l'exécution de la fonction "tree_insert" sur la séquence I obtenu de la pré-commande, je reçois exactement le même arbre-T (j'ai commencé avec) de retour?pré-commande et "tree_insert" sur un BST
Merci,
Par exemple, disons que vous avez 3 éléments. Lorsque vous insérez, le premier élément que vous insérez sera pris comme racine, puis l'élément suivant (qu'il soit inférieur ou supérieur) sera placé en conséquence à gauche ou à droite. La traversée de pré-commande signifie qu'il va d'abord visiter la racine, puis récursivement l'enfant de gauche, puis récursivement le bon enfant. Donc, après la pré-commande affichera la racine, l'élément le plus petit, puis l'élément plus grand. Maintenant, essayez d'insérer à nouveau ces 3 éléments. Vous recevrez le même arbre. (Le premier élément inséré sera la racine, puis l'élément plus petit ira de nouveau à gauche, et l'élément plus grand ira automatiquement à droite). Vous pouvez modéliser ceci avec 6 scénarios différents avec 3 éléments.
Scénario 1: Éléments à insérer = {1, 2, 3} root = 1, droit enfant = 2, le plus à droite = 3
Quand vous faites Précommande, 1 est visité en premier. Pas d'enfant à gauche donc 2 est visité ensuite. 2 n'a pas laissé d'enfant donc 3 est visité ensuite. (1, 2, 3)
Scénario 2: Éléments pour insérer = {2, 1, 3} root = 2, l'enfant gauche = 1, droit enfant = 3
Quand vous faites Précommande, 2 est visité en premier. A quitté l'enfant 1 donc c'est visité ensuite. Le bon enfant a 3 ans, donc c'est visité la prochaine fois. (2, 1, 3)
Scénario 3: Éléments à insérer = {3, 1, 2} root = 3, gauche enfant = 1, enfant droit de l'enfant à gauche (à hauteur de 1) = 2
Lorsque vous effectuez preOrder, 3 est visité en premier. L'enfant gauche est 1 donc c'est visité ensuite. Aucun enfant à gauche de 1, donc 3 est visité ensuite. (3, 1, 2)
Il existe 3 autres scénarios que vous pouvez écrire et vérifier par vous-même.
peut-être l'utilisation de "show" (comme dans l'exemple) n'était pas le meilleur choix .. Je suppose que je devrais utiliser l'induction pour prouver que c'est correct pour tous cas, et l'étape de base est évidente, mais je ne suis pas sûr de savoir comment construire mon hypothèse ... (supposons qu'il est correct pour tous les arbres avec une hauteur de 1 ... n?) –
Oui, vous pouvez faire quelque chose comme ça . Et briser dans 6 cas serait ma première approche, mais je suis sûr qu'il y a probablement une manière mathématiquement inclinée de le faire en utilisant la théorie. –
Pour une traversée pré-commande donnée d'un arbre, plusieurs BST peuvent être formés. Un BST unique peut être généré si vous avez également une traversée INORDER à côté de la traversée de pré-commande.
pouvez-vous me donner un exemple d'une séquence de pré-commande qui peut générer plus d'un BST * en utilisant insert_tree *? –
essayez ici http://cs.stackexchange.com/questions – NIMISHAN