Tomorrow will May Day to Chongqing, today in insist on finishing this blog, but also can alleviate a lot of play guilt.

Clue binary tree

In view of the waste of space in the use of ordinary binary tree, later generations have made improvements on the basis of binary tree, using its null pointer field to store some sort of traversal order pointing to its predecessor node, and the pointer to the successor node. These Pointers are called clues, and the corresponding binary tree becomes a clue binary tree. We make full use of the binary linked list of idle nodes to operate, make full use of. In other words, when defining the structure, two flag fields are added. If the node has a left subtree, then Lchild refers to the left child; otherwise, Lchild refers to the precursor. If the node has a right subtree, then Lchild points to the right child, otherwise it points to the backdrive.

operation

The establishment of binary tree of clues

/// build the binary tree of clues
ThreadTree InitThreadTree(a){
    char ch;
    ThreadTree T;
    scanf("%c", &ch);
    if(ch == The '#') T = NULL;
    else{
        T = (ThreadTree)malloc(sizeof(ThreadNode));
        T->data = ch;
        T->lchild = InitThreadTree();
        T->rchild = InitThreadTree();
    }
    return T;
}
Copy the code

Cueing of cue binary trees

/// Cue binary tree cue
If (lchild = null, lchild = null, lchild = null, lchild = null, lchild = null, lchild = null, lchild = null, lchild = null) And then recursion * and after recursion, the pointer pre is going to point every time to the node that you just visited * in order traversal, and if the left child is not null, it's going to keep processing the left child until the left child is null, and then processing the right child */

void InThread(ThreadTree p,ThreadTree pre){
    if(p ! =NULL) {//p is the current node, pre is the node just visited
        InThread(p->lchild, pre);    // Recursively, optimize the left subtree
        if(p->lchild == NULL) {// The left subtree is empty to establish the precursor clue
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre ! =NULL && pre->rchild == NULL){
            pre->rchild = p;          // If the right subtree is empty, the following clues of the precursor node are created
            pre->rtag = 1;
        }
        pre = p;                      // pre = p
        InThread(p->rchild, pre);     // Recursively, optimize the right subtree}}void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T ! =NULL){
        InThread(T, pre);
        pre->rchild = NULL;           // Processes the last node traversed
        pre->rtag = 1; }}Copy the code

Traversal of a binary tree of clues

/// trace binary tree traversal
/* nextnode is the firstnode to be traversed by nextnode. /* nextnode is the nextnode to be traversed by nextnode. NextNode = firstNode(p-> rChild); nextNode = firstNode(p->rchild); * /
ThreadTree FirstNode(ThreadTree p){
    while(p->ltag == 0) p = p->lchild;
    return p;
}

ThreadTree NextNode(ThreadTree p){
    if(p->rtag == 0) return FirstNode(p->rchild);
                                      // Access the first node of the tree with the right node as the root
    else return p->rchild;            // When rtag is 1, rChild always points to the next one
}

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

void InOrder(ThreadTree T){
    for(ThreadTree p = FirstNode(T); p ! =NULL; p = NextNode(p))
        Visit(p);
}
Copy the code

The overall

#include<stdio.h>
#include<stdlib.h>


typedef struct ThreadNode{
    char data;
    struct ThreadNode * lchild, * rchild;
    int ltag, rtag;//0 means not to build precursor or rear drive, 1 means to build
}ThreadNode, * ThreadTree;

ThreadTree InitThreadTree(a);
void InThread(ThreadTree p,ThreadTree pre);  // The binary tree is clued by the middle order traversal
void CreateInThread(ThreadTree T);  // Create the in-order binary tree by in-order traversal

ThreadTree FirstNode(ThreadTree p); // Find the first node in the order traversal
ThreadTree NextNode(ThreadTree p);  // Find the last node in the sequence of node p
void Visit(ThreadTree T);
void InOrder(ThreadTree T); // In order traversal

/// build the binary tree of clues
ThreadTree InitThreadTree(a){
    char ch;
    ThreadTree T;
    scanf("%c", &ch);
    if(ch == The '#') T = NULL;
    else{
        T = (ThreadTree)malloc(sizeof(ThreadNode));
        T->data = ch;
        T->lchild = InitThreadTree();
        T->rchild = InitThreadTree();
    }
    return T;
}

/// Cue binary tree cue
If (lchild = null, lchild = null, lchild = null, lchild = null, lchild = null, lchild = null, lchild = null, lchild = null) And then recursion * and after recursion, the pointer pre is going to point every time to the node that you just visited * in order traversal, and if the left child is not null, it's going to keep processing the left child until the left child is null, and then processing the right child */

void InThread(ThreadTree p,ThreadTree pre){
    if(p ! =NULL) {//p is the current node, pre is the node just visited
        InThread(p->lchild, pre);    // Recursively, optimize the left subtree
        if(p->lchild == NULL) {// The left subtree is empty to establish the precursor clue
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre ! =NULL && pre->rchild == NULL){
            pre->rchild = p;          // If the right subtree is empty, the following clues of the precursor node are created
            pre->rtag = 1;
        }
        pre = p;                      // pre = p
        InThread(p->rchild, pre);     // Recursively, optimize the right subtree}}void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T ! =NULL){
        InThread(T, pre);
        pre->rchild = NULL;           // Processes the last node traversed
        pre->rtag = 1; }}/// trace binary tree traversal
/* nextnode is the firstnode to be traversed by nextnode. /* nextnode is the nextnode to be traversed by nextnode. NextNode = firstNode(p-> rChild); nextNode = firstNode(p->rchild); * /
ThreadTree FirstNode(ThreadTree p){
    while(p->ltag == 0) p = p->lchild;
    return p;
}

ThreadTree NextNode(ThreadTree p){
    if(p->rtag == 0) return FirstNode(p->rchild);
                                      // Access the first node of the tree with the right node as the root
    else return p->rchild;            // When rtag is 1, rChild always points to the next one
}

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

void InOrder(ThreadTree T){
    for(ThreadTree p = FirstNode(T); p ! =NULL; p = NextNode(p))
        Visit(p);
}

int main(a)
{
    ThreadNode *T=(ThreadNode*)malloc(sizeof(ThreadNode));
    T=InitThreadTree();
    InThread(T,NULL);
    InOrder(T);
    return 0;
}
Copy the code