数据结构之树和二叉树

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 4.2k 阅读时长 ≈ 4 分钟

第七章树和二叉树

第一节树的概念

1.概念

​ 是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

  • 有且仅有一个特定的称为根的结点；
  • 当n>1时，其余结点可分为m（m＞0）个互不相交的有限集，其中每个集合本身又是一棵树，并且成为根的子树

2.特点

  • 树的根结点没有前驱，除根节点外的所有结点有且只有一个前驱；
  • 树中所有结点可以由零个或多个后继

3.基本性质

\begin{flalign}
&1)树中的结点数等于所有结点的度数之和+1&&\
&2)度为m的树中第i层上至多有m^{i-1}个结点（i≥1）\
&3)高度为h的m叉树至多有(m^h-1)/(m-1)个结点\
&4)n结点m叉树最小高度为\lceil log_m[n(m-1)+1] \rceil \
\end{flalign}

4.存储结构

（1）双亲表示法

graph TB;
R((R))
A((A))
B((B))
C((C))
D((D))
E((E))
F((F))
G((G))
H((H))
K((K))
R-->A
R-->B
R-->C
A-->D
A-->E
C-->F
F-->G
F-->H
F-->K
data parent
0 R -1
1 A 0
2 B 0
3 C 0
4 D 1
5 E 1
6 F 3
7 G 6
8 H 6
9 K 6

（2）孩子表示法

将每个节点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点链表为空表）；

这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

（3）孩子兄弟表示法

优点：方便地实现树转换为二叉树的操作，易于查找结点的孩子等；

缺点：从当前结点查找其双亲结点比较麻烦

①在兄弟结点之间加一条线；

②对每个结点，只保留它与i一个孩子的连线，而与其他孩子 连线全部抹掉；

③以树根为轴心，顺时针旋转45°。

5.树、森林与二叉树遍历的对应关系

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

第二节二叉树

1.概念和性质

（1）概念

​ 一棵二叉树是结点的一个有限集合，该集合：

  • ​ 或者为空；
  • ​ 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

完全二叉树：效率很高的数据结构，由满二叉树而引出来的。是一种特殊的完全二叉树。

二叉排序树：左<中<右.

平衡二叉树：左子树与右子树深度之差不超过1。

（2）性质

\begin{flalign}
&1)n_0 = n_2 +1\
&2)非空二叉树上第k层至多有2^{k-1}个结点（k≥1）\
&3)高度为h的二叉树至少有2^h-1个结点（h≥1）\
&4)对完全二叉树按向上到下、从左到右的顺序依次编号1,2,…,n，则有以下关系：\
&~①当i>1时，结点i的双亲的编号是\lfloor i/2 \rfloor，即当i为偶数时，其双亲的编号是i/2，它是双亲的左孩子。当i为奇数时，其双亲的编号是（i-1）/2，它是双亲的右孩子。\
&~②当2i≤n时，结点i的左孩子编号为2i，否则无左孩子。\
&~③当2i+1≤n时，结点i的右孩子编号为2i+1，否则无右孩子。\
&~④结点i所在层次（深度）为\lfloor log_2i \rfloor+1。\
&5)具有n个（n>0）结点的完全二叉树的高度为\lceil log_2(n+1) \rceil 或\lfloor log_2n \rfloor +1。
\end{flalign}

2.存储结构和基本算法

（1）顺序存储结构

（2）链式存储结构

lchild data rchild 
1
2
3
4
typedef struct BiTree{
	ElemType data;  // 数据域
	struct BiTree *lchile,*rchild; // 左、右孩子指针
}BiTNode,*BiTree;

第三节二叉树的遍历算法

1.先序遍历

递归算法

1
2
3
4
5
6
7
void PreOrder(BiTree T){
    if(T){
        visit(T);		//访问根结点
        PreOrder(T->lchild);	//递归遍历左子树
        PreOrder(T->rchild);	//递归遍历右子树
    }
}

非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
void PreOrder(BiTree T){
    InitStack(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赋值为当前结点的右孩子
        }//else
    }//while
}

2.中序遍历

递归算法

1
2
3
4
5
6
7
void InOrder(BiTree T){
    if(T){
        InOrder(T->lchild);	//递归遍历左子树
        visit(T);		//访问根结点
        InOrder(T->rchild);	//递归遍历右子树
    }
}

非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
void InOrder(BiTree T){
    InitStack(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 = p->rchild;			//向右子树走，p赋值为当前结点的右孩子
        }//else
    }//while
}

3.后序遍历

递归算法

1
2
3
4
5
6
7
void PostOrder(BiTree T){
    if(T){
       	PostOrder(T->lchild);	//递归遍历左子树
        PostOrder(T->rchild);	//递归遍历右子树
        visit(T);		//访问根结点
    }
}

非递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PostOrder(BiTree T){
    InitStack(S);
    BiTree 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;		//转向右
            else{	//否则，弹出结点并访问
                Pop(S,p);			 //将结点弹出
                visit(p->data);		 //访问该结点
                r = p;				//记录最近访问过的结点
                p = NULL;			//结点访问完后，重置p指针
            }
        }//else
    }//while
}

4.层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
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);	//右子树不空，则右子树根结点入队
    }//while
}

第四节线索二叉树

是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到集中遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前去和直接后继。

目的：为了加快查找结点前驱和后继的速度。

空指针 = 线索数 = n+1

lchild ltag data rtag rchild

ltag

  • ​ 0 lchild域指示结点的左孩子
  • ​ 1 lchild域指示结点的前驱

rtag

  • ​ 0 rchild域指示结点的右孩子
  • ​ 1 rchild域指示结点的前驱

存储结构

1
2
3
4
5
typedef struct ThreadNode{
    ElemType data;						//数据元素
    struct ThreadNode *lchild,*rchild;		//左、右孩子指针
    int ltag,rtag;						//左、右线索标志
}ThreadNode,*ThreadTree;

第五节哈夫曼树

1.概念

树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记作：
$$
WPL = \sum_{i=1}^nw_il_i
$$
举例如下哈夫曼树，WPL = (4+2)3+52+7*1 = 35

graph TB;
A((A))
B((B))
C((C))
D((D:7))
E((E:5))
F((F:2))
G((G:4))
A-->D
A-->B
B-->C
B-->E
C-->G
C-->F

2.编码问题（左0右1）

graph TB;
A((A))
B((B))
C((C))
D((D:7))
E((E:5))
F((F:2))
G((G:4))
A--1-->D
A--0-->B
B--0-->C
B--1-->E
C--0-->G
C--1-->F
D E F G
1 01 001 000