二叉树
二叉树定义与性质
定义
每个结点最多有两个子树
性质
1.非空二叉树上叶子结点数=度为2的结点数+1(树的结点数=所有结点度数+1)$n_0=n_2+1$
2.非空二叉树第k层最多有$2^{k-1}$个结点
3.高度为h的二叉树最多有$2^h-1$个结点
4.n个结点的完全二叉树的高度为$\lceil$$log_2(n+1)$$\rceil$ 或者$\lfloor$$log_2n$$\rfloor+1$
5.n个结点的完全二叉树 叶结点的个数$n_0$为$n_0=n-\lfloor$$n/2$$\rfloor$
特殊二叉树
1.满二叉树
2.完全二叉树:每个结点编号都与相同深度的满二叉树的结点一一对应
3.二叉排序树:左子树的结点关键字均小于根结点 右字数的结点关键字均大于根结点
4.平衡二叉树:树上任一结点的左子树和右子树的深度之差不超过1
二叉树的存储结构
二叉树的顺序存储
满二叉树和完全二叉树适合顺序存储 按满二叉树的编号分配位置 不存在的空结点置0
二叉树的链式存储
1
2
3
4
| typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
|
二叉树的遍历
先序遍历+中序遍历可确定二叉树(先序遍历第一个为根结点 根结点将中序遍历序列划分为左右序列再以此类推)
后序遍历+中序遍历可确定二叉树(后序遍历最后一个为根结点 将中序遍历序列左右划分))
层次遍历+中序遍历可确定二叉树
以此二叉树为例进行遍历
先序遍历(根左右)
若二叉树非空
1.访问根结点2.先序遍历左子树3.先序遍历右子树
先序遍历递归算法: 时间复杂度 $O(n)$
1
2
3
4
5
6
7
| void PreOrder(BiTree T){
if(T!=null){
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
|
序列为 `1 2 4 6 3 5`
中序遍历(左根右)
若二叉树非空
1.中序遍历左子树2.访问根结点3.中序遍历右子树
中序遍历递归算法: 时间复杂度 $O(n)$
1
2
3
4
5
6
7
| void InOrder(BiTree T){
if(T!=null){
InOrder(T->lchild);
visit(T);
InOrder(T->rchild);
}
}
|
序列为 `2 6 4 1 3 5`
中序遍历非递归算法效率高于递归算法 且需要栈来实现:
1
2
3
4
5
6
7
8
9
10
11
12
| void InOrder2(BiTree T){
InitStack(S);BiTree p;//p始终指向栈顶元素
while(p||IsEmpty(S)){
if(p){
Push(S,p);p=p->lchild;//根结点进栈 遍历左子树
}
else{
Pop(S,p)；visit(p);
p=p->rchild;//结点出栈 并被访问 然后遍历右子树
}
}
}
|
后序遍历(左右根)
若二叉树非空
1.后序遍历左子树2.后序遍历右子树3.访问根结点
后序遍历递归算法: 时间复杂度 $O(n)$
1
2
3
4
5
6
7
| void PostOrder(BiTree T){
if(T!=null){
PostOrder(T->lchild);
PostOrder(T->rchild);
visit(T);
}
}
|
序列为 `6 4 2 5 3 1`
层次遍历
按照每一层从左到右的顺序遍历整棵树 借助一个队列实现层次遍历
层次遍历算法:
1
2
3
4
5
6
7
8
9
10
11
| 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 4 5 6
线索二叉树
tag为0：child指向孩子结点 tag为1:child指向前驱/后继结点
| ltag |
lchild |
data |
rchild |
rtag |
| 左标识位 |
左孩子/前驱结点 |
元素位 |
右孩子/后继结点 |
右标识位 |
| 线索二叉树结构体代码： |
|
|
|
|
1
2
3
4
5
| typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
|
中序线索二叉树递归算法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 递归函数InThread：
void InThread(ThreadTree &p,ThreadTree &pre){
if(p!=null){
InThread(p->lchild,pre);
if(p->lchild==null){
p->lchild==null;p->ltag=1;
}
if((pre!=null)&&(pre->rchild==null)){
pre->rchild=p;
pre->rtag=1;
}
pre=p;
InThread(p->rchild,pre)
}
}
主函数CreateInThread
void CreateInThread(ThreadTree T){
ThreadTree pre=null;
if(T!=null){
InThread(T,pre);
pre->rchild=null;
pre->rtag=1;
}
}
|
树与二叉树的应用
二叉排序树(BST)
平衡二叉树(AVL)
哈弗曼树/哈弗曼编码
树 森林
树存储结构
1.双亲表示法:采用一组连续空间来存储结点 每个结点都有一个伪指针来表示其双亲结点的下标 根结点下标为0伪指针为-1
寻找双亲结点效率高 寻找孩子结点效率低
1
2
3
4
5
6
7
8
9
|
typedef struct{//树结点定义
ElemType data;
int parent;//双亲下标
}PTNode;
typedef struct{//树类型定义
PTNode nodes[Maxsize];
int n;//结点数
}PTree;
|
2.孩子表示法:将每个结点的孩子结点都用单链表连接起来 n个结点有n个孩子链表 按层次遍历给结点下标标号 根结点为0
寻找孩子结点效率高 寻找双亲结点效率低
1
2
3
4
5
6
7
8
9
10
11
12
13
|
typedef struct{//单链表中孩子结点
int child;//孩子结点下标
struct CNode *next;//下一个孩子结点的指针
}CNode;
typedef struct{//每一个结点
ElemType data;
struct CNode *child;//第一个孩子结点的指针
}CNode;
typedef struct{//树类型定义
PTNode nodes[Maxsize];
int n;//结点数
}CTree;
|
3.孩子兄弟表示法(二叉树表示法):左指针指向结点的第一个孩子结点 右指针指向结点的下一个兄弟结点(左孩子右兄弟)
可以方便的实现树转化为二叉树的操作 易于查找孩子结点 缺点:查找双亲结点很麻烦 需为每个结点添加一个parent域指向父结点
1
2
3
4
| typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
|
树 森林与二叉树转换
1.树与二叉树转换(左孩子右兄弟方法):结点的左指针指向第一个孩子结点 右指针指向它在树中相邻的兄弟结点
2.森林与二叉树转换:将森林中每一个树按照左孩子右兄弟转化为多个二叉树 然后将这几个二叉树的根结点都当做相邻的兄弟结点 然后连接起来构成一个大的二叉树
卐:二叉树转化为树或森林都是唯一的
树和森林的遍历
个人见解 转化为对应的二叉树再进行遍历写出序列
| 树 |
森林 |
二叉树 |
| 先根遍历 |
先序遍历 |
先序遍历 |
| 后根遍历 |
中序遍历 |
中序遍历 |
