数据结构【树篇】(一）

数据结构【树篇】(一）

---

---

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下竞争压力逐渐增大，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个寒假巩固速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

---

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
.

---

目录

一、二叉树

(一)、二叉树的存储结构

.
参考代码

#define MaxSize 100
//二叉树的顺序存储
struct TreeNode{
    int value;          //结点中的数据元素
    bool isEmpty;       //结点是否为空
};

//定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点
TreeNode t[MaxSize];
//初始化时所有结点标记为空
for(int i=0;i<MaxSize;i++){
    t[i].isEmpty=true;
}

//二叉树的链式存储
typedef ElemType{
    int value;
};

typedef struct BiTNode{
    ElemType data;                  //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针
    struct BiTNode *parent          //父节点指针
}BiTNode,*BiTree;

void init(){
    //定义一颗空树
    BiTree root = NULL;

    //插入根节点
    root = (BiTree)malloc(sizeof(BiTNode));
    root->data = {1};
    root->lchild = NULL;
    root->rchild = NULL;
    
    //插入新结点
    BiTNode *p = (BiTNode *) malloc(sizeof (BiTNode));
    p->data = {2};
    p->rchild = NULL;
    p->lchild = NULL;
    root->lchild = p;       //作为根节点的左孩子
    
}

---

(二)、二叉树的前中后遍历

//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);            //访问根结点
        PreOrder(T->lchild); //递归遍历左子树
        PreOrder(T->rchild); //递归遍历右子树
    }
}

//中序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild); //递归遍历左子树
        PostOrder(T->rchild); //递归遍历右子树
        visit(T);             //访问根结点
    }
}

//后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild); //递归遍历左子树
        PostOrder(T->rchild); //递归遍历右子树
        visit(T);             //访问根结点
    }
}

---

(三)、二叉树的层次遍历

//链式队列结点
typedef struct{
    BiTNode * data;             //存指针而不是结点
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,&rear;       //队头队尾
}LinkQueue;

//层次遍历
/*算法思想:
 ①初始化一个辅助队列
 ②根结点入队
 ③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话)
 ④重复③直至队列为空
 */
void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);               //初始化辅助队列
    BiTree p;
    EnQueue(Q,T);               //将根结点入队
    while(!IsEmpty(Q)){         //队列不空则循环
        DeQueue(Q,p);           //队头结点出队
        visit(p);               //访问出队结点
        if(p->lchild!=NULL)
            EnQueue(Q,p->lchild);   //左孩子入队
        if(p->rchild!=NULL)
            EnQueue(Q,p->rchild);   //右孩子入队
    }
}

---

(四)、线索二叉树

//线索二叉树结点
typedef struct ThreadNode{
    int data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;                      //左右线索标志
}ThreadNode,*ThreadTree;

---

二、二叉树的线索化

//中序线索化
//中序遍历二叉树，一边遍历一边线索化
void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);            //中序遍历左子树
        visit(T);                       //访问根节点
        InThread(T->rchild);            //中序遍历右子树
    }
}

ThreadNode *pre=NULL;       //全局变量pre,指向当前访问结点的前驱

void visit(ThreadNode *q){
    if(q->lchild==NULL){                //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T){
    pre = NULL;                        //pre初始为NULL
    if(T!=NULL){                       //非空二叉树才能线索化
        InThread(T);                   //中序线索化二叉树
        if(pre->rchild==NULL)
            pre->rtag=1;                //处理遍历的最后一个结点
    }
}


//中序线索化
void InThread(ThreadTree p,ThreadTree &pre){
    if(p!=NULL){
        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);
    }
}


//先序线索化
//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);                       //访问根节点
        if(T->ltag==0)
            PreThread(T->lchild);       //lchild不是前驱线索
        PreThread(T->rchild);            //前序遍历右子树
    }
}

ThreadNode *pre=NULL;       //全局变量pre,指向当前访问结点的前驱

void visit(ThreadNode *q){
    if(q->lchild==NULL){                //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&pre->rchild==NULL){
        pre->rchild=q;                  //建立前驱结点的后继搜索
        pre->rtag=1;
    }
    pre=q;
}

//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
    pre = NULL;                        //pre初始为NULL
    if(T!=NULL){                       //非空二叉树才能线索化
        PreThread(T);                   //先序线索化二叉树
        if(pre->rchild==NULL)
            pre->rtag=1;                //处理遍历的最后一个结点
    }
}


//先序线索化
void PreThread(ThreadTree p,ThreadTree &pre) {
    if (p != NULL) {
        PreThread(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;
        if(p->ltag==0)
            PreThread(p->lchild,pre);   //递归
        PreThread(p->rchild,pre);            //递归
    }
}

//后序线索化
//后序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);          //后序遍历左子树
        PostThread(T->rchild);          //后序遍历右子树
        visit(T);                       //访问根节点
    }
}

ThreadNode *pre=NULL;       //全局变量pre,指向当前访问结点的前驱

void visit(ThreadNode *q){
    if(q->lchild==NULL){                //左子树为空，建立前驱线索
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL&pre->rchild==NULL){
        pre->rchild=q;                  //建立前驱结点的后继搜索
        pre->rtag=1;
    }
    pre=q;
}

//后序线索化二叉树T
void CreatePostThread(ThreadTree T){
    pre = NULL;                        //pre初始为NULL
    if(T!=NULL){                       //非空二叉树才能线索化
        PostThread(T);                 //后序线索化二叉树
        if(pre->rchild==NULL)
            pre->rtag=1;                //处理遍历的最后一个结点
    }
}


//后序线索化
void PostThread(ThreadTree p,ThreadTree &pre) {
    if (p != NULL) {
        PostThread(p->lchild, pre);     //递归，线索化左子树
        PostThread(p->rchild,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;
    }
}

---

三、结语

感谢大家一直以来的不断支持与鼓励，码题集题库中的进阶塔350题正在逐步更新，之后会逐步跟进星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。