一.二叉树

本文的数据结构基于C语言练习。

C语言中的二叉树是一种数据结构，用于表示具有层次关系的数据集合。它由一个根节点开始，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树有许多相关性质，其中一些重要的包括：

1. 深度：指从根节点到某个节点的路径长度。树的深度等于所有节点深度的最大值加上1。
2. 高度：指从某个节点到其子树中的最远叶子节点的路径长度。树的高度等于根节点的高度。
3. 节点数：指树中节点的总数。如果树的深度为d，则节点数不超过2^d-1个。
4. 层次遍历：按照从上到下、从左到右的顺序遍历树中的节点。
5. 先序遍历：先访问根节点，然后按照先序遍历左子树和右子树。
6. 中序遍历：先按照中序遍历左子树，然后访问根节点，最后按照中序遍历右子树。
7. 后序遍历：先按照后序遍历左子树和右子树，然后访问根节点。
8. 平衡二叉树：指任意节点的左右子树高度差不超过1的二叉树。
9. 满二叉树：指所有非叶子节点都有两个子节点，且所有叶子节点都在同一层的二叉树。
10. 完全二叉树：指除最后一层之外，每一层都被填满的二叉树，最后一层从左到右填充。

二.二叉树的遍历

这里通过一个例子来详细介绍：

2023/6/8 09:49:27

二叉树遍历是指按照某个顺序依次访问二叉树的每一个节点，目前比较常用的三种遍历分别是先序遍历、中序遍历和后序遍历。下面举例介绍这三种遍历：

假设有如下一棵二叉树：

        1
       / \
      2   3
     / \   
    4   5

其中节点1为根节点，节点2和3为节点1的子节点，节点4和5为节点2的子节点。

1. 先序遍历：

先序遍历指先访问根节点，然后按先序遍历左子树和右子树。对于上述二叉树的先序遍历结果为：1, 2, 4, 5, 3。具体方法是从根节点出发，先输出根节点1，然后递归地遍历左子树2和右子树3，对于左子树2，先输出它的根节点2，然后递归遍历它的左子树4和右子树5。

1. 中序遍历：

中序遍历指按照中序遍历左子树、访问根节点和中序遍历右子树的顺序来遍历二叉树。对于上述二叉树的中序遍历结果为：4, 2, 5, 1, 3。具体方法是先递归遍历左子树2，输出节点4和2，再输出根节点1，最后递归遍历右子树3，输出节点5。

1. 后序遍历：

后序遍历指按照后序遍历左子树、后序遍历右子树和访问根节点的顺序来遍历二叉树。对于上述二叉树的后序遍历结果为：4, 5, 2, 3, 1。具体方法是先递归遍历左子树2，输出节点4和5，再递归遍历右子树3，输出节点2，最后输出根节点1。

三.线索二叉树

线索二叉树是一种特殊的二叉树，其每个节点都附带了指向其前驱和后继节点的线索，这些线索可以加速对节点的遍历操作。在线索二叉树中，若左子树存在，则左子树的最右下节点的右孩子会指向该节点的后继节点；若右子树存在，则右子树的最左下节点的左孩子会指向该节点的前驱节点。

线索二叉树的遍历分为前序、中序、后序和按照线索遍历四种方式，下面我们以中序遍历为例进行介绍。

假设有如下一棵二叉树：

        1
       / \
      2   3
     / \   
    4   5

其中节点1为根节点，节点2和3为节点1的子节点，节点4和5为节点2的子节点。

对于线索二叉树，我们需要首先将其转换成线索二叉树，过程如下：

1. 先建立一个头结点，其中头结点的左孩子指向根节点，右孩子指向中序遍历的最后一个节点。
2. 对于每一个节点，如果其左孩子不存在，则将其左孩子设置为前驱节点，并将前驱节点的右孩子指向该节点。如果其右孩子不存在，则将其右孩子设置为后继节点，并将后继节点的左孩子指向该节点。
3. 对根节点进行中序遍历，递归地对左子树进行线索化，然后处理其前驱指针，随后递归地对右子树进行线索化，然后处理其后继指针。

转换成线索二叉树之后，我们可以使用中序遍历来遍历整棵树。具体方法是从头结点开始，依次访问每个节点的后继节点，直到遇到尾节点即可结束遍历。

对于上述例子，通过中序遍历得到的节点顺序为：4, 2, 5, 1, 3。而在线索二叉树中，4的后继节点是2，2的后继节点是5，5的后继节点是1，1的后继节点是3，最后3的后继节点是尾节点，因此我们依次输出4、2、5、1、3就完成了中序遍历。

四.核心功能实现

1.初始构造一棵二叉树

//我们先初始化构造一个二叉树
void InitBTree(BTnode &T){
   
                     //T是一个结构体指针，指向这个树结点的结构体，而这个结构体又包含两个指针
    T=(BTnode)malloc(sizeof(BTree));
    T->data=50;
    T->lchild=NULL;
    T->rchild=NULL;
    T->ltag=T->rtag=0;
}

//插入一个树结点
void Insert(BTnode &T,int x){
   
                //这里x是我们插入结点需要保存的值
    if(T == NULL){
   
    // 最后结点为空，插入节点
        T = (BTnode)malloc(sizeof(BTree));
        T->data = x;
        T->lchild = NULL;
        T->rchild = NULL;
        T->ltag=T->rtag=0;
    }
    else{
   
   
        if(x <= T->data){
   
    // 插入左子树
            Insert(T->lchild, x);
        }
        else{
   
    // 插入右子树
            Insert(T->rchild, x);
        }
    }
}

2.普通二叉树的递归遍历

//访问，也就是输出函数
void Visit(BTnode &T){
   
   
    printf("%d\t",T->data);
}

//先序遍历
void Preorder(BTnode &T){
   
   
    if(T!=NULL){
   
   
        Visit(T);        //在访问函数里面定义我们想要的可视化输出
        Preorder(T->lchild);
        Preorder(T->rchild);
    }
}

//中序遍历
void Inorder(BTnode &T){
   
   
    if(T!=NULL){
   
   
        Inorder(T->lchild);
        Visit(T);
        Inorder(T->rchild);
    }
}

//后序遍历
void Postorder(BTnode &T){
   
   
    if(T!=NULL){
   
   
        Postorder(T->lchild);
        Postorder(T->rchild);
        Visit(T);
    }
}

3.二叉树线索化

//中序遍历线索化
void InThread(BTnode &p,BTnode &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;                   //这个结点标记完了，换下一个
        //中间这一部分可以改写成visit函数，你就看出来这个简单的递归了
        InThread(p->rchild,pre);
    }
}
/*这只是针对某一个结点线索化的处理过程*/

//构造中序线索二叉树
void createITree(BTnode &T){
   
             //调用刚刚线索化的方法来改造我们原来的二叉树
    BTnode pre=NULL;                //刚开始假设没有pre则为NULL
    if(T!=NULL){
   
   
        InThread(T,pre);                //把二叉树进行线索化
        pre->rchild=NULL;               //处理最后一个结点
        pre->rtag=1;
    }

}

4.线索二叉树的遍历

//该函数用来找二叉树中序序列的第一个结点
BTNode *Firstnode(BTnode &p){
    while(p->ltag==0)              //第一个结点没有前驱结点，所以其lchild=0，其余原本左孩子为空的结点都变成了左线索
        p=p->lchild;
    return p;
}

//该函数用来找后继结点
BTNode *Nextnode(BTnode &p){
    if(p->rtag==0)
        return Firstnode(p->rchild);      //rtag=0说明还是右孩子，找右子树中的第一个结点为其后继
    else
        return p->rchild;  //ratg=1说明右孩子就是后继，直接返回
}

//最后的大招，中序线索二叉树的遍历
void Inorder1(BTnode &T){
    for(BTNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))          //不要for循环只会i+1
        Visit(p);                
}

五.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct BTNode{
   
   
    int data;                          //为了实验简便，这里存储的数据都为整数
    struct BTNode *lchild,*rchild;
    int ltag,rtag;                   //左右线索标志
}BTree,*BTnode;                       //之所以这样是为了区分结点和树

//我们先初始化构造一个二叉树
void InitBTree(BTnode &T){
   
                     //T是一个结构体指针，指向这个树结点的结构体，而这个结构体又包含两个指针
    T=(BTnode)malloc(sizeof(BTree));
    T->data=50;
    T->lchild=NULL;
    T->rchild=NULL;
    T->ltag=T->rtag=0;
}

//插入一个树结点
void Insert(BTnode &T,int x){
   
                //这里x是我们插入结点需要保存的值
    if(T == NULL){
   
    // 最后结点为空，插入节点
        T = (BTnode)malloc(sizeof(BTree));
        T->data = x;
        T->lchild = NULL;
        T->rchild = NULL;
        T->ltag=T->rtag=0;
    }
    else{
   
   
        if(x <= T->data){
   
    // 插入左子树
            Insert(T->lchild, x);
        }
        else{
   
    // 插入右子树
            Insert(T->rchild, x);
        }
    }
}
/*为了方便定义插入规则，我们这里实验二叉排序树的规则即可*/
/*虽然这里用二叉排序树的规则方便了定义插入规则，但复杂了删除操作
  我们这里也只是为了演示二叉树的遍历和线索二叉树，所以不定义删除函数*/

//访问，也就是输出函数
void Visit(BTnode &T){
   
   
    printf("%d\t",T->data);
}

//先序遍历
void Preorder(BTnode &T){
   
   
    if(T!=NULL){
   
   
        Visit(T);        //在访问函数里面定义我们想要的可视化输出
        Preorder(T->lchild);
        Preorder(T->rchild);
    }
}

//中序遍历
void Inorder(BTnode &T){
   
   
    if(T!=NULL){
   
   
        Inorder(T->lchild);
        Visit(T);
        Inorder(T->rchild);
    }
}

//后序遍历
void Postorder(BTnode &T){
   
   
    if(T!=NULL){
   
   
        Postorder(T->lchild);
        Postorder(T->rchild);
        Visit(T);
    }
}

/*完成了这几个遍历后，我们要开始构造线索二叉树了*/
/*构造三种线索二叉树，前提是这个树以及存在，我们采用的方法是边遍历边构造*/

//中序遍历线索化
void InThread(BTnode &p,BTnode &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;                   //这个结点标记完了，换下一个
        //中间这一部分可以改写成visit函数，你就看出来这个简单的递归了
        InThread(p->rchild,pre);
    }
}
/*这只是针对某一个结点线索化的处理过程*/

//构造中序线索二叉树
void createITree(BTnode &T){
   
             //调用刚刚线索化的方法来改造我们原来的二叉树
    BTnode pre=NULL;                //刚开始假设没有pre则为NULL
    if(T!=NULL){
   
   
        InThread(T,pre);                //把二叉树进行线索化
        pre->rchild=NULL;               //处理最后一个结点
        pre->rtag=1;
    }

}
//这样我们就把原来的那棵二叉树改成了线索二叉树，为了查看我们的线索二叉树是否正确，我们又要写对应线索二叉树的方法

/*对线索树进行遍历时，只要先找到序列的第一个结点，然后依次取其后继，知道其后继为空代表整个二叉树遍历完*/
/*这里又有一点，其右线索标志为1，右孩子就指示其后继，但有时候也有其结点原来左右孩子就都不为空，这个时候就选择其右子树中
  第一个访问的结点（右子树中最左下的结点）为其后继*/

//该函数用来找二叉树中序序列的第一个结点
BTNode *Firstnode(BTnode &p){
   
   
    while(p->ltag==0)              //第一个结点没有前驱结点，所以其lchild=0，其余原本左孩子为空的结点都变成了左线索
        p=p->lchild;
    return p;
}

//该函数用来找后继结点
BTNode *Nextnode(BTnode &p){
   
   
    if(p->rtag==0)
        return Firstnode(p->rchild);      //rtag=0说明还是右孩子，找右子树中的第一个结点为其后继
    else
        return p->rchild;  //ratg=1说明右孩子就是后继，直接返回
}

//最后的大招，中序线索二叉树的遍历
void Inorder1(BTnode &T){
   
   
    for(BTNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))          //不要for循环只会i+1
        Visit(p);                
}

int main(){
   
   
    BTnode T;
    InitBTree(T);
    int nums[]={
   
   20,45,68,54,8};   //初始化二叉树待插入的数据,注意我们初始化定义了根结点的值为50
    for(int i=0;i<5;i++){
   
   
        Insert(T,nums[i]);
    }
    //到这里我们脑海里应该有了二叉树的画面了
    printf("先序遍历：");
    Preorder(T);
    printf("\n");
    printf("中序遍历：");
    Inorder(T);
    printf("\n");
    printf("后序遍历：");
    Postorder(T);
    printf("\n");
    //这一行下面开始我们转向线索二叉树
    createITree(T);
    printf("中序线索二叉树遍历：");
    Inorder1(T);
}

/*这里提一嘴，学习了栈和队列后，我们知道递归背地里是通过栈来实现的，所以这里的三种遍历我们如果
  不想使用递归，就得使用栈，比较麻烦，为了快速演示，递归虽然效率低但我们还是选择使用它*/

六.运行结果