数据结构算法Day08-创新互联

typedef struct ThreadNode{
    ElemTyoe data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T){
        inThread(T,pre);
        //处理最后一个结点
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

//p指向正在访问的结点，pre指向刚刚访问过的结点
void InThread(ThreadTree &p,ThreadTree &pre){
    if(T){
        InThread(p->lchild,pre);
        if(p->lchild==NULL){
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL && pre->rchild==NULL){
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
         InThread(p->rchild,pre);
    }
}

求中序线索二叉树中序序列下的第一个结点

创新互联 - 成都机柜租用，四川服务器租用，成都服务器租用，四川网通托管,绵阳服务器托管，德阳服务器托管，遂宁服务器托管，绵阳服务器托管，四川云主机，成都云主机，西南云主机，成都机柜租用，西南服务器托管，四川/成都大带宽，成都机柜租用，四川老牌ＩＤＣ服务商

ThreadNode *FirstNode(ThreadNode *p){
    while(p->ltag==0)
        p=p->lchild;
    return p;
}

求中序线索二叉树中结点p在中序序列下的后继

ThreadNode *NextNode(ThreadNode *p){
    if(p->rtag=0)
        return FirstNode(p->rchild);
    else 
        return p->rchild;
}

中序遍历过程

void Inorder(ThreadNode *r){
    for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p))
        visit(p);
}

ThreadNode *LastNode(ThreadNode *p){
    while(p->rtag==0)
        p=p->rchild;
    return p;
}

ThreadNode *PreNode(ThreadNode *p){
    if(p->ltag==1)
        return p->lchild;
    else
        return LastNode(p->lchild);
}

#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int length;
}Sqlist;

void search(Sqlist L,int key){
    int low=0,high=L.length-1;
    int mid,temp;
    while(low<=high){
        mid=(low+high)/2;
        if(L.data[mid]==key)
            break;
        if(L.data[mid]high){
        for(int i=length-1;i>high;i--)
            L.data[i+1]=L.data[i];
        L.data[high+1]=key;
    }
}

void Swap(LinkList &L,int key){
    LinkList p,pre;
    pre=L,p=L->next;
    if(L->data==key)
        return;
    while(p){
        if(p->data=key){
           temp=pre->data;
           pre->data=key;
           p->data=temp;
        }else{
           pre=p;
           p=p->next;
        }
    }
}

先排序再找值

int search(SqList L,int key){
    int mid,low=0,high=L.length-1;
    for(int i=0;i

int flag=1,min=-100;
void InOder(BiTree T){
    if(T){
        InOder(T->lchild);
        if(min>T->data)
            flag=0;           
        min=T->data;
        InOder(T->rchild);
    }
}

int max,min;
void search(BiTree T){
    BiNode *p=T;
    if(T){
        while(p&&p->lchild){
           min=p->data;
           p=p->lchild;
        }
        p=T;
        while(p&&p->rchild){
            max=p->data;
            p=p->rchild;
        }
    }
}

int level(BiTree T,int key){
    int n=1;
    BiTree p=T;
    if(T){
        while(p->data!=key){
            if(p->datalchild;
            else
                p=p->rchild;
            ++n;
        }
    }
    return n;
}