四川盐亭网站制作公司

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

线索二叉树结构体
typedef struct ThreadNode{
    ElemTyoe data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;
27、建立中序线索二叉树
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);
    }
}
28、中序遍历线索二叉树

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

创新互联 - 成都机柜租用，四川服务器租用，成都服务器租用，四川网通托管,绵阳服务器托管，德阳服务器托管，遂宁服务器托管，绵阳服务器托管，四川云主机，成都云主机，西南云主机，成都机柜租用，西南服务器托管，四川/成都大带宽，成都机柜租用，四川老牌ＩＤＣ服务商
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);
}
29、寻找中序二叉树的前驱结点
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);
}
五、查找 1、顺序表递增有序，设计算法在最少的时间内查找值为x的元素。若找到，则将其与后继元素位置交换，否则按照递增顺序插入顺序表。
#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;
    }
}
2、找到单链表中值为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;
        }
    }
}
3、在顺序表中二分查找值为key的元素

先排序再找值

int search(SqList L,int key){
    int mid,low=0,high=L.length-1;
    for(int i=0;i
4、判断给定二叉树是否为二叉排序树

因为二叉排序树中序序列本身就是从小到大排列的，所以设置一个很小的值，让其与序列进行比较，如果比最小值大则替换，按理来说每个值都会被替换，只要后面有元素无法替换，则说明该二叉树不是排序树。

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);
    }
}
5、寻找二叉排序中的大值和最小值

二叉排序树中的大值在最右边，最小值在最右边

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;
        }
    }
}
6、设求出指定结点在给定二叉排序树中的层次
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;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


新闻标题：数据结构算法Day08-创新互联
本文路径：http://scyanting.com/article/dpeegs.html

其他资讯