5、树

1、树的性质

• 节点数=所有节点的度数和+1

• 度为m的树第i层的节点数至多有：$m^{i-1}$

• 高为h，m叉树至多的节点数：

$$\sum_{i=0}^{h}m^{i-1}=\frac{m^{h}-1}{m-1}$$

• n个节点的m叉树最小高度为：$\log_{m}[n(m-1)+1]$向上取整

2、二叉树

• $n_{0}=n_{2}+1$

• 第K层的节点数至多有：$2^{k-1}$

顺序存储（完全二叉树）

完全二叉树

struct TreeNode {
    ElemType value; //结点中的数据元素
    bool isEmpty; //结点是否为空
};

TreeNode t [MaxSize]; //按照完全二叉树的顺序存储

链式存储

typedef struct BiTNode{
    ELemType data; //数据域
    struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode ,*BiTree;

初始化

//定义一棵空树
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-> lchild = NULL;
p-> rchild = NULL;
root->lchild = p; //作为根节点的左孩子

先序遍历（根-左-右）

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

中序遍历（左-根-右）

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

后序遍历（左-右-根）

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

层序遍历

• 将根节点入队

• 队列非空

  • 将队头出队，访问该节点

  • 将该节点的左、右孩子依次插入队尾

• 重复直至队列为空

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

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

//层序遍历
void Level0rder(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);  //右孩子入队
    }
}

线索二叉树

中序线索二叉树

• 左指针指向中序前驱

• 右指针指向中序后继

//全局变量pre,指向当前访问结点的中(前、后)序前驱
ThreadNode *pre=NULL;

typedef struct BiTNode{
    ELemType data; //数据域
    struct BiTNode *lchild, *rchild; //左、右孩子指针
    int ltag, rtag; //左、 右线索标志：0表示孩子，1表示线索
}BiTNode ,*BiTree;

中序线索化

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;
}

前后序类似，注意

• 最后再修改一次per的后继节点为null

• 遍历时判断左右子树是孩子还是线索

孩子-兄弟表示法：左孩子右兄弟

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	中序遍历	中序遍历

二叉排序树的删除

• 叶子：直接删

• 只有左/右子树：直接删，用子树顶替

• 同时有左右子树

  • 用后继节点顶替：右子树中最左下的

  • 用前驱节点顶替：左子树中最右下的

AVL树

ALV树的结点数量

h为树高

$n_h$为树高为h时的最小节点数

$$n_0 = 0\\ n_1=1\\ n_2=2\\ n_h=1+n_{h-1}+n_{h-2}$$

ALV树的插入

（在某节点的）L【左孩子】（的）R【右子树】（中插入导致不平衡）

• LL：左孩子右上旋

• RR：右孩子左上旋

• LR

  • 左孩子的右孩子左上旋，变成新的左孩子

  • 新的左孩子右上旋

• RL

  • 右孩子的左孩子右上旋，变成新的右孩子

  • 新的右孩子左上旋

哈夫曼树

• 权值最小的两个组成兄弟

• 根节点的权值等于两个孩子相加

• 由n个节点建立哈夫曼树的过程中新建了n-1个节点

红黑树

• 本质是二叉排序树：左<根<右

• 结点只有两种颜色

• 根结点是黑色的

• 叶结点（失败结点、NULL结点）是黑色的

• 没有两个相邻的红节点

• 从任何一个结点到叶子节点的简单路径上黑节点的数量相同

• 设共有n个节点，则红黑树的树高：$h\leq2\log_2(n+1)$

红黑树

struct RBnode{
    int key;
    RBnode* parent;		//父节点
    RBnode* lChild;		//左孩子
    RBnode* rChild;		//右孩子
    int color;			//结点颜色
}

插入原则

• 确定插入位置（同二叉排序树）

  • 新节点是根：染为黑色

  • 新节点非根：染为红色

• 若插入后满足特性，插入结束

  • 插入只会破坏 “没有两个相邻的红节点” 这一特性

  • 除非是根节点，只要满足这一特性即可

• 否则，观察叔叔节点（父节点的兄弟）

  • 叔叔节点为黑色：旋转+染色

    • LL：右旋，父换爷+染色

    • RR：左旋，父换爷+染色

    • LR：左、右旋，儿换爷+染色

    • RL：右、左旋，儿换爷+染色

  • 叔叔节点为红色

    • 叔、父、爷染色，将爷节点视为新节点再继续处理

3、并查集

表示

• 通过森林表示多个集合

• 使用双亲表示法来存储并查集

  • 每个节点中保存指向双亲的“指针”

  • 根节点指针为-1

• 查：向上遍历，找到根节点，判断是否在同一个集合里

• 并：将两棵树的根节点相连

代码实现

#define SIZE 13;
int UFSets[SIZE];		//数组中存储每个节点的根

//初始化
void Initial(int S[]){
    for(int i=0; i<SIZE; i++){
        S[i]=-1;		//先全部设为单独的子集
    }
}

//查
int Find(int S[], int x){
    while(S[x]>=0){
        x = S[x];
    }
    return x;
}

//并
void Union(S[], int Root1, int Root2){
    if(Root1 != Root2){
        S[Root2] = Root1;
    }
}

• 时间复杂度

  • 并：O(1)

  • 查：O(n)

对union操作的优化

• 让高度低的树成为子树

• 根节点的绝对值表示树中的节点总数（-6、-3……）

• 合并时将根节点相加

void Union(S[], int root1, int root2){
    if(root1 != root2){
        if(S[root2] > S[root1]){
            S[root1] += S[root2];	//累加节点总数
            S[root2] = S[root1];	//小树合并到大树
        }else{
            S[root2] += S[root1];
            S[root1] = S[root2];
        }
    }
}

树高不超过$\lfloor \log_2n \rfloor + 1$

时间复杂度

• 并：O(1)

• 查：O($\log_2n$)

对find操作的优化

• 在查找某个节点找到根节点后，将路径上所有的节点都直接挂到根节点下

int Find(int S[], int x){
    int root = x;
    while(S[x]>=0){
        root = S[x];
    }
    while(x != root){
        int temp = S[x];
        S[x] = root;
        x = remp;
    }
    return root;
}