Preordered clue binary tree

reference Middle order clue binary tree

The overall idea is similar to the middle order clue binary tree
How to find the successor of a node in a preordered clue binary tree ？
node p In the subsequent ：

1. p There are left children , namely p->ltag==0, The left child is the successor
2. p No left child , Right pointer rchild That is to say p The subsequent nodes under the precedence ,
   prchild Or point to the right child ( In fact, the right child is also the successor node under the priority ), Or point to p Prior order The successor node of

It's just a preliminary clue void PreThread(ThreadTree &p,ThreadTree &pre) Pay attention to adding tag The judgment of the , Otherwise, there may be an endless cycle , The following code snippet shows

 if(p->ltag != 1)//@@@  Here because p->lchild May be p The precursor node of ,// If you don't judge ltag, It's a dead cycle ,
    PreThread(p->lchild,pre);// recursive , Clue left subtree 
 if(p->rtag != 1)//@@@
    PreThread(p->rchild, pre);// recursive , Clue right subtree 

Complete test code

// Preordered threaded binary trees 
#include<stdio.h>
#include<stdlib.h>
#define ElemType char
//tag by 0 Indicates pointing to the left / The right child , by 1 Indicates the precursor to the node / The subsequent 
typedef struct ThreadNode{
    
    ElemType data;// data elements 
    struct ThreadNode *lchild,*rchild;// Left and right child pointer 
    int ltag;// Because when defining a structure , It is not allocated memory , So the initial value cannot be stored . After the structure variable should be declared , Manual assignment 
    int rtag;// Left and right cue marks 
}ThreadNode,*ThreadTree;

void visit(ThreadTree T){
    
    printf("%c ",T->data);
}

// Construction of preorder clue binary tree ,  Root left and right 
void PreThread(ThreadTree &p,ThreadTree &pre){
    
    if(p){
    
        if(p->lchild == NULL){
    // The left subtree is empty , Establish precursor clues 
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL && pre->rchild==NULL){
    
            pre->rchild=p;// Establish the following clues of the precursor node 
            pre->rtag=1;
        }

        pre=p;// Mark the current node as the node just visited 
        if(p->ltag != 1)//@@@  Here because p->lchild May be p The precursor node of ,
            // If you don't judge ltag, It's a dead cycle ,
            PreThread(p->lchild,pre);// recursive , Clue left subtree 
        if(p->rtag != 1)//@@@
            PreThread(p->rchild, pre);// recursive , Clue right subtree 
    }//if(p != NULL)
}
// The main process algorithm for establishing a preordered clue binary tree through preorder traversal is as follows ：
void CreatePreThread(ThreadTree &T){
    
    ThreadTree pre=NULL;
    if(T){
                  // Nonempty binary tree , Clue 
        PreThread(T,pre);// Clue binary tree 
        pre->rchild==NULL;// Process the last node traversed 
        pre->rtag=1;
        //printf("CreatePreThread Finished\n");
    }
}


// Find preorder clues in a binary tree , The first node of a preordered sequence 
ThreadNode *Firstnode(ThreadNode *p){
    
    return p;
}

// Find preorder clues in a binary tree , node p A successor to a prior sequence 
/*p In the subsequent ： 1. p There are left children , namely p->ltag==0, The left child is the successor  2. p No left child , Right pointer rchild That is to say p The subsequent nodes under the precedence , prchild Or point to the right child ( In fact, the right child is also the successor node under the priority ), Or point to p The subsequent nodes under the precedence  */
ThreadNode *Nextnode(ThreadNode *p){
    
    if(p->ltag==0){
    // Left child pointer 
        return Firstnode(p->lchild);
    }
    else{
    // ltag==1  Return directly to the follow-up clues 
        return p->rchild;
    }
}

// Using the above two algorithms ,
// We can write a preorder traversal algorithm of preorder clue binary tree without head node 
void Preorder(ThreadNode *T){
    
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
    
        visit(p);
    }
}

// Create a threaded binary tree , Enter... In the previous order , # Represents an empty node 
bool CreateThreadTree(ThreadTree &T){
    
    ElemType ch;
    scanf("%c", &ch);
    if(ch == '#'){
    
        //printf(" Do you want to create an empty tree ？\n");
        T=NULL;
        return false;
    }
    else{
    
        T=(ThreadTree)malloc(sizeof(ThreadNode));
        T->ltag=T->rtag=0;
        if(!T){
    
            printf("malloc failure\n");
            return false;
        }
        T->data = ch;
        CreateThreadTree(T->lchild);
        CreateThreadTree(T->rchild);
        return true;
    }
}

// Subsequent destruction 
bool DestroyThreadTree(ThreadTree T){
    
    if(T==NULL){
    
        printf(" Blank nodes \n");
        return false;
    }
    if(T->ltag!=1)//@@@
        DestroyThreadTree(T->lchild);
    if(T->rtag!=1)//@@@
        DestroyThreadTree(T->rchild);
    printf(" The destruction %c\n",T->data);
    free(T);//@@@'
    T=NULL;
    return true;
}

// Preordered recursive traversal of clue binary tree 
void PreOrder(ThreadTree T){
    
    if(T){
    
        visit(T);
        if(T->ltag!=1)
            PreOrder(T->lchild);
        if(T->rtag != 1)
            PreOrder(T->rchild);
    }
}


int main(){
    
    ThreadTree T=NULL;
    printf(" Enter the values of the nodes in the binary tree in the previous order ( Input # Represents an empty node )\n");
    CreateThreadTree(T);// Input preamble , Build a binary tree 

    CreatePreThread(T);// Through preorder traversal, a preorder clue binary tree is established 

    ThreadNode *p=Firstnode(T);// Find the first node under the preorder traversal 
    printf("\n The first node of the preorder traversal p: %c\n",p->data);
    ThreadNode* r=Nextnode(p);// Find the middle order to traverse p In the subsequent 
    printf("p In the subsequent r: %c\n",r->data);

    printf(" Traverse the clue binary tree first ( recursive PreOrder ≈  normal BinaryTree Traverse ): \n");
    PreOrder(T);
    printf("\n");


    printf("\n Traverse the clue binary tree first ( Non recursive Preorder ≈ Firstnode+Nextnode): \n");
    Preorder(T);

    printf("\n Remember to destroy it after use !\n");
    DestroyThreadTree(T);

    return 0;
}

The test sample ：


test result