我的思念像满二叉树般疯长，每个空指针都指向你的方向——全程动画可视化数据结构算法之二叉树

#include <iostream>

#define MaxSize 100

// 假设 ElemType 已经定义
typedef int ElemType;

// 定义二叉树节点结构体
struct TreeNode {
    ElemType value;      // 结点中的数据元素
    bool isEmpty;        // 结点是否为空
};

int main() {
    // 声明一个大小为 MaxSize 的数组
    TreeNode t[MaxSize];

    // 初始化所有结点为空
    for (int i = 0; i < MaxSize; i++) {
        t[i].isEmpty = true;  // 设置每个结点为空
    }

    // 可以在此后做一些测试或操作，确保程序正常运行
    return 0;
}

#include <stdlib.h> // 包含动态内存分配函数（如malloc）的头文件

// 定义树节点中存储的数据类型
struct ElemType{
    int value; // 数据成员，一个整型值
};

// 定义二叉树节点结构
typedef struct BiTNode{
    ElemType data; // 节点存储的数据
    struct BiTNode *lchild, *rchild; // 指向左子节点和右子节点的指针
} BiTNode, *BiTree; // BiTNode是节点类型，BiTree是指向节点的指针类型

int main() {
    // 定义一棵空树，root指针初始化为NULL
    BiTree root = NULL; 

    // 插入根节点
    root = (BiTree) malloc(sizeof(BiTNode)); // 动态分配内存来创建根节点
    root->data = {1}; // 给根节点的数据赋值为1
    root->lchild = NULL; // 初始化根节点的左子节点为NULL
    root->rchild = NULL; // 初始化根节点的右子节点为NULL

    // 插入新结点
    BiTNode *p = (BiTNode *) malloc(sizeof(BiTNode)); // 动态分配内存创建新节点
    p->data = {2}; // 给新节点的数据赋值为2
    p->lchild = NULL; // 初始化新节点的左子节点为NULL
    p->rchild = NULL; // 初始化新节点的右子节点为NULL
    root->lchild = p; // 将新节点作为根节点的左孩子

    return 0;
}

// 定义二叉树节点结构体
typedef struct BiTNode{
    ElemType data;  // 数据域，用于存储节点的数据，ElemType是之前定义好的数据类型
    struct BiTNode *lchild, *rchild;  // 左、右孩子指针，分别指向该节点的左子节点和右子节点
} BiTNode, *BiTree;  // BiTNode是二叉树节点类型，BiTree是指向二叉树节点的指针类型

// 假设这是一个用于访问节点的函数，具体功能根据实际需求定义
void visit(BiTree node) {
    // 这里可以写具体的访问操作，例如打印节点数据等
}

// 先序遍历函数
void PreOrder(BiTree T){
    if(T!=NULL){  // 如果二叉树不为空
        visit(T);  // 访问根结点
        PreOrder(T->lchild);  // 递归遍历左子树
        PreOrder(T->rchild);  // 递归遍历右子树
    }
}

// 定义二叉树节点结构体
typedef struct BiTNode{
    ElemType data;  // 数据域，存储节点的数据，ElemType为之前已定义的数据类型
    struct BiTNode *lchild, *rchild;  // 左、右孩子指针，分别指向该节点的左子节点和右子节点
} BiTNode, *BiTree;  // BiTNode是二叉树节点类型，BiTree是指向二叉树节点的指针类型

// 假设这是一个用于访问节点的函数，具体功能按需编写
void visit(BiTree node) {
    // 在这里编写具体的访问操作，例如打印节点数据等
}

// 中序遍历函数
void InOrder(BiTree T){
    if(T!=NULL){  // 如果二叉树不为空
        InOrder(T->lchild);  // 递归地中序遍历左子树
        visit(T);  // 访问根节点
        InOrder(T->rchild);  // 递归地中序遍历右子树
    }
}

// 定义二叉树节点的结构体
typedef struct BiTNode{
    ElemType data;  // 数据域，用于存储节点的数据，ElemType是预先定义好的数据类型
    struct BiTNode *lchild, *rchild;  // 左、右孩子指针，分别指向该节点的左子节点和右子节点
} BiTNode, *BiTree;  // BiTNode是二叉树节点类型，BiTree是指向二叉树节点的指针类型

// 假设这是一个访问节点的函数，具体实现根据实际需求编写
// 比如可以是打印节点数据，或者对节点进行其他操作
void visit(BiTree node) {
    // 此处编写具体访问操作的代码
}

// 后序遍历函数
void PostOrder(BiTree T){
    if(T!=NULL){  // 判断二叉树是否为空，若不为空才进行遍历操作
        PostOrder(T->lchild);  // 递归地后序遍历左子树
        PostOrder(T->rchild);  // 递归地后序遍历右子树
        visit(T);  // 访问根节点，在左右子树遍历完成后进行
    }
}

// 定义二叉树节点结构体，采用链式存储，每个节点存储一个字符类型的数据
typedef struct BiTNode{
    char data;  
    struct BiTNode *lchild, *rchild;  
} BiTNode, *BiTree;  

// 定义链式队列节点结构体，其中data存储的是指向二叉树节点的指针
typedef struct LinkNode{
    BiTNode *data;  
    struct LinkNode *next;  
} LinkNode;

// 定义链式队列结构体，包含队头和队尾指针
typedef struct{
    LinkNode *front, *rear;  
} LinkQueue;

// 二叉树层次遍历函数
void LevelOrder(BiTree T){
    LinkQueue Q;
    // 初始化辅助队列Q
    InitQueue(Q);  
    BiTree p;
    // 将根结点入队
    EnQueue(Q, T);  
    // 当队列不为空时，进行循环操作
    while (!IsEmpty(Q)){  
        // 队头结点出队，并将出队节点赋值给p
        DeQueue(Q, p);  
        // 访问出队的二叉树节点
        visit(p);  
        // 如果当前节点的左孩子不为空
        if(p->lchild != NULL)  
            // 将左孩子节点入队
            EnQueue(Q, p->lchild);  
        // 如果当前节点的右孩子不为空
        if(p->rchild != NULL)  
            // 将右孩子节点入队
            EnQueue(Q, p->rchild);  
    }
}
// 假设存在以下函数声明，具体实现根据实际需求编写
// 初始化队列函数
void InitQueue(LinkQueue &Q);
// 入队函数
void EnQueue(LinkQueue &Q, BiTree e);
// 判断队列是否为空函数
bool IsEmpty(LinkQueue Q);
// 出队函数
void DeQueue(LinkQueue &Q, BiTree &e);
// 访问二叉树节点的函数
void visit(BiTree node);

// 定义二叉树节点结构，采用链式存储，这种结构也被称为二叉链表
typedef struct BiTNode{
    ElemType data;  // 数据域，用于存储节点的数据，ElemType是预先定义好的数据类型
    struct BiTNode *lchild, *rchild;  // 左孩子指针和右孩子指针，分别指向该节点的左子节点和右子节点
} BiTNode, *BiTree;  // BiTNode表示二叉树节点类型，BiTree表示指向二叉树节点的指针类型

// 定义线索二叉树节点结构
typedef struct ThreadNode{
    ElemType data;  // 数据域，用于存储节点的数据，ElemType是预先定义好的数据类型
    struct ThreadNode *lchild, *rchild;  // 左、右指针，既可能指向孩子节点，也可能是线索
    int ltag, rtag;  // 左、右线索标志
                    // 当ltag为0时，lchild指针指向左孩子节点；当ltag为1时，lchild指针是前驱线索
                    // 当rtag为0时，rchild指针指向右孩子节点；当rtag为1时，rchild指针是后继线索
} ThreadNode, *ThreadTree;  // ThreadNode表示线索二叉树节点类型，ThreadTree表示指向线索二叉树节点的指针类型

​
// 定义二叉树节点结构体
typedef struct BiTNode{
    // 假设ElemType是之前已定义好的数据类型，用于存储节点数据
    ElemType data;  
    struct BiTNode *lchild, *rchild;  
} BiTNode, *BiTree; 

// 辅助全局变量，用于查找结点p的前驱
BiTNode *p;  // p指向目标结点
BiTNode *pre = NULL;  // 指向当前访问结点的前驱
BiTNode *final = NULL;  // 用于记录最终结果

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

// 访问结点函数
void visit(BiTNode *q){
    if (q==p)  // 当前访问结点刚好是结点p
        final = pre;  // 找到p的前驱
    else
        pre = q;  // pre指向当前访问的结点
}

​

// 中序线索化二叉树的函数，参数T是指向线索二叉树根节点的指针
void CreateInThread(ThreadTree T) {
    // 定义一个全局或在合适作用域声明的指针pre，这里先初始化为NULL，用于记录前驱节点
    pre = NULL;  
    // 判断二叉树是否为空，若不为空才进行线索化操作
    if (T != NULL) { 
        InThread(T);  // 调用函数对二叉树进行中序线索化
        // 检查线索化过程中记录的最后一个节点（即中序遍历的最后一个节点）的右指针情况
        if (pre->rchild == NULL) 
            pre->rtag = 1;  // 将该节点的右线索标志设为1，表示右指针是线索
    }
}


// 定义线索二叉树节点结构体
typedef struct ThreadNode{
    ElemType data;  // 数据域，存储节点的数据，ElemType是预先定义好的数据类型
    struct ThreadNode *lchild, *rchild;  // 左、右指针，可能指向孩子节点或者线索
    int ltag, rtag;  // 左、右线索标志，ltag/rtag为0表示指针指向孩子，为1表示指针是线索
} ThreadNode, *ThreadTree;  // ThreadNode表示线索二叉树节点类型，ThreadTree表示指向线索二叉树节点的指针类型

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

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

// 访问节点函数，用于建立线索
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;  // 将该节点的右线索标志设为1，表示右指针是线索
    }
}

// 定义线索二叉树节点结构体
typedef struct ThreadNode{
    ElemType data;  // 数据域，存储节点的数据，ElemType是预先定义的数据类型
    struct ThreadNode *lchild, *rchild;  // 左、右指针，可能指向孩子节点或者线索
    int ltag, rtag;  // 左、右线索标志，ltag为0时表示lchild指向左孩子，为1时表示是前驱线索；rtag同理
} ThreadNode, *ThreadTree;  // ThreadNode表示线索二叉树节点类型，ThreadTree表示指向线索二叉树节点的指针类型

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

// 先序遍历二叉树并进行线索化的函数
void PreThread(ThreadTree T){
    if(T != NULL){
        visit(T);  // 先处理根节点
        PreThread(T->lchild);  // 递归先序遍历左子树并线索化
        PreThread(T->rchild);  // 递归先序遍历右子树并线索化
    }
}

// 访问节点的函数，用于建立线索
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; // 更新前驱节点为当前节点
}

// 线索二叉树的结点结构假设包含左孩子指针、左线索标志、数据、右线索标志、右孩子指针
// 后序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T) {
    if (T!= NULL) {
        PostThread(T->lchild);  // 后序遍历左子树
        PostThread(T->rchild);  // 后序遍历右子树
        visit(T);  // 访问根节点
    }
}

// 访问结点函数，用于线索化操作
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;
}

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

// 定义线索二叉树节点结构体（假设之前已定义）
// typedef struct ThreadNode{
//     ElemType data;  
//     struct ThreadNode *lchild, *rchild;  
//     int ltag, rtag;  
// } ThreadNode, *ThreadTree; 

// 找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
    // 循环找到最左下结点(不一定是叶结点)，
    // 当左线索标志ltag为0时，说明lchild指向左子节点，继续向左找
    while(p->ltag == 0) p = p->lchild; 
    return p;
}

// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
    // 如果右线索标志rtag为0，说明rchild指向右子树
    // 则返回右子树中第一个被中序遍历的结点（即右子树的最左下结点）
    if(p->rtag == 0) return Firstnode(p->rchild); 
    else 
        return p->rchild;  // rtag为1时，直接返回后继线索
}

// 对中序线索二叉树进行中序遍历（利用线索实现的非递归算法），空间复杂度O(1)
void Inorder(ThreadNode *T){
    // 从根节点T开始，找到中序遍历的第一个节点赋值给p
    // 只要p不为空，就继续找p的后继节点并访问
    for(ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) 
        visit(p);  // 访问节点p，visit函数需要另外实现
}

// 定义线索二叉树节点结构体（假设之前已定义）
// typedef struct ThreadNode{
//     ElemType data;  
//     struct ThreadNode *lchild, *rchild;  
//     int ltag, rtag;  
// } ThreadNode, *ThreadTree; 

// 找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
    // 循环找到最右下结点(不一定是叶结点)，
    // 当右线索标志rtag为0时，说明rchild指向右子节点，继续向右找
    while(p->rtag == 0) p = p->rchild; 
    return p;
}

// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
    // 如果左线索标志ltag为0，说明lchild指向左子树
    // 则返回左子树中最后一个被中序遍历的结点（即左子树的最右下结点）
    if(p->ltag == 0) return Lastnode(p->lchild); 
    else 
        return p->lchild;  // ltag为1时，直接返回前驱线索
}

// 对中序线索二叉树进行逆向中序遍历
void RevInorder(ThreadNode *T){
    // 从根节点T开始，找到中序遍历的最后一个节点赋值给p
    // 只要p不为空，就继续找p的前驱节点并访问
    for(ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p)) 
        visit(p);  // 访问节点p，visit函数需要另外实现
}

// 定义一个宏，用于表示树中最多的结点数为100
#define MAX_TREE_SIZE 100 

// 定义树的结点结构
typedef struct{
    ElemType data;  // 数据元素，ElemType是预先定义好的数据类型
    int parent;  // 双亲位置域，用于存储该节点的双亲在数组中的下标
} PTNode; 

// 定义树的类型结构
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];  // 用数组来存储树的节点，即双亲表示法
    int n;  // 记录树中当前的结点数
} PTree; 

// 定义树中孩子节点相关的结构体
struct CTNode {
    int child;  // 记录孩子结点在数组中的位置
    struct CTNode *next;  // 指向下一个孩子的指针
};

// 定义树中每个节点的结构体
typedef struct {
    ElemType data;  // 数据元素，ElemType是预先定义的数据类型
    struct CTNode *firstChild;  // 指向第一个孩子的指针
} CTBox;

// 定义树的整体结构体
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];  // 用数组存储树的节点，MAX_TREE_SIZE是之前定义的宏，表示最大节点数
    int n, r;  // n表示树的结点数，r表示根的位置 
} CTree;

// 定义树的节点结构体，采用孩子兄弟表示法
typedef struct CSNode{
    ElemType data;  // 数据域，用于存储节点的数据，ElemType是预先定义好的数据类型
    struct CSNode *firstchild, *nextsibling;  // firstchild指向第一个孩子，可看作左指针
                                                // nextsibling指向右兄弟，可看作右指针
} CSNode, *CSTree;  // CSNode表示树节点类型，CSTree表示指向树节点的指针类型

// 定义二叉排序树节点结构体
typedef struct BSTNode{
    int key;  // 数据域，存储节点的值
    struct BSTNode *lchild, *rchild;  // 左、右孩子指针，分别指向该节点的左子节点和右子节点
} BSTNode, *BSTTree;  // BSTNode表示二叉排序树节点类型，BSTTree表示指向二叉排序树节点的指针类型

// 在二叉排序树中查找值为key的结点（非递归实现）
BSTNode *BST_Search(BSTTree T, int key){
    // 当树不为空且要查找的key值不等于当前节点的key值时，继续循环查找
    while(T != NULL && key != T->key){  
        if(key < T->key) 
            T = T->lchild;  // 若key值小于当前节点的key值，则在左子树上查找
        else 
            T = T->rchild;  // 若key值大于当前节点的key值，则在右子树上查找
    }
    return T;  // 返回查找结果，找到则返回对应节点指针，否则返回NULL
}

// 在二叉排序树中查找值为key的结点（递归实现）
BSTNode *BSTSearch(BSTTree T, int key){
    if (T == NULL)
        return NULL;  // 若树为空，查找失败，返回NULL
    if (key == T->key)
        return T;  // 若找到与key值相等的节点，查找成功，返回该节点指针
    else if (key < T->key)
        return BSTSearch(T->lchild, key);  // 若key值小于当前节点的key值，在左子树中递归查找
    else
        return BSTSearch(T->rchild, key);  // 若key值大于当前节点的key值，在右子树中递归查找
}

// 在二叉排序树插入关键字为k的新结点（递归实现）
// 参数T是指向二叉排序树根节点的指针的引用，这样可以在函数中修改根节点；k是要插入的关键字
int BST_Insert(BSTTree &T, int k){ 
    if(T == NULL){  // 原树为空，新插入的结点为根结点
        // 分配新的节点空间，(BSTTree)是强制类型转换，将malloc返回的void*转换为BSTTree类型
        T = (BSTTree)malloc(sizeof(BSTNode)); 
        T->key = k;  // 将新节点的关键字设为k
        T->lchild = T->rchild = NULL;  // 新节点的左右子树初始化为空
        return 1;  // 返回1，表示插入成功
    }
    else if(k == T->key)  // 树中存在相同关键字的结点，插入失败
        return 0; 
    else if(k < T->key)  // 插入到T的左子树
        return BST_Insert(T->lchild, k); 
    else  // 插入到T的右子树
        return BST_Insert(T->rchild, k); 
}