1. 树

1.1 树的基本概念

定义：除了根节点，每个节点有且仅有一个前驱
基本术语：

节点：树上的一个个元素，包含数据元素和指向子树的指针
节点的度：节点的子树个数
树的度：树中各节点的度的最大值
叶子节点：又称终端节点，指度为0的节点
分支节点：又称非终端节点，指度不为0的节点
孩子：节点的子树的根
双亲：孩子的上一个节点
兄弟：同一个双亲的孩子之间互为兄弟
祖先：根到某节点路径上的所有节点，都是这个节点的祖先
层次：根为第一层，往下为第二层
高度：树中节点的最大层次

1.2 树的存储结构

顺序存储结构
浪费空间，一般不使用
链式存储结构

孩子存储结构
双亲存储结构
孩子兄弟存储结构

2. 二叉树

定义：
每个节点最多只能有两个子树，即每个子树的度为0，1，2
且有左右之分，不能颠倒

2.1 二叉树的主要性质

非空二叉树上叶子节点数等于双分支节点数加1
即：n0 = n2 + 1
证明：设二叉树上叶子节点数为n0，单分支节点数为n1，双分支节点数为n2；
则总结点数为n0+n1+n2
总分支数为n1+2n2
根据总分支数=总节点数-1，有n0+n1+n2-1 = n1+2n2
化简后得到：n0 = n2 + 1
二叉树上的第i层最多有2^(i-1)个节点
高度为h的二叉树最多有2^h - 1个节点
在有n个节点的完全二叉树下，如果i为某节点的编号，那么有

i/2（向下取整）为其双亲的节点编号
2i为其左孩子编号，2i+1为其右孩子编号(若>n,那么无左右孩子)

具有n个节点的完全二叉树的高度为log2 n + 1(向下取整)

2.2 二叉树的存储结构

顺序存储结构
最适用于完全二叉树，适用于普通二叉树易导致浪费存储空间

链式存储结构
用一个节点和两个树之间的关系表示二叉树的链式存储结构

typedef struct BTNode
{
    Elemtype data;  //数据域
    struct BTNode *lchlid;  //左指针域
    struct BTNode *rchlid;  //右指针域
}BTNode；

2.3 二叉树的遍历算法

先序遍历(根 -> 左 -> 右)

void preorder(BTNode *p) {
    if(p != NULL) {
        visit(p);  //假设visit为打印等我们需要的操作
        preorder(p -> lchild);  //遍历左子树
        preorder(p -> rchild);  //遍历右子树
    }
}

中序遍历(左 -> 根 -> 右)

void inorder(BTNode *p) {
    if(p != NULL) {
        inorder(p -> lchild);  //遍历左子树
        visit(p);  //假设visit为打印等我们需要的操作
        inorder(p -> rchild);  //遍历右子树
    }
}

后序遍历(左 -> 右 -> 根)

void postorder(BTNode *p) {
    if(p != NULL) {
        postorder(p -> lchild);  //遍历左子树
        postorder(p -> rchild);  //遍历右子树
        visit(p);  //假设visit为打印等我们需要的操作
    }
}

层序遍历

void level(BTNode *p) {
    int front, rear;
    BTNode *queue[maxSize];
    front = rear = 0;
    BTNode *q;
    if(p != NULL) {
        rear = (rear + 1)% maxSize;
        queue[rear] = p;
        while(front != rear) {
            front = (front + 1)% maxSize;
            q = queue[front];
            visit(q);
            if(q -> lchild != NULL) {
                rear = (rear + 1)% maxSize;
                queue[rear] = q -> lchild;
            }
            if(q -> rchild != NULL) {
                rear = (rear + 1)% maxSize;
                queue[rear] = q -> rchild;
            }
        }
    }
}

2.4 线索二叉树

节点定义：

typedef struct TBTNode {
    char data;
    int ltag, rtag;  //线索标记，判断是子树还是线索
    struct TBTNode *lchild;
    struct TBTNode *rchild;
}TBTNode;

中序遍历线索二叉树算法：

void InThread(TBTNode *p, TBTNode *&pre) {
    if(p != null) {
        InThread(p -> lchild, pre); // 递归，左子树线索化
        if(p -> lchild == NULL) {
            // 建立当前节点的前驱线索
            p -> lchild = pre;
            p -> ltag = 1;
        }
        if(pre != NULL && pre -> rchlid == NULL) {
            // 建立前驱节点的后继线索
            p -> rchild = p;
            p -> rtag = 1;
        }
        pre = p;
        p = p->rchlid;
        InThread(p,pre); // 递归，右子树线索化
    }
}

// 建立线索二叉树
void createInThread(TBTNode *root) {
    TBTNode *pre = NULL;
    if(root != NULL) {
        InThread(root, pre);
        pre -> rchild = null;  //非空二叉树线索化
        pre -> rtag = 1;   // 处理中序最后一个节点 
    }
}

2.5 树和二叉树的应用

2.5.1 二叉排序树(BTS)

2.5.1.1 定义

若其左子树不为空，则左子树上所有关键字的值均不大于根关键字的值；
若其右子树不为空，则右子树上所有关键字的值均不小于根关键字的值；
每个根节点下的子树都满足此规则

2.5.1.2 存储结构

typedef struct BTNode {
    int key;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;

2.5.1.3 查找

BTNode* BSTSearch(BTNode* bt, int key) {
    if(bt == NULL)
        return NULL;
    else {
        if(bt->key == key) {
            return bt;            
        }
        else if(key < bt->key) {
            // 小于根节点关键字时，到左子树查找
            return BSTSearch(bt->lchild, key)
        }
        else {
            // 大于根节点关键字时，到右子树查找
            return BSTSearch(bt->rchild, key)
        }
    }
}

2.5.1.3 插入

int BSTInsert(BTNode* &bt, int key) {
    // 找到插入位置，创建新节点并插入
    if(bt == null) {
        bt = (BTNode*)malloc(sizeof(BTNode)); //创建新节点
        bt->lchild = bt->rchild = NULL;
        bt->key = key;
        return 1;
    }
    else  //节点不为空，查找插入位置，和查找算法类似
    {
        if(key == bt->key) {
            // 已经存在值，不用插入
            return 0;            
        }
                else if(key < bt->key) {
            // 小于根节点关键字时，到左子树查找
            return BSTSearch(bt->lchild, key)
        }
        else {
            // 大于根节点关键字时，到右子树查找
            return BSTSearch(bt->rchild, key)
        }
    }
}

2.5.1.4 构造

void CreateBTS(BTNode *&bt, int key[], int n) {
    // 初始化一棵空树
    bt = NULL;
    for(int i = 0; i < n; i++) {
        // 逐个插入节点
        BSTInsert(bt, key[i]);
    }
}

2.5.1.5 删除

p节点为叶子节点，直接删除
p节点只有左子树或者右子树，直接删除，将子树与原来双亲节点连接即可
p节点既有左子树又有右子树，将其直接前驱(或后继)作为双亲节点的连接点

2.5.2 平衡二叉树(AVL树)

2.5.2.1 定义

是一种特殊的二叉排序树，其左右子树高度的差的绝对值不超过1；其考点主要为平衡调整，共有LL, RR, LR, RL四种类型

2.5.2.2 LL

当前操作节点是A （A这个节点是最小失衡树的根节点)
断开该节点的根节点的左孩子连接线 (此时变成了两棵树，设以A为根节点的树为原根树，以B为根节点的树为新根树)
判断新根树的根节点的右子树是否为空

若空，直接把原根树作为新根树的右子树。
若不空:
– 将新根树的根节点的右子树独立出来，设其名为新原独树。
– 把新原独树作为原根树的左子树。
– 把原根树作为新根树的右子树。

2.5.2.3 RR

当前操作节点是66 （66这个节点是最小失衡树的根节点)
断开该节点的右孩子连接线 (此时变成了两棵树，设以66为根节点的树为原根树，以77为根节点的树为新根树)
判断新根树的根节点的左子树是否为空

若空，直接把原根树作为新根树的左子树。
若不空:
– 将新根树的根节点的左子树独立出来，设其名为新原独树。
– 把新原独树作为原根树的右子树。
– 把原根树作为新根树的左子树。

2.5.2.4 LR

先左旋，再右旋

2.5.2.5 RL

先右旋，再左旋

2.5.3 哈夫曼树与哈夫曼编码

2.5.4 并查集

2.5.5 红黑树

2.5.5.1 性质

节点包含红黑信息，根节点是黑色
所有叶子节点都是黑色，标记为NIL节点
每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。