Deux séquences ergodiques connues pour construire des arbres binaires

L'ordre de traversée de l'arbre binaire est：Accéder d'abord au noeud racine,Puis l'ordre précédent traverse le Sous - arbre gauche,Avant de traverser le Sous - arbre droit.

L'ordre de traversée du milieu est：L'ordre du milieu traverse le Sous - arbre gauche du noeud racine,Puis l'accès au noeud racine,Enfin, l'ordre médian traverse le Sous - arbre droit.

L'ordre de traversée suivant est：Traversez ensuite le Sous - arbre gauche du noeud racine,Ensuite, l'ordre suivant traverse le Sous - arbre droit,Dernier accès au noeud racine.

Un.,Avant connu,L'ordre moyen traverse la séquence pour construire un arbre binaire

 【Principales idées】
1.Traversée pré - ordonnée,Pour connaître les racines
2.Traverser à travers l'ordre du milieu,Pour connaître la longueur du sous - arbre gauche.
3.Il ne reste que l'inconnu du sous - arbre droit,Construit Récursivement

//Fonctions auxiliaires
struct TreeNode* build(int* preorder, int l1, int r1, int* inorder, int l2, int r2){
    if (l1 > r1) return NULL;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[l1]; //La traversée du préfixe indique où se trouve la racine
    int mid = l2;
    while (inorder[mid] != root->val) mid++;
    int leftSize = mid - l2; // La traversée du milieu indique la longueur du sous - arbre gauche （ Avant la racine ）
    //Construction récursive
    root->left = build(preorder, l1 + 1, l1 + leftSize, inorder, l2, mid - 1);
    root->right = build(preorder, l1 + leftSize + 1, r1, inorder, mid + 1, r2);
    return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    return build(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1)   ;
}

2., Connu sous le nom de , L'ordre suivant traverse la séquence pour construire un arbre binaire ​

【Principales idées】
1. La clé est de comprendre comment la traversée post - séquentielle représente le Sous - arbre gauche 、Sous - arbre droit、Racine
·Traversée du préfixe：Racine/Sous - arbre gauche/Sous - arbre droit -> Racine sur la tête
·Traversée de l'ordre moyen：Sous - arbre gauche/Racine/Sous - arbre droit -> Longueur du sous - arbre gauche
·Traversée postérieure：Sous - arbre gauche/Sous - arbre droit/Racine -> Racine à la queue

La relation entre ：
Déterminer la longueur du sous - arbre gauche en traversant dans l'ordre du milieu ： leftSize = left_in - mid
Préfacepreorder Dans l'ordreinorder Post - orderpostorder
Sous - arbre gauche (left_pr + 1, left_pr + leftSize) || (left_in, mid - 1) || (left_po, left_po + leftSize - 1)
Sous - arbre droit (left_pr + leftSize + 1, right_pr) || (mid + 1, right_in) || (po + leftSize, right_po - 1)

*mid Parce qu'il est né dans la traversée de l'ordre moyen , Ne peut être utilisé que dans la traversée de l'ordre du milieu
* Pourquoi le Sous - arbre gauche dans la traversée post - séquentielle - 1？ Parce que ça vient de“0” Tableau des nombres de départ , Son indice est “ - 1”
* On peut déduire que le Sous - arbre gauche de la traversée de l'ordre précédent n'a pas besoin de - 1. Parce que l'en - tête de la traversée du préfixe est la racine , Pour devenir “De1C'est parti.”Tableau de

//Fonctions auxiliaires
struct TreeNode* build(int* inorder, int left_in, int right_in, int* postorder, int left_po, int right_po) {
    if (left_in > right_in) return NULL;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = postorder[right_po];
    int mid = left_in;
    while (inorder[mid] != root->val) mid++;
    int leftSize = mid - left_in;
    root->left = build(inorder, left_in, mid - 1, postorder, left_po, left_po + leftSize - 1);
    root->right = build(inorder, mid + 1, right_in, postorder, left_po + leftSize, right_po - 1);
    return root;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    return build(inorder, 0, inorderSize - 1, postorder, 0, postorderSize - 1);
}

Trois,Avant connu, L'ordre suivant traverse la séquence pour construire un arbre binaire

【Principales idées】
1. Construisez d'abord la racine , Puis Calculez la longueur du sous - arbre gauche , Construisez le Sous - arbre gauche , Enfin, le Sous - arbre droit . Tout le processus peut être réalisé par récurrence
2. Les racines ultimes sont faciles à trouver , C'est la première traversée de l'ordre précédent .
3. Quelle est la longueur du sous - arbre gauche ？ Peut être basé sur la définition de la traversée de l'ordre précédent et de la traversée de l'ordre suivant , C'est - à - dire la préface ：Racine->Gauche.->A droite,Post - order：Gauche.->A droite->Racine,Mise en placemid Le pointeur se déplace successivement sur la traversée post - séquentielle ,Attendez.mid La valeur correspondante est égale à la valeur de la racine sur la traversée précédente ,À ce moment - là.mid Soustrayez l'indice de la position de départ de la traversée et ajoutez 1, On obtient la longueur du sous - arbre gauche
4. On obtient la longueur du sous - arbre gauche , À part les racines , Le reste est le Sous - arbre droit

【Attention aux détails】
1. Attention aux circonstances particulières , Par exemple, il n'y a qu'un seul noeud dans la traversée pré - ordre
2.AvecC Lorsque la langue établit le noeud , N'oubliez pas d'initialiser . Comme construire un rootPoint,Je m'en souviens.root->left = NULL, root->right = NULL

//Fonctions auxiliaires
struct TreeNode* build(int* preorder, int left_pr, int right_pr, int* postorder, int left_po, int right_po) {
    if (left_pr > right_pr) return NULL;  Des circonstances exceptionnelles qui ne peuvent être évitées ①
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); //C Méthode d'établissement des noeuds linguistiques 
    root->val = preorder[left_pr]; 
    root->left = NULL, root->right = NULL; //InitialisationrootNoeud, Omettre cette étape serait une erreur 
    if (left_pr == right_pr) return root; // Des circonstances exceptionnelles qui ne peuvent être évitées ②
    int mid = left_po;
    while (mid < right_po && postorder[mid] != preorder[left_pr + 1]) mid++;
    int leftSize = mid - left_po + 1; // Pour obtenir la longueur du sous - arbre gauche 
    //Construire Récursivement les sous - arbres gauche et droit
    root->left = build(preorder, left_pr + 1, left_pr + leftSize, postorder, left_po, mid);
    root->right = build(preorder, left_pr + leftSize + 1, right_pr, postorder, mid + 1, right_po - 1);
    return root;
}

struct TreeNode* constructFromPrePost(int* preorder, int preorderSize, int* postorder, int postorderSize){
    return build(preorder, 0, preorderSize - 1, postorder, 0, postorderSize - 1);
}