This is the 25th day of my participation in Gwen Challenge

Tree algorithm is mainly to master the order after order in order level recursion and non-recursion algorithm written after order traversal binary tree non-recursion algorithm after order traversal non-recursion

void PostOrder(BiTree T){
    InitStack(S);
    p = T;
    r = NULL;
    while(p || ! isEmpty(S)){if(p){
            push(S,p);
            p = p->lchild;
        }else{
            GetTop(S,p);
            if(p->rchild && p->rchild! =r){// If the right subtree exists and has not been accessed
                p = p->rchild;
                push(S,p);
                p = p->lchild;
            }else{
                pop(S,p);
                visit(p->data);
                r = p;
                p = NULL; }}}}Copy the code

2. The non-recursive method of hierarchical traversal is used to solve the high-hierarchical traversal non-recursion of binary tree

int Btdepth(BiTree T){
    if(! T)return 0;
    int front =- 1,rear=- 1;
    int last =0,level=0;
    BiTree Q[MaxSize];
    Q[++rear] = T;
    BiTree p;
    while(front<rear){
        p=Q[++front];
        if(p->lchild)Q[++rear]=p->lchild;
        if(p->rchild)Q[++rear]=p->rchild;
        if(front == last){
            // The rightmost node of this layerlevel++; last = rear; }}return level;
}
Copy the code

The algorithm realizes the determination of a unique binary tree by preordering sequence and middle-ordering sequence

ElemType A[],ElemType B[],int l1,int h1,int l2,int h2){ // L1 =l2=1,h1 = h2 =n; root=(BiTNode *)malloc(sizeof(BiTNode)); root->data = A[l1]; for(i=l2; B[i]! =root->data; i++); llen = i-l2; rlen = h2-i; if(llen) root->lchild = PreInCreat(A,B,l1+1,l1+llen,l2,l2+llen-1); else root->lchild = NULL; if(rlen) root->rchild = PreInCreat(A,B,h1+1,h1+rlen,h2,h2+rlen-1); else root->rchild = NULL; return root; }Copy the code

Binary tree is stored by binary chain storage structure. An algorithm is designed to find the value of the k ‘node in the sequential traversal sequence

int i =1;
ElemType PreNode(BiTree b,int k){
    if(b==NULL)return '#';
    if(i==k)return b->data;
    i++;
    ch=PreNode(b->lchild,k);
    if(ch == '#'){
        ch = PreNode(b->rchild,k);
        return ch;
    }
    return ch;
}
Copy the code

Find the nearest common node r of the binary tree P,q

typedef struct{ BiTree t; int tag; }stack;}stack;}stack; stack s[],s1[]; BiTree Ancestor(BiTree ROOT,BiTNode *p,BiTNode *q){ top = 0; bt=ROOT; while(bt! =NULL||top>0){ while(bt! =NULL&&bt! =p&&bt! =q){ while(bt! =NULL){ s[++top].t =bt; s[top].tag =0 ; bt = bt->lchild; } } while(top! =0&&s[top].tag==1){ if(s[top].t==p){ for(i=1; i<=top; i++){ s1[i]=s[i]; top1=top; } if(s[top].t==q){ for(i=top; i>0; i--){ for(j=top1; j>0; j--){ if(s1[j].t==s[i].t) return s[i].t; } } //top--; ? }top--; }//while } } }Copy the code

The algorithm BiThrTree is used to find the precursors of the specified nodes in the sequential clue binary tree

InPostPre(BiThrTree t,BiThrTree p){
    BiThrTree q;
    if(p->rtag==0)q = p->rchild;
    else if(p->ltag ==0 )q= p->lchild;
    else if (p->lchild == NULL) q=NULL // p is the first node of the middle sequence
        else{
            // Find the ancestor of p, and then find the ancestor's child
            while(p->ltag==1&&p->lchild! =NULL)p=p->child;
            if(p->ltag==0){
                q=p->lchild;
            }else{
                q=NULL; }}return q;
    
}
Copy the code