数据结构-二叉树

2017-06-27

二叉树

二叉树的存储

二叉树的顺序存储-数据结构

//顺序存储，从树顶到底，从上到下，从左往右存入结点，不存在则标记
//顺序存储常用于满二叉树和完全二叉树
#define MaxSize 50	//定义树中元素的最大个数
typedef struct{    //树的结点定义
    ElemType data;  //数据元素
}BiTNode;
typedef struct{
	BiTNode nodes[MaxSize];	//存放栈中元素
}BiTree;	//

二叉树的链式存储-数据结构

//主要使用链式存储，之后也只讨论链式的方法
typedef struct BiTNode{
    ElemType data;  //数据域
    BiTNode *lchild,*rchild;    //左右孩子指针
}BiTNode,*BiTree;

二叉树的遍历

二叉树的先序遍历

void PreOrder(BiTree T){
    if(T != NULL){  //判断非空
        printf("%d",T->data);   //访问结点
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

二叉树的中序遍历-递归算法

void InOrderRecursion(BiTree T){
    if(T != NULL){  //判断非空
        InOrderRecursion(T->lchild);
        printf("%d",T->data);   //访问结点
        InOrderRecursion(T->rchild);
    }
}

二叉树的中序遍历-非递归算法

void InOrderNotRecursion(BiTree T){
    //非递归算法需要借助辅助栈
    BiTree p = T;
    BiTNode e;
    SqStack *stack = InitStack();   //详见数据结构-栈
    while(p||StackEmpty(*stack)){
        if(p){
            PushStack(*stack,*p);  //可修改stack数据结构，让其直接存储node
            p = p->lchild;
        }else{  //一直寻找左孩子直到为空
            e = PopStack(*stack);   //出栈
            printf("%d",e.data);  //访问结点
            p = p->rchild;
        }
    }
}

二叉树的后序遍历-递归算法

void PostOrderRecursion(BiTree T){
    if(T != NULL){  //判断非空
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%d",T->data);   //访问结点
    }
}

二叉树的后序遍历-非递归算法

//后序遍历的非递归算法，需要在结点内增加是否访问过的属性
typedef struct {
    BiTNode *p; //p是二叉树的结点的指针
    bool rvisited;    //rvisited=true代表p所指向的结点的右结点已被访问过
}SNode; //栈中的结点定义
void PostOrderNotRecursion(BiTree T){
    SNode sn;
    SNode temp;
    BiTNode *pt = T;
    SqStack *S = InitStack();
    while(T){
        sn.p = pt;
        sn.rvisited = false;    //设置初值让其没有访问过右孩子
        PushStack(*S, sn);  //一直让最左的孩子入栈
        pt = pt->lchild;
    }
    while(!StackEmpty(*S)){
        sn = GetPopStack(*S);	//取出栈顶元素判断，但是不弹出
        if(sn.p->rchild !=NULL&&sn.rvisited){   //若右孩子存在，且访问过
            temp = PopStack(*S);
            printf("%d",temp.p->data);  //访问结点
        }else{  //右孩子不存在，或者没有访问过
            sn.rvisited = true;
            pt = sn.p->rchild;  //往右访问右孩子
            while(pt){    //再一直寻找到最低的左孩子,如果右孩子不存在，则直接跳过，访问stack上一层
                sn.p = pt;
                sn.rvisited = false;    //设置初值让其没有访问过右孩子
                PushStack(*S, sn);  //一直让最左的孩子入栈
                pt = pt->lchild;
            }
        }
    }
}

二叉树的层次遍历

void LevelOrder(BiTree T){
    //层次遍历需要辅助队列，详见数据结构-队列
    SqQueue *queue = InitQueue();
    BiTree p = T;
    BiTNode e;
    EnSqQueue(*queue,*T); //将根结点的入队，修改队列数据结构，让其直接存储node
    while(!isSqQueueEmpty(*queue)){
        e = DeSqQueue(*queue);
        printf("%d",e.data); //访问该结点
        if(p->lchild != NULL){
            EnSqQueue(*queue,*p->lchild);  //左孩子不为空，则入队，先入左孩子
        }
        if(p->rchild != NULL){
            EnSqQueue(*queue,*p->rchild);  //右孩子不为空，则入队，后入右孩子
        }
    }
}

线索二叉树

线索二叉树的存储

//若无左子树，标记ltag，令lchild指向前驱；若无右子树，标记rtag，令rchild指向后继
typedef struct ThreadNode{
    ElemType data;  //数据元素
    ThreadNode *lchild,*rchild; //左、右孩子指针
    int ltag,rtag;  //左、右线索标志
}ThreadNode,*ThreadTree;

线索二叉树的构造-中序遍历线索化

//对二叉树的线索化，就是遍历一次二叉树
void InThread(ThreadTree &p,ThreadTree &pre){
    if(p != NULL){
        InThread(p->lchild, pre);
        //下列为访问结点，并作操作
        if(p->lchild==NULL){    //没有左孩子，则标记ltag为1，并把lchild设置为其前驱
            p->lchild = pre;
            p->ltag = 1;
        }
        if(pre!=NULL&&pre->rchild==NULL){   //没有右孩子，则标记rtag为1，并把rchild设置为其后继
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(p->rchild, pre);
    }
}
void CreateInThread(ThreadTree T){
    ThreadTree pre = NULL;
    if(T!=NULL){    //非空二叉树，线索化
        InThread(T,pre);    //线索化二叉树
        pre->rchild = NULL; //处理遍历的最后一个结点
        pre->rtag = 1;
    }
}

线索二叉树的遍历

线索二叉树的遍历-寻找某种遍历的第一个结点

//层次遍历需要知道后续结点，需要单独考虑，例如输入A,B为左右孩子，B为A的后续，只输入A，无法得到B
ThreadNode *FirstNode(ThreadNode *p,int order){
    switch (order){
        case 0: //"preorder"
            if(p->ltag == 0){   //有左孩子优先返回左孩子，没有左孩子有右孩子就返回右孩子，否则返回NULL
                return p->lchild;
            }else if(p->rtag == 0){
                return p->lchild;
            }else{
                return NULL;
            }
            break;
        
        case 1: //"inorder"
            while(p->ltag==0){
                p = p->lchild;  //向左找第一个
            }
            return p;
            break;
            
        case 2: //"postorder"
            while(p->rtag==0||p->ltag==0){
                if(p->rtag==0){
                    p = p->lchild;  //若有左孩子，则优先寻找左孩子
                }else{
                    p = p->rchild;  //把所有左右孩子都找完，最低下的结点为第一个
                }
            }
            return p;
            break;
        
        default:
            return NULL;
            break;
    }
}

线索二叉树的遍历-寻找某种遍历的下一个结点

//内部线索顺序根据线索化前的遍历顺序决定
ThreadNode *NextNode(ThreadNode *p,int order){
    switch (order) {
        case 0: //"preorder"
            if(p->ltag == 0){
                return p->lchild;//有左孩子，则其左孩子为其下一结点
            }else{
                return p->rchild;   //如果没有左孩子，无论是否有右孩子，rchild都为其后继
            }
            break;
            
        case 1: //"inorder"
            if(p->rtag == 0){
                return FirstNode(p->rchild, order); //见上一方法
            }else{
                return p->rchild;   //如果没有右孩子即rtag==1，则rchild内存的就是后继
            }
            break;
            
        case 2: //"postorder"
            if(p->rtag==0){ //如果有右孩子，往右找第一个
                return FirstNode(p->rchild, order); //见上一方法
            }else{
                return p->rchild;   //如果没有右孩子即rtag==1，则rchild内存的就是后继
            }
            return p;
            break;
            
        default:
            return NULL;
            break;
    }
}

线索二叉树的遍历-某种遍历

//所有遍历（层次除外）方法通用该方法
void ThreadInorder(ThreadNode *T,int order){
    for(ThreadNode *p = FirstNode(T, order);p!=NULL;p=NextNode(p,order)){
        printf("%d",p->data);
    }
}

二叉树排序树

二叉树排序树的存储-数据结构

//沿用二叉树的数据结构，只是逻辑不同了，且数据值唯一
typedef struct BiTNode{
    ElemType data;  //数据域
    BiTNode *lchild,*rchild;    //左右孩子指针
}BiTNode,*BiTree;

二叉树排序的构造

//构造二叉排序树，ElemType input[]为输入原数据，按序输入，n为输入数据数量
BiTree CreatBST(ElemType input[],int n){
    BiTree T = (BiTree)malloc(sizeof(BiTree));
    T = NULL;   //初始化空树
    int i = 0;
    while(i<n){
        InsertBST(T, input[i]); //插入方法
        i++;
    }
    return T;
}

二叉树排序的查找

BiTNode *FindBST(BiTree T,ElemType e){
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    p = NULL;
    while(T&&T->data!=e){   //T不为空，并且未找到需要的data
        if(T->data>e){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    if(T&&T->data==e){  //找到了该结点
        p = T;
    }else{
        printf("未找到该元素，p为空结点");
    }
    return p;
}

二叉树排序的插入

//插入二叉排序树，将插入元素e与结点比较，大于则往右插，小于则往左插
//此为递归方法，非递归则循环判断大小，小则访问左孩子，大则访问右孩子，直到找到空则插入
void InsertBST(BiTree &T,ElemType e){
    if(T==NULL){    //如果为空树，则插入根结点
        T->data = e;
        T->lchild = NULL;
        T->rchild = NULL;   //初始化左右孩子为空
    }else if(T->data > e){
        InsertBST(T->lchild, e);    //小于则往左插
    }else if(T->data < e){
        InsertBST(T->rchild, e);    //大于则往右插
    }else{
        printf("该字符已存在");   //数据值唯一，相等则不插入
    }
}

二叉树排序的删除

//删除二叉排序树需要分成4种情况讨论
void DeleteBST(BiTree &T,ElemType e){
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    BiTNode *ppre = (BiTNode*)malloc(sizeof(BiTNode));
    BiTNode *next = (BiTNode*)malloc(sizeof(BiTNode));  //用于情况4的删除
    p = FindBST(T, e);  //找到需要删除的结点
    if(p){  //p存在的情况下找pre
        ppre = FindBSTpre(T,e); //寻找p的父亲
    }
    if(p&&ppre == NULL){  //p为根结点，没有父亲
        if(p->lchild == NULL &&p->rchild == NULL){    //情况1:p的左右孩子都不存在，p为叶子结点
            //该情况下，直接释放结点，变成空树
            T = NULL;
        }else if(p->lchild != NULL &&p->rchild == NULL){    //情况2:p的左孩子存在，右孩子不存在
            //该情况下，直接子树代替结点，左子树
            T = p->lchild;
        }else if(p->lchild == NULL &&p->rchild != NULL){    //情况3:p的左孩子不存在，右孩子存在
            //该情况下，直接子树代替结点，右子树
            T = p->rchild;
        }else{    //情况4:p的左孩子存在，右孩子存在
            //该情况下选择被删除元素的直接后继或直接前驱来转换为下一次的删除
            //这里寻找下一个直接后继（也可是前驱）
            next = p->rchild;
            while(next->lchild){
                next = next->lchild;    //转为了情况1或者3（因为找到底，肯定没有左孩子了）
            }
            ppre = FindBSTpre(T, next->data);   //待删的父亲已经是next的父亲了
            p->data = next ->data;
            if(next->rchild){   //如果next右孩子存在，则为情况3
                ppre->lchild = next->rchild;    //next父亲的左孩子变为next的右孩子
            }else{
                ppre->lchild = NULL;    //否则直接删
            }
        }
    }else{  //p不为根结点
        if(p == NULL){  //该结点不存在，不操作
            printf("该结点不存在，删除失败");
        }else if(p->lchild == NULL &&p->rchild == NULL){    //情况1:p的左右孩子都不存在，p为叶子结点
            //该情况下，直接释放结点
            if(ppre->lchild == p){  //判断p是pre的哪个孩子，再删除
                ppre->lchild = NULL;
            }else{
                ppre->rchild = NULL;
            }
            free(p);    //释放p
        }else if(p->lchild != NULL &&p->rchild == NULL){    //情况2:p的左孩子存在，右孩子不存在
            //该情况下，直接子树代替结点，左子树
            if(ppre->lchild == p){  //判断p是pre的哪个孩子，再删除
                ppre->lchild = p->lchild;
            }else{
                ppre->rchild = p->lchild;
            }
            free(p);    //释放p
        }else if(p->lchild == NULL &&p->rchild != NULL){    //情况3:p的左孩子不存在，右孩子存在
            //该情况下，直接子树代替结点，右子树
            if(ppre->lchild == p){  //判断p是pre的哪个孩子，再删除
                ppre->lchild = p->rchild;
            }else{
                ppre->rchild = p->rchild;
            }
            free(p);    //释放p
        }else{    //情况4:p的左孩子存在，右孩子存在
            //该情况下选择被删除元素的直接后继或直接前驱来转换为下一次的删除
            //这里寻找下一个直接后继（也可是前驱）
            next = p->rchild;
            while(next->lchild){
                next = next->lchild;    //转为了情况1或者3（因为找到底，肯定没有左孩子了）
            }
            ppre = FindBSTpre(T, next->data);   //待删的父亲已经是next的父亲了
            p->data = next ->data;
            if(next->rchild){   //如果next右孩子存在，则为情况3
                ppre->lchild = next->rchild;    //next父亲的左孩子变为next的右孩子
            }else{
                ppre->lchild = NULL;    //否则直接删
            }
        }
    }
}