Post ordered clue binary tree

Construction of post ordered clue binary tree

Trident linked list structure

The structure should use a trident linked list , Because it is necessary to find the successor node of a node when traversing the middle order clue binary tree , For the right child , The successor node is its parents , So we need to find the parent node , So use the Trident linked list
bool CreateThreadTree(ThreadTree &T, ThreadTree parent) To create a tree, you need to add one more parent Parameters , For the root node parent Set as NULL, When you create a tree, you pass in NULL As a parameter
Post order clue binary tree and middle order , The previous sequence is different , Special attention required

typedef struct ThreadNode{
    
    ElemType data;// data elements 
    struct ThreadNode *lchild,*rchild,*parent;// Left and right child pointer , A pointer to both parents @@@
    int ltag;//
    int rtag;// Left and right cue marks 
}ThreadNode,*ThreadTree;

PostThread

Construction of post ordered clue binary tree , Left and right
Pay attention to experience @@@ Role of

// Construction of post ordered clue binary tree ,  Left and right 
void PostThread(ThreadTree &p,ThreadTree &pre){
    
    if(p){
    
        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 ,
            PostThread(p->lchild,pre);// recursive , Clue left subtree 
        if(p->rtag != 1)//@@@
            PostThread(p->rchild, pre);// recursive , Clue right subtree 

        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 != NULL)
}

CreatePostThread

Through post order traversal, a post order clue binary tree is established ：
Be careful ： Because the post order traversal root is the last node to be traversed , So you can't simply use pre->rchild==NULL; Instead, we need to judge whether there is a right child

// The main process algorithm of establishing post order clue binary tree through post order traversal is as follows ：
void CreatePostThread(ThreadTree &T){
    
    ThreadTree pre=NULL;
    if(T){
                  // Nonempty binary tree , Clue 
        PostThread(T,pre);// Clue binary tree 
        /* pre->rchild==NULL;// Process the last node traversed  pre->rtag=1; */
        if(pre->rchild==NULL){
    //@@@
// Because the last node traversed is the root node of the whole tree ,
// So you can't simply pre->rchild==NULL
            pre->rtag=1;
        }
        else{
    
            pre->rtag=0;
        }
        //printf("CreatePostThread Finished\n");
    }
}

Traversal of post order clue binary tree

Firstnode

Find the sequence of clues in the binary tree , The first node under a sequence of subsequences
Ideas ：

1. Find the leftmost lower node first , But this node is not necessarily a leaf node , because For it may have a right child , But no left child
2. See if it has a right child , There are repeat 1. , Recursion Firstnode
3. No right child , It indicates that it is the node to be found ,return p

// Find the sequence of clues in the binary tree , The first node under a sequence of subsequences 
ThreadNode *Firstnode(ThreadNode *p){
    
    while(p->ltag==0){
    // Go to the bottom left node first , Not necessarily leaf nodes ,
        p=p->lchild;// Because it may have a right child , And no left child 
    }
    if(p->rtag == 0){
    // See if it has a right child , If there is a right child , Then recursion Firstnode
        Firstnode(p->rchild);
    }
    else{
    // If there is no right child , Explain that it is the node to be found ,return
        return p;
    }
}

Nextnode

Find the sequence of clues in the binary tree , node p A successor under a subsequent sequence
1. First judge whether there are parents , No parent is the root node , That is, the last node of post order traversal
2. If there are parents, it depends on whether the parent node has right children , And I am not a right child ！！！,( If you are the right child , Recursion will lead to an endless loop , Because the pointer between them forms a circle ),
If the parent node has a right child , be Fistenode( Right child of parent node ), That is, find the right child of the parent node ( The right child of the parent node may be a small subtree ) The first node of the subsequent traversal of
3. If the parent node has no right child , It indicates that the parent node should be traversed . Any node has a parent node ( Except for the root node )

// Find the sequence of clues in the binary tree , node p A successor under a subsequent sequence 
ThreadNode *Nextnode(ThreadNode *p){
    
    if(!p->parent){
    // explain p Unmarried parents ,p Root node 
        printf(" The root node is the last node in the subsequent traversal \n");
        return NULL;
    }
    if(p->parent->rtag==0 && **p->parent->rchild != p**){
    // Right child pointer 
        return Firstnode(p->parent->rchild);
    }
    else {
    // ltag==1  Return directly to the follow-up clues 
        return p->parent;
    }
}

Complete test code c++

// A postorder threaded binary tree 
#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,*parent;// Left and right child pointer , A pointer to both parents @@@
    int ltag;//
    int rtag;// Left and right cue marks 
}ThreadNode,*ThreadTree;

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

// Construction of post ordered clue binary tree ,  Left and right 
void PostThread(ThreadTree &p,ThreadTree &pre){
    
    if(p){
    
        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 ,
            PostThread(p->lchild,pre);// recursive , Clue left subtree 
        if(p->rtag != 1)//@@@
            PostThread(p->rchild, pre);// recursive , Clue right subtree 

        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 != NULL)
}
// The main process algorithm of establishing post order clue binary tree through post order traversal is as follows ：
void CreatePostThread(ThreadTree &T){
    
    ThreadTree pre=NULL;
    if(T){
                  // Nonempty binary tree , Clue 
        PostThread(T,pre);// Clue binary tree 
        /* pre->rchild==NULL;// Process the last node traversed  pre->rtag=1; */
        if(pre->rchild==NULL){
    
// Because the last node traversed is the root node of the whole tree ,
// So you can't simply pre->rchild==NULL
            pre->rtag=1;
        }
        else{
    
            pre->rtag=0;
        }
        //printf("CreatePostThread Finished\n");
    }
}


// Find the sequence of clues in the binary tree , The first node under a sequence of subsequences 
ThreadNode *Firstnode(ThreadNode *p){
    
    while(p->ltag==0){
    // Go to the node at the bottom left node first , Not necessarily leaf nodes ,
        p=p->lchild;// Because it may have a right child , And no left child 
    }
    if(p->rtag == 0){
    // See if it has a right child , If there is a right child , Then recursion Firstnode
        Firstnode(p->rchild);
    }
    else{
    // If there is no right child , Explain that it is the node to be found ,return
        return p;
    }
}
// Find the sequence of clues in the binary tree , node p A successor under a subsequent sequence 
ThreadNode *Nextnode(ThreadNode *p){
    
    if(!p->parent){
    // explain p Unmarried parents ,p Root node 
        //printf(" The root node is the last node in the subsequent traversal \n");
        return NULL;
    }
    if(p->parent->rtag==0 && p->parent->rchild != p){
    
    // Right child pointer , And the right child is not himself , Explain that you are a left child  @@@
        return Firstnode(p->parent->rchild);
    }
    else {
    // ltag==1  Return directly to the follow-up clues 
        return p->parent;
    }
}
 Using the above two algorithms , We can write a post order traversal algorithm of post order clue binary tree without head node 
void Postorder(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, ThreadTree parent){
    
    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;
        T->parent = parent;
        CreateThreadTree(T->lchild,T);
        CreateThreadTree(T->rchild,T);
        return true;
    }
}

// Subsequent destruction   Left and right 
bool DestroyThreadTree(ThreadTree T){
    
    if(T==NULL){
    
        printf(" Blank nodes \n");
        return false;
    }
    if(T->ltag!=1){
    //@@@ The left pointer points to the child node , Not clue signs 
        DestroyThreadTree(T->lchild);
    }
    //printf("%c->rtag %d\n",T->data,T->rtag);
    if(T->rtag!=1){
    //@@@
        DestroyThreadTree(T->rchild);
    }

    printf(" The destruction %c\n",T->data);
    free(T);//@@@'
    T=NULL;
    return true;
}

// The post order recursively traverses the clue binary tree 
void PostOrder(ThreadTree T){
    
    if(T){
    
        if(T->ltag!=1)
            PostOrder(T->lchild);
        if(T->rtag != 1)
            PostOrder(T->rchild);
        visit(T);
    }
}


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,NULL);// Input preamble , Build a binary tree 

    CreatePostThread(T);// Through post order traversal, a pre order clue binary tree is established 


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

    printf(" After traversing the clue binary tree ( recursive PostOrder ≈  normal BinaryTree Traverse ): \n");
    PostOrder(T);
    printf("\n");


    printf("\n After traversing the clue binary tree ( Non recursive Postorder ≈ Firstnode+Nextnode): \n");
    Postorder(T);

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

    return 0;
}

The test sample 1

Enter... In the input window ： AB#D##C##

The test sample 2

Preamble input : ABD##E##C#G##
Sequential output : DEBGCA**