1、树的性质
度为m的树第i层的节点数至多有：mi−1
i=0∑hmi−1=m−1mh−1 n个节点的m叉树最小高度为：logm[n(m−1)+1]向上取整
2、二叉树
n0=n2+1
第K层的节点数至多有：2k−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;
}
前后序类似，注意
孩子-兄弟表示法：左孩子右兄弟
二叉排序树的删除
AVL树
ALV树的结点数量
h为树高
ALV树的插入
（在某节点的）L【左孩子】（的）R【右子树】（中插入导致不平衡）
哈夫曼树
红黑树
从任何一个结点到叶子节点的简单路径上黑节点的数量相同
struct RBnode{
int key;
RBnode* parent; //父节点
RBnode* lChild; //左孩子
RBnode* rChild; //右孩子
int color; //结点颜色
}
插入原则
3、并查集
表示
代码实现
#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;
}
}
对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];
}
}
}
时间复杂度
对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;
}
