数据结构——树与二叉树

头文件TreeAndBinaryTree.h

// TreeAndBinaryTree.h - 树与二叉树
#include <iostream>

#define MAX_TREE_SIZE 100

/*********************************************************************************************************************************
 * 数据类型一览
 * ElemType 数据部分
 * TreeNoe 二叉树 顺序存储
 * BiTNode, *BiTree 二叉树 链式存储
 * ThreadNode, *ThreadTree 线索二叉树
 * BSTNode, *BSTree 二叉排序树
 * AVLNode, *AVLTree 二叉平衡树
 * HuffmanNode, *HuffmanTree 哈夫曼树
 * 
 * 操作函数 共享栈操作在函数名后加0或者1 不带头结点的链栈操作在函数名后加WithoutFirstNode
 * void InitTree(tree[], n) 初始化顺序存储二叉树
 * int InsertBiTree(&T, e) 二叉树的链式存储插入二叉树,默认左子树如果左子树满则插入右子树 插入根节点返回0，插入左子树返回1，插入右子树返回2
 * void Print(T) 输出二叉树结点
 * void PreOrder(T) 二叉树的链式存储先序遍历
 * void InOrder(T) 二叉树的链式存储中序遍历
 * void PostOrder(T) 二叉树的链式存储后序遍历
 * int TreeDepth(T) 利用递归求树的深度 返回树的深度
 * void LevelOrder(T) 二叉树的层序遍历
 * void Visit(*q) 访问节点
 * void InThread(T) 二叉树的链式存储中序遍历
 * void PreThread(T) 二叉树的链式存储先序遍历
 * void PostThread(T) 二叉树的链式存储后序遍历
 * void CreateInThread(&T) 中序线索化二叉树T
 * void CreatePreThread(&T) 先序线索化二叉树T
 * void CreatePostThread(&T) 后序线索化二叉树T
 * ThreadNode *InOrderPre(*q) 中序线索二叉树找指定结点的中序前驱pre 返回其前驱结点，无法找到则输出信息并返回NULL
 * ThreadNode *InOrderNext(*q) 中序线索二叉树找指定结点的中序后继next 返回其后继结点
 * ThreadNode *PreOrderPre(*q) 先序线索二叉树找指定结点的先序前驱pre 返回其前驱结点
 * ThreadNode *PreOrderNext(*q) 先序线索二叉树找指定结点的先序后继next 返回其后继结点
 * ThreadNode *PostOrderPre(*q) 后序线索二叉树找指定结点的后序前驱pre 返回其前驱结点
 * ThreadNode *PostOrderNext(*q) 后序线索二叉树找指定结点的后序后继next 返回其后继结点，无法找到则输出信息并返回NULL
 * BSTNode *SearchBST_Recursive(T, key) 二叉排序树的递归查找 返回查找到的结点，没有则返回NULL
 * BSTNode *SearchBST(T, key) 二叉排序树的非递归查找 返回查找到的结点，没有则返回NULL
 * void InsertBST_Recursive(&T, x) 二叉排序树的递归插入
 * void InsertBST(&T, x) 二叉排序树的非递归插入
 * void DeleteBST(&T, key) 二叉排序树的删除
 * void CreateBSTree(&T, str[], n) 二叉排序树的链式存储创建
 * AVLTree SingleRotateWithLeft(AVLTree &T) LL右单旋
 * AVLTree SingleRotateWithRight(AVLTree &T) LL左单旋
 * AVLTree DoubleRotateWithLeft(AVLTree &T） LR双旋
 * AVLTree DoubleRotateWithRight(AVLTree &T) RL双旋
 * void InsertAVL(&T, x) 二叉平衡树的插入
 * void CreateHuffmanTree(&T, n) 构造哈夫曼树
 * 
 *********************************************************************************************************************************/

// 数据部分用ElemType结构体表示
struct ElemType {
    int value;
};

// 二叉树的顺序存储
struct TreeNoe{
    ElemType data;
    bool isEmpty;
};

// 二叉树的链式存储
typedef struct BiTNode{
    ElemType data;  // 数据域
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
}BiTNode, *BiTree;  // n个结点对应2n个指针对应n+1个空链域


// 初始化二叉树的顺序存储
void InitTree(TreeNoe tree[], int n){
    for (int i = 0; i < n; i++) {
        tree[i].isEmpty = true;
    }
}

// 二叉树的链式存储插入根节点
void CreateBiTree(BiTree &T, ElemType e){
    T = (BiTree)malloc(sizeof(BiTNode));
    if (T == NULL) {
        std::cout << "分配空间失败" << std::endl;
        exit(0);
    }
    T->data = e;
    T->lchild = NULL;
    T->rchild = NULL;
}

// 二叉树的链式存储插入二叉树（默认左子树如果左子树满则插入右子树）
int InsertBiTree(BiTree &T, ElemType e){
    if (T == NULL) {
        CreateBiTree(T, e);
        return 0;  // 插入根节点
    }
    if (T->lchild == NULL) {
        CreateBiTree(T->lchild, e);
        return 1;  // 插入左子树
    }
    if (T->rchild == NULL) {
        CreateBiTree(T->rchild, e);
        return 2;  // 插入右子树
    }
    return -1;
}

// 输出二叉树结点
void Print(BiTree T){
    std::cout << T->data.value << " ";
}

// 二叉树的链式存储 先序遍历
void PreOrder(BiTree T){
    if (T != NULL) {
        Print(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 二叉树的链式存储 中序遍历
void InOrder(BiTree T){
    if (T != NULL) {
        InOrder(T->lchild);
        Print(T);
        InOrder(T->rchild);
    }
}

// 二叉树的链式存储 后序遍历
void PostOrder(BiTree T){
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        Print(T);
    }
}

// 利用递归求树的深度
int TreeDepth(BiTree T){
    if (T == NULL) {
        return 0;
    }
    int ldepth = TreeDepth(T->lchild);
    int rdepth = TreeDepth(T->rchild);
    return (ldepth > rdepth ? ldepth : rdepth) + 1;
}

// 层序遍历辅助链队列
typedef struct LinkNode{
    BiTNode *data;
    struct LinkNode *next;
}LinkNode;
typedef struct LinkQueue{
    LinkNode *front, *rear;  // 队头队尾指针
}LinkQueue;
void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}
bool EmptyQueue(LinkQueue Q){
    return Q.front == Q.rear;
}
void EnQueue(LinkQueue &Q, BiTNode *T){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = T;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}
BiTree DeQueue(LinkQueue &Q){
    LinkNode *p = Q.front->next;
    BiTNode *T = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    free(p);
    return T;
}

// 二叉树的层序遍历
void LevelOrder(BiTree T){
    if (T == NULL) {
        return;
    }
    LinkQueue Q;
    InitQueue(Q);
    EnQueue(Q, T);
    while (!EmptyQueue(Q)) {
        T = DeQueue(Q);
        Print(T);
        if (T->lchild != NULL) {
            EnQueue(Q, T->lchild);
        }
        if (T->rchild != NULL) {
            EnQueue(Q, T->rchild);
        }
    }
}

// 线索二叉树
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag,rtag;  // 左右线索标志，为0时指向孩子，为1时指向线索
}ThreadNode, *ThreadTree;

ThreadNode *Pre = NULL;

// 访问节点
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 InThread(ThreadTree T){
    if (T != NULL) {
        InThread(T->lchild);
        Visit(T);
        InThread(T->rchild);
    }
}

// 二叉树的链式存储 先序遍历
void PreThread(ThreadTree T){
    if (T != NULL) {
        Visit(T);
        if(T->ltag == 0){
            PreThread(T->lchild);  // 判断lchild是否指向的是孩子
            // 如果lchild指向的是前驱则不需要再进行递归遍历
        }
        PreThread(T->rchild);
    }
}

// 二叉树的链式存储 后序遍历
void PostThread(ThreadTree T){
    if (T != NULL) {
        PostThread(T->lchild);
        PostThread(T->rchild);
        Visit(T);
    }
}

// 中序线索化二叉树T
void CreateInThread(ThreadTree &T){
    Pre = NULL;
    if(T != NULL){
        InThread(T);
        if(Pre->rchild == NULL){
            Pre->rtag = 1;  // 手动处理最后一个结点的右指针标识
        }
    }
}

// 先序线索化二叉树T
void CreatePreThread(ThreadTree &T){
    Pre = NULL;
    if(T != NULL){
        PreThread(T);
        if(Pre->rchild == NULL){
            Pre->rtag = 1;  // 手动处理最后一个结点的右指针标识
        }
    }
}

// 后序线索化二叉树T
void CreatePostThread(ThreadTree &T){
    Pre = NULL;
    if(T != NULL){
        PostThread(T);
        if(Pre->rchild == NULL){
            Pre->rtag = 1;  // 手动处理最后一个结点的右指针标识
        }
    }
}

// 中序线索二叉树找指定结点的中序前驱pre
ThreadNode *InOrderPre(ThreadNode *q){
    if(q->ltag == 1){  // 如果左指针指向的是前驱
        return q->lchild;
    }
    // 否则，左指针指向的是左边孩子，则循环查找前驱的前驱
    ThreadNode *p = q->lchild;
    while(p->rtag == 0){
        p = p->rchild;
    }
    // q的左孩子的右孩子方向的叶子结点即为q的前驱
    return p;
}

// 中序线索二叉树找指定结点的中序后继next
ThreadNode *InOrderNext(ThreadNode *q){
    if(q->rtag == 1){  // 如果右指针指向的是后继
        return q->rchild;
    }
    // 否则，右指针指向的是右边孩子，则循环查找后继的后继
    ThreadNode *p = q->rchild;
    while(p->ltag == 0){
        p = p->lchild;
    }
    // q的右孩子的左孩子方向的叶子结点即为q的后继
    return p;
}

// 先序线索二叉树找指定结点的先序前驱pre
ThreadNode *PreOrderPre(ThreadNode *q){
    if(q->ltag == 1){  // 如果左指针指向的是前驱
        return q->lchild;
    }
    // 否则，左指针指向的是左边孩子，则根据先序排序 根 -> 左 -> 右 无法判断前驱
    std::cout << "无法找到该结点的先序前驱！" << std::endl;
    return NULL;
}

// 先序线索二叉树找指定结点的先序后继next
ThreadNode *PreOrderNext(ThreadNode *q){
    if(q->rtag == 1){  // 如果右指针指向的是后继
        return q->rchild;
    }
    if(q->lchild != NULL){  // 如果左孩子不为空，则左孩子的前驱即为后继
        return q->lchild;
    }else{  // 根据先序排序 根 -> 左 -> 右，且左孩子为空，则右孩子的前驱即为后继
        return q->rchild;
    }
}

// 后序线索二叉树找指定结点的后序前驱pre
ThreadNode *PostOrderPre(ThreadNode *q){
    if(q->ltag == 1){  // 如果左指针指向的是前驱
        return q->lchild;
    }
    if(q->rchild != NULL){  // 如果右孩子不为空，则右孩子的前驱即为前驱
        return q->rchild;
    }else{  // 根据后序排序 左 -> 右 -> 根，且右孩子为空，则左孩子的前驱即为前驱
        return q->lchild;
    }
}

// 后序线索二叉树找指定结点的后序后继next
ThreadNode *PostOrderNext(ThreadNode *q){
    if(q->rtag == 1){  // 如果左指针指向的是前驱
        return q->rchild;
    }
    // 否则，右指针指向的是右边孩子，则根据后序排序 左 -> 右 -> 根 无法判断后继
    std::cout << "无法找到该结点的后序后继！" << std::endl;
    return NULL;
}

// 二叉排序树
typedef struct BSTNode{
    int data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

// 查找二叉排序树中指定结点 递归
BSTNode *SearchBST_Recursive(BSTree T, int key){
    if(T == NULL  T->data == key){
        return T;
    }
    if(key < T->data){
        return SearchBST_Recursive(T->lchild, key);
    }else{
        return SearchBST_Recursive(T->rchild, key);
    }
}

// 查找二叉排序树中指定结点 非递归
BSTNode *SearchBST(BSTree T, int key){
    while(T != NULL && T->data != key){
        if(key < T->data){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    return T;
}

// 插入二叉排序树 递归
void InsertBST_Recursive(BSTree &T, int x){
    if(T == NULL){
        T = (BSTree)malloc(sizeof(BSTNode));
        T->data = x;
        T->lchild = T->rchild = NULL;
    }else if(x == T->data){
        std::cout << "该结点已存在！" << std::endl;
    }else if(x < T->data){
        InsertBST_Recursive(T->lchild, x);
    }else{
        InsertBST_Recursive(T->rchild, x);
    }
}

// 插入二叉排序树 非递归
void InsertBST(BSTree &T, int x){
    BSTree p = T, q = NULL;
    while(p != NULL && p->data != x){
        q = p;
        if(x < p->data){
            p = p->lchild;
        }else{
            p = p->rchild;
        }
    }
    if(p == NULL){
        p = (BSTree)malloc(sizeof(BSTNode));
        p->data = x;
        p->lchild = p->rchild = NULL;
        if(q == NULL){
            T = p;
        }else if(x < q->data){
            q->lchild = p;
        }else{
            q->rchild = p;
        }
    }else{
        std::cout << "该结点已存在！" << std::endl;
    }
}

// 删除二叉排序树
void DeleteBST(BSTree &T, int key){
    BSTree p = T, q = NULL;
    while(p != NULL && p->data != key){
        q = p;
        if(key < p->data){
            p = p->lchild;
        }else{
            p = p->rchild;
        }
    }
    if(p == NULL){
        std::cout << "该结点不存在！" << std::endl;
    }else{
        if(p->lchild == NULL){
            if(q == NULL){
                T = p->rchild;
            }else if(p == q->lchild){
                q->lchild = p->rchild;
            }else{
                q->rchild = p->rchild;
            }
        }else if(p->rchild == NULL){
            if(q == NULL){
                T = p->lchild;
            }else if(p == q->lchild){
                q->lchild = p->lchild;
            }else{
                q->rchild = p->lchild;
            }
        }else{
            BSTree s = p->lchild;
            while(s->rchild != NULL){
                s = s->rchild;
            }
            p->data = s->data;
            DeleteBST(p->lchild, s->data);
        }
    }
}

// 创建二叉排序树
void CreateBSTree(BSTree &T, int str[], int n){
    T = NULL;
    for(int i = 0; i < n; i++){
        InsertBST(T, str[i]);
    }
}

// 平衡二叉树
typedef struct AVLNode{
    int data;  // 数据域
    int height;  // 平衡因子，即高度
    struct AVLNode *lchild, *rchild;
}AVLNode, *AVLTree;

// 求最大值
int Max(int a, int b){
    return a > b ? a : b;
}

// LL右单旋转
AVLTree SingleRotateWithLeft(AVLTree &T){
    AVLTree p = T->lchild;
    T->lchild = p->rchild;
    p->rchild = T;
    T->height = Max(T->lchild->height, T->rchild->height) + 1;
    p->height = Max(p->lchild->height, T->height) + 1;
    return p;
}

// RR左单旋转
AVLTree SingleRotateWithRight(AVLTree &T){
    AVLTree p = T->rchild;
    T->rchild = p->lchild;
    p->lchild = T;
    T->height = Max(T->lchild->height, T->rchild->height) + 1;
    p->height = Max(p->rchild->height, T->height) + 1;
    return p;
}

// LR先左后右双旋转 即先变成LL结构再恢复平衡
AVLTree DoubleRotateWithLeft(AVLTree &T){
    T->lchild = SingleRotateWithRight(T->lchild);
    return SingleRotateWithLeft(T);
}

// RL先右后左双旋转 即先变成RR结构再恢复平衡
AVLTree DoubleRotateWithRight(AVLTree &T){
    T->rchild = SingleRotateWithLeft(T->rchild);
    return SingleRotateWithRight(T);
}

// 平衡二叉树的插入
void InsertAVL(AVLTree &T, int x){
    if(T == NULL){
        T = (AVLTree)malloc(sizeof(AVLNode));
        T->data = x;
        T->lchild = T->rchild = NULL;
        T->height = 1;
    }else if(x == T->data){
        std::cout << "该结点已存在！" << std::endl;
    }else if(x < T->data){
        InsertAVL(T->lchild, x);
        if(T->lchild->height - T->rchild->height == 2){
            if(T->lchild->lchild->height - T->lchild->rchild->height == 1){
                // 左左
                T = SingleRotateWithLeft(T);
            }else{
                // 左右
                T = DoubleRotateWithLeft(T);
            }
        }
    }else{
        InsertAVL(T->rchild, x);
        if(T->rchild->height - T->lchild->height == 2){
            if(T->rchild->rchild->height - T->rchild->lchild->height == 1){
                // 右右
                T = SingleRotateWithRight(T);
            }else{
                // 右左
                T = DoubleRotateWithRight(T);
            }
        }
    }
    T->height = (T->lchild->height > T->rchild->height ? T->lchild->height : T->rchild->height) + 1;
}

// 构造哈夫曼树
typedef struct HuffmanNode{
    int weight;  // 权值
    int parent, lchild, rchild;  // 双亲，左孩子，右孩子
}HuffmanNode, *HuffmanTree;
// 构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &T, int n){
    int i, j, k;
    int *w = (int *)malloc(sizeof(int) * n);
    for(i = 0; i < n; i++){
        std::cout << "请输入第" << i + 1 << "个结点的权值：";
        std::cin >> w[i];
    }
    for(i = 0; i < n; i++){
        for(j = i + 1; j < n; j++){
            if(w[i] > w[j]){
                k = w[i];
                w[i] = w[j];
                w[j] = k;
            }
        }
    }
    T = (HuffmanTree)malloc(sizeof(HuffmanNode) * n);
    for(i = 0; i < n; i++){
        T[i].weight = w[i];
        T[i].parent = T[i].lchild = T[i].rchild = -1;
    }
    for(i = n - 1; i > 0; i--){
        T[i].parent = i - 1;
        T[i - 1].lchild = i;
    }
}