吴江seo排名_前端开发和后端开发哪个好_谷歌seo什么意思_关键词是指什么

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <time.h>

using namespace std;

typedef struct Node {
    int key,ltag,rtag;
    Node *lchild,*rchild;
} Node;

Node *getNewNode(int key) {
    Node *p=(Node*)malloc(sizeof(Node));
    p->key=key;
    p->ltag=p->rtag=0;
    p->lchild=p->rchild=NULL;
    return p;
}

Node *insert(Node *root,int key) {
    if(!root)return getNewNode(key);
    if(rand()%2)root->lchild=insert(root->lchild,key);
    else root->rchild=insert(root->rchild,key);
    return root;
}

void clear(Node *root) {
    if(!root)return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}

void pre_order(Node *root) {
    if(!root)return ;
    cout<<root->key<<" ";
    if(!root->ltag)pre_order(root->lchild);
    if(!root->rtag)pre_order(root->rchild);
    return ;
}

void in_order(Node *root) {
    if(!root)return ;
    if(!root->ltag)in_order(root->lchild);
    cout<<root->key<<" ";
    if(!root->rtag)in_order(root->rchild);
    return ;
}

void post_order(Node *root) {
    if(!root)return ;
    if(!root->ltag)post_order(root->lchild);
    if(!root->rtag)post_order(root->rchild);
    cout<<root->key<<" ";
    return ;
}

Node *pre_node=NULL,*inorder_root=NULL;

void __build_inorder_thread(Node *root) {
    if(!root)return ;
    if(!root->ltag)__build_inorder_thread(root->lchild);
    if(inorder_root==NULL)inorder_root=root;
    if(root->lchild==NULL) {
        root->lchild=pre_node;
        root->ltag=1;
    }
    if(pre_node&&pre_node->rchild==NULL) {
        pre_node->rchild=root;
        pre_node->rtag=1;
    }
    pre_node=root;
    if(!root->rtag)__build_inorder_thread(root->rchild);
    return ;
}

void build_inorder_thread(Node *root) {
    __build_inorder_thread(root);
    pre_node->rchild=NULL;
    pre_node->rtag=1;
    return ;
}

Node *getNext(Node *root){
    if(root->rtag==1)return root->rchild;
    root=root->rchild;
    while(root->ltag==0&&root->lchild)root=root->lchild;
    return root;
}

int main() {
    srand(time(0));
    Node *root=NULL;
    for(int i=0; i<10; i++) {
        root=insert(root,rand()%100);
    }
    pre_node=inorder_root=NULL;
    build_inorder_thread(root);
    pre_order(root);
    printf("\n");
    in_order(root);
    printf("\n");
    post_order(root);
    cout<<endl;
    Node *node=inorder_root;
    while(node) {
        cout<<node->key<<" ";
        node=getNext(node);
    }
    clear(root);
    return 0;
}