基础概念

子树，孩子双亲，兄弟，度，叶子，分支节点，层次，深度（最大层次）有序树，无序树

二叉树简介

斜树

所有节点都只有左或右子树

满二叉树

所有节点同时具有左子树和右子树，同样深度的的二叉树中满二叉树的节点最多，叶子最多

完全二叉树

对一棵具有n个节点的二叉树按层序从左到右排序，二叉树某个节点的排序与同样位置的满二叉树节点的排序相同如果所有节点都满足这个条件，则二叉树为完全二叉树
若存在度为1的节点的话，有且只有一个，并且只有左孩子

二叉树性质

  1. 在二叉树的第i层上最多有2^{i-1}个节点
  2. 深度为i的二叉树最多有2^i-1个节点
  3. 对任何一棵二叉树来说，如果叶子节点数目为n0，度为2的节点数目为n2，则n0=n2+1
  4. 具有n个节点的完全二叉树的高度为至少为log2(n+1)
  5. 如果对一棵有n个节点的完全二叉树的节点按层序编号（从第一层开始到最下一层，每一层从左到右编号），对任一节点i有:
    1. 如果i=1 ，则节点为根节点，没有双亲。
    2. 如果2i > n ，则节点i没有左孩子 ；否则其左孩子节点为2i .（n为节点总数）
    3. 如果2i+1>n ，则节点i没有右孩子；否则其右孩子节点为2i+1

树的遍历

先序遍历

根左右

1
2
3
4
5
6
7
8
递归法
void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);	//访问根节点
		PreOrder(T->lchild);	//递归遍历左子树
		PreOrder(T->rchild);	//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
非递归
void PreOrder2(BiTree T){
	InitStack(S);	//初始化栈S
	BiTree p = T;	//p是遍历指针
	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
		if(p){
			visit(p);	//访问出栈结点
			Push(S, p);	//当前节点入栈
			p = p->lchild;	//左孩子不空，一直向左走
		}else{
			Pop(S, p);	//栈顶元素出栈
			p = p->rchild;	//向右子树走，p赋值为当前结点的右孩子
		}
	}
}

中序遍历

左根右

1
2
3
4
5
6
7
8
递归法
void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);	//访问根节点
		PreOrder(T->lchild);	//递归遍历左子树
		PreOrder(T->rchild);	//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
非递归
void InOrder2(BiTree T){
	InitStack(S);	//初始化栈S
	BiTree p = T;	//p是遍历指针
	while(p || !IsEmpty(S)){	//栈不空或p不空时循环
		if(p){
			Push(S, p);	//当前节点入栈
			p = p->lchild;	//左孩子不空，一直向左走
		}else{
			Pop(S, p);	//栈顶元素出栈
			visit(p);	//访问出栈结点
			p = p->rchild;	//向右子树走，p赋值为当前结点的右孩子
		}
	}
}

后序遍历

左右根

1
2
3
4
5
6
7
8
递归法
void PreOrder(BiTree T){
	if(T != NULL){
		visit(T);	//访问根节点
		PreOrder(T->lchild);	//递归遍历左子树
		PreOrder(T->rchild);	//递归遍历右子树
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
非递归
void PostOrder2(BiTree T){
	InitStack(S);
	p = T;
	r = NULL;
	while(p || !IsEmpty(S)){
		if(p){	//走到最左边
			push(S, p);
			p = p->lchild;
		}else{	//向右
			GetTop(S, p);	//读栈顶元素（非出栈）
			//若右子树存在，且未被访问过
			if(p->rchild && p->rchild != r){
				p = p->rchild;	//转向右
				push(S, p);	//压入栈
				p = p->lchild;	//再走到最左
			}else{	//否则，弹出结点并访问
				pop(S, p);	//将结点弹出
				visit(p->data);	//访问该结点
				r = p;	//记录最近访问过的结点
				p = NULL;
			}
		}
	}
}

前中后序遍历秒杀法

根据树写出他的三个遍历结果，在每个节点左下右标注三个点，从每次从根节点左子树出发，向下遍历，若为先序遍历，则按照经过左标记的先后顺序依次排列；中序遍历为下标记；后序遍历为右标标记

层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LevelOrder(BiTree T){
	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);	//右子树不空，则右子树根节点入队
		}
	}
}

线索二叉树

树、森林和二叉树的转化

树–>二叉树

  1. 连接所有兄弟节点
  2. 去掉出长子外的连线
  3. 层次调整
    此时所有长子都是左孩子，兄弟节点都是右孩子

森林–>二叉树

  1. 将森林中的所有树转化为二叉树
  2. 第一颗二叉树不动，将剩余的二叉树依次转化为前一个二叉树的右孩子

二叉排序/搜索/查找树(BST)

二叉排序树的节点包含key值，并要求key值
左孩子<根节点<右孩子，并且不存在重复key的节点

平衡二叉树(AVL树)

树上任意节点的高度之差不超过一
节点的平衡因子=左子树高-右子树高 需要满足：-1<=平衡因子<=1 可能值只为1，0，-1

哈夫曼树

哈夫曼树的定义

带权路径长度(WPL,{边树 * 权值}求和)最小的二叉树

哈夫曼树的构造

  1. 将所有节点按照权值从小到大的顺序排序
  2. 取最小的两个节点组成兄弟，并将两者权值的和作为两者的根节点，然后将该根节点加入排序，移除掉两个兄弟节点
  3. 步骤2，直到队列为空

哈夫曼编码

将哈夫曼树左分支权值改为0，右分支权值改为1，当当询问某一节点的哈夫曼编码时，从根节点向下深度遍历，然后将分支的权值连接起来即为该节点的哈夫曼编码