树和二叉树

树的逻辑结构

定义

树形结构，即是从树根生长，逐级分支的结构

结点数为0的树称为空树，非空树的特性是：有且仅有一个根节点，除了根节点外，任何一个结点都有且仅有一个前驱

image-20220509152907265

子树：树可以分为m个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根节点的子树

树是一种递归定义的数据结构

结点的度：即结点孩子的数量

树的度：各结点的度的最大值

森林：m棵互不相交的树的集合

性质

  1. 结点数=总度数+1

    这个较好理解，总度数就是除了根节点之外的结点数，或者说，总度数就是树的”树枝“

    对于森林来说，结点数=总度数+树的数量

  2. 度为m的树是指结点的度的最大值，而m叉树是指，每个结点最多只能有m个孩子，实际上即使没有也可以

  3. 度为m的树的第i层至多有$m^{i-1}$个结点

    image-20220509154338974

  4. 由3可知，把每层的结点加起来，根据等比数列求和，高度为h的m叉树最多有$\frac{m^h-1}{m-1}$个结点

  5. 高度为h的m叉树至少有h个结点，高度为h，度为m的树至少有h+m-1个结点

    image-20220509154723746

二叉树的逻辑结构

定义

二叉树是n个结点的有限集合，n为0时是空二叉树，n>0时是由一个根节点和两个互不相交的被称为根的左子树和右子树组成

特点：每个结点至少只有两棵子树，左右子树不能颠倒

几种特殊的二叉树：

  1. 满二叉树

    一颗高度为h，且含有$2^h-1$个结点的二叉树

    image-20220509155321356

    只有最后一层有叶子结点，而且不存在度为1的结点

  2. 完全二叉树

    当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树

    image-20220509160245884

    最多只有一个度为1的结点，$i≤[n/2]$为分支结点，$i＞[n/2]$为叶子结点

  3. 二叉排序树（BST）

    左子树上所有结点的关键字均小于根节点的关键字

    右节点上所有结点的关键字均大于根节点的关键字

    左子树和右子树又均是一颗二叉排序树

    image-20220509160730761

  4. 平衡二叉树（AVL）

    树上任一结点的左子树和右子树的深度之差不超过1

性质

设非空二叉树中度为0,1,2的结点个数分别为$n_0,n_1,n_2$，则$n_0=n_2+1$，即叶子结点比二分支结点多一个

推导过程：已知树的结点数=总度数+1 即$n=n_1+2n_2+1$，同时$n=n_0+n_1+n_2$，所以可以推出$n_0=n_2+1$

完全二叉树

  1. 具有n个结点的完全二叉树的高度h为$log_2(n+1)$或$[log_2n]+1$
  2. 对于完全二叉树， 已知其最多只有一个度为1的结点，$n_1=0或1$，而二叉树有性质$n_0=n_2+1$,所以$n=n_1+2n_2+1$，如果完全二叉树有偶数个结点，那么$n_1$为1，奇数个为0

二叉树的存储结构

顺序存储

定义

1
2
3
4
5
struct TreeNode{
    ElemType value;
    bool isEmpty;
};
TreeNode t[MaxSize];

用数组存储二叉树的结点，一定要把二叉树的结点编号与完全二叉树对应起来

image-20220509165446882

image-20220509165426378

在最坏的情况下，二叉树为右单枝树，也至少需要$2^h-1$个存储单元，结论是二叉树的顺序存储结构，只适合存储完全二叉树

链式存储

定义

1
2
3
4
5
typedef struct BiTNode
{
    char data;
    struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;

（有两个指针域的链表罢了)

image-20220509170458898

n个结点的二叉链表共有n+1个空链域

创建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void CreateBiTree(BiTree* T)  // 双重指针，因为需要修改根节点的指向，就是需要修改root的值，所以应该传入指向root的地址，这样在被调用的函数中，对*T的操作等价于操作root
{
    char ch;
    scanf("%c", &ch);
    if (ch == '#')
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T)
            exit(-1);
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);// 递归创建
        CreateBiTree(&(*T)->rchild);
    }
}

二叉树的遍历

遍历：按照某种次序把所有结点都访问一遍

一共有4种遍历

  1. 先序遍历：对于二叉树和其子树，先访问二叉树的根节点，然后是左孩子，然后是右孩子 （根左右）
  2. 中序遍历：对于二叉树和其子树，先访问二叉树的左孩子，然后是根节点，然后是右孩子 (左根右)
  3. 后序遍历：对于二叉树和其子树，先访问二叉树的左孩子，然后是右孩子，然后是根节点 （左右根）
  4. 层序遍历：按照二叉树的分层，从左到右依次访问

先序，中序，后序遍历的代码实现（递归）：

1
2
3
4
5
6
7
8
9
10
11
//二叉树的先序，中序，后序遍历(递归)
void PreOrderTraverse(BiTree T)
{
    if (T == NULL)
        return;
  //  printf("%c ", T->data);  先序
    PreOrderTraverse(T->lchild);
  //  printf("%c ", T->data);  中序
    PreOrderTraverse(T->rchild);
  //  printf("%c ", T->data);  后序
}

可以很明显的看出，三种遍历方式的不同之处在于，在何时对二叉树结点进行操作

image-20220510140133236

对二叉树进行遍历，模拟访问路径，红色路线表示第一次访问，绿色路线表示第二次访问，紫色表示第三次访问

可以看出，第一次访问就出栈是前序遍历，第二次访问就出栈是中序遍历，第三次访问就出栈是后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 栈的顺序结构
typedef struct {
    BiTree data[MAX]; //定义一个数组，用来存储二叉树的结点指针
    int top; //定义一个整型变量，用来表示栈顶指针的位置
}Stack;  //用栈来存储结点

void preOrder(BiTree T) { //定义一个函数，用来实现非递归的前序遍历，参数是二叉树的根结点指针
    Stack s; //声明一个栈变量
    s.top = -1; //初始化栈为空，栈顶指针为-1
    BiTree p = T; //声明一个二叉树结点指针变量，用来指向当前访问的结点，初始为根结点
    while (p != NULL || s.top != -1) { //循环条件是当前结点不为空或者栈不为空，表示还有结点没有访问完
        if (p != NULL) { //如果当前结点不为空，表示还可以继续向左子树访问
            s.data[++s.top] = p; //将当前结点入栈，同时栈顶指针加一
            printf("%c ", p->data); //打印当前结点的数据，这是前序遍历的访问操作
            p = p->lchild; //将当前结点指向其左子结点，继续向左子树访问
        }
        else { //如果当前结点为空，表示左子树已经访问完毕，需要回溯到上一个结点，并访问其右子树
            p = s.data[s.top--]; //将栈顶元素出栈，并赋值给当前结点指针，同时栈顶指针减一
            printf("%c ", p->data); //打印当前结点的数据，这是中序遍历的访问操作
            p = p->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
26
27
28
29
30
31
//非递归利用顺序栈来进行后序遍历
typedef struct {
    int  data[MAX];
    int top;
}Stack1;

void postOrder(BiTree T) {
    Stack s;
    s.top = -1;
    Stack1 flagStack;   //记录每个节点访问次数栈
    BiTree p = T;
    while (p != NULL || s.top != -1) {
        if (p != NULL) {     //第一次访问，flag置1，入栈
            s.data[++s.top] = p;
            flagStack.data[s.top] = 1;
            p = p->lchild;
        }
        else {//（p == NULL）
            if (flagStack.data[s.top] == 1) {  //第二次访问，flag置2，取栈顶元素但不出栈
                p = s.data[s.top];
                flagStack.data[s.top] = 2;
                p = p->rchild;
            }
            else {         //第三次访问，出栈
                p = s.data[s.top--];
                printf("%c ", p->data);    //出栈时，访问输出
                p = NULL;      //p置空，以便继续退栈
            }
        }
    }
}

层序遍历

image-20220510144707198

需要构造一个辅助队列，如队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾，直到队列为空

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 定义层次遍历中辅助队列的结构
typedef struct queue {
    BiTree data;
    struct queue* next;
}LinkNode,*PNODE;

// 定义辅助队列的队头队尾指针
typedef struct {
    LinkNode* front, * rear;
}LinkQueue,*PQUEUE;

// 初始化队列
void InitQueue(PQUEUE Q) {
    Q->front = Q->rear = (PNODE)malloc(sizeof(LinkNode)); 
    Q->front->next = NULL;
}

// 进队操作
void EnQueue(PQUEUE Q, BiTree x) {
    PNODE s = (PNODE)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
}

// 出队操作
BiTree DeQueue(PQUEUE Q) {
    PNODE p = Q->front->next;
    if (Q->front == Q->rear)
        return NULL;
 
    Q->front->next = p->next;
    if (Q->rear == p)
        Q->rear = Q->front;

    return p->data;
}
// 层次遍历
void LevelOrder(BiTree T) {
    LinkQueue Q;
    InitQueue(&Q);
    BiTree p=NULL;
    EnQueue(&Q, T);
    while (Q.front!=Q.rear) {  //判断是否队空
        p=DeQueue(&Q);
        printf("%c ", p->data);
        if (p->lchild != NULL)
            EnQueue(&Q, p->lchild);
        if (p->rchild != NULL)
            EnQueue(&Q, p->rchild);
    }
}

根据遍历构造二叉树

根据一种遍历顺序是无法得到二叉树结构的，需要中序和其他任一遍历序列才能构造出二叉树

寻找任一二叉树结点的父节点

1
2
3
4
5
6
7
8
9
10
11
/
public TreeNode getParent(TreeNode root,TreeNode p){
   if(root == null ||root.left == p || root.right == p) return root; //树为空，或者p是root的子节点，返回root  

    TreeNode left = getParent(root.left,p); //root的左孩子 是否为p的父节点
    if(left != null) return left;  //是的话，return left，无需找右子树
    TreeNode right = getParent(root.right,p); //root的右孩子 是否为p的父节点
    if(right != null) return right;  //是的话，return right
    return left; //左右子树都不包含p，返回 null; (return right 同样是null)

 }

线索化二叉树

二叉树的问题：

  1. 建立二叉树时，n个结点的二叉树总共有2n个指针域，会有n+1个指针域被浪费
  2. 在创建二叉树的时候，大部分算法都是用递归实现，实现起来简单，然而系统运行起来却很吃力，很占用系统资源。当我们在建立好二叉树之后我们需要频繁的查找某个单元，就得频繁的调用遍历递归去查找，这显然并不高效

结合这两个问题，解决办法是用这些空指针域，存放一些有用的指向信息，从而尽量的将一棵二叉树线性化成双向链表，我们把这些指向信息称之为线索，也就是说线索二叉树等效成双向链表

中序遍历

image-20220511141151393

先序遍历

image-20220511163802955

后序遍历

image-20220511163932656

结点的定义

1
2
3
4
5
6
7
8
9
//将原来的三个域扩展到五个域
typedef struct node
{
	dataType data; //根节点的值 
	struct node *lchild; //左孩子 
	struct node *rchild; //右孩子 
	int ltag; //左标记
	int rtag; //右标记
}BiTree;

创建并初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
BiTree *creat() //二叉树的创建及初始化(初始化左右标记为0) 
{
	dataType value;
	BiTree *t;
	
	scanf("%c",&value);
	
	if(value=='#')
	{
		t=NULL;
	}
	else
	{
		t=(BiTree *)malloc(sizeof(BiTree));
		t->data=value;
		t->ltag=0;//初始化左标记为0 
		t->rtag=0;//初始化右标记为0 
		t->lchild=creat();
		t->rchild=creat();
	}
	return t;
}

中序化二叉树

  • 利用两个指针p和pre，让其在中序遍历的过程中分别指向一前一后，也就是说始终保持p是pre的后继，pre是p的前驱；那么在处理到p结点的时候，我们可以根据p节点是否有左孩子来判断，p->lchild是否要指向前驱，若p指向的节点没有左孩子，则直接让p->lchild=pre;并将p->ltag赋值为1，即可完成将结点的左孩子指向前驱结点。pre也一个道理，若pre所指向的节点没有右孩子，将pre->rchild=p;并即将pre->rtag赋值为1，即可完成该结点的右孩子指向后继节点
  • 整体思路就是：通过p来处理左孩子指向前驱（左孩子为空的情况下），通过pre来处理右孩子指向后继（右孩子为空的情况下）

pre与p指针功能相同，但定义却不相同，p是线索化函数内的局部变量，而pre为了保证在每一次递归序列中能够正确返回当前值，必须定义成全局变量 

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
26
27
28
29
30
31
32
33
34
35
36
37
38
//因为我们是以中序遍历的顺序给二叉树填上线索，所以，整个线索化的函数是套用在中序遍历的框架下的。
// 线索化二叉树就是给二叉树的基础上，添加能完整表示出二叉树节点前驱后继的指针
BiTree *pre=NULL; //定义全局变量pre

void InThreaded(BiTree* p)
{
	if (p!=NULL)
	{
        //	  后序化二叉树
	   //InThreaded(p->lchild);  递归遍历右子树
       //InThreaded(p->rchild);  递归线索化左子树
	
		InThreaded(p->lchild); // 递归线索化左子树，直到找到首结点

		if (p->lchild==NULL)   //如果当前结点没有左子树，那么需要给其添加前驱的指针
		{
			p->ltag = 1;       //标志为1，表示其前驱
			p->lchild = pre;    // 那么当前结点的前驱就是pre
		}
            // 如果上个结点没有右子树，那么他的后继就是p，即当前结点
		if (pre!=NULL && pre->rchild==NULL) 
            // 如果当前结点的前驱不是NULL，或者前驱的右孩子不存在
		{
			pre->rtag = 1;              // 标志为1，表示为后继    
			pre->rchild = p;            // 那么前驱的后继就是当前结点
		}
		pre = p;    //下一个结点
	/*	  先序化二叉树
	    InThreaded(p->rchild);  //递归遍历右子树
                if(p.ltag==0){    //为了避免循环
         InThreaded(p->lchild); // 递归线索化左子树
        }
	*/
	}
        
        
	}
}

查找后继

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BiTree* Next(BiTree* t) //已知节点t找t的"后继"结点位置 
{
	if (t->rtag == 1) //右标志为1，可以直接得到"后继"结点 
	{
		t = t->rchild;
	}
	else /*右标志为0，不能直接的到"后继"结点，
		   则需要找到右子树最左下角的节点*/
	{
		t = t->rchild;
		while (t->ltag == 0)
		{
			t = t->lchild;
		} //while
	}//else
	return t;
}

查找前驱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
BiTree* Prior(BiTree* t)//已知节点t找t的"前驱"结点位置 
{
	if (t->ltag == 1)//左标志为1，可以直接找到"前驱"结点的位置 
	{
		t = t->lchild;
	}
	else /*左标志为0，不能直接的到"前驱"结点，
		   则需要找到左子树最右下角的节点*/
	{
		t = t->lchild;
		while (t->rtag == 0)
		{
			t = t->rchild;
		} //while
	} //else

	return t;
}

利用线索实现中序遍历

但是需要注意的一点是，我们creat函数中输入是以先序的次序输入端，故p一开始指向的节点是先序的第一个节点，而不是中序的第一个结点，所以要先查找第一个节点，在用Next中的线索查找后续结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InorderTraverse(BiTree *t)//利用线索实现中序遍历 
{
	if(!t)
	{
		return;
	}
	
	while(t->ltag==0)//查找第一个节点 
//因为二叉树的创建creat是以先序遍历序列创建，所以t所指向的第一个结点并不是中序遍历所要访问的第一个结点 
{
		t=t->lchild;
	}
	printf("%c ",t->data);//访问第一个结点
	while(t->rchild)
// 此处以"t的右孩子不为空"为循环条件，是因为，先前设定了最后一个结点的"后继"为空，表示结束 
	{               //根据线索访问后续结点 
		t=Next(t);
		printf("%c ",t->data); 
	}
 }

在中序遍历中，左根右的顺序，任意一结点可以找到前驱和后继

在前序遍历中，根左右的顺序，有左孩子的结点是无法找到其前驱的

在后序遍历中，左右根的顺序，有右孩子的结点是无法找到其后继的

image-20220511164049416

树的存储结构

双亲表示法（顺序存储）

每个结点中保存自身数据以及指向父节点的位置

定义

1
2
3
4
5
6
7
8
typedef struct Tree{
    ElemType data;  //数据元素
    int parent;     //双亲位置域
}TreeNode;
typedef struct Ptree{         //存放树的顺序表
    TreeNode nodes[size];   //双亲表示
    int n;               //结点数
}PTree

优点：查指定结点的双亲很方便

缺点：查指定结点的孩子只能从头遍历

孩子表示法（顺序＋链式）

顺序存储各个结点，每个结点中保存孩子链表头指针

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
struct CTNode{     
    int child ;       //孩子结点在数组中的位置
    struct CTNode *next; //下一个孩子
}
typedef struct {              //结点定义，包括数据和孩子的链表	
 ElemType data;
 struct CTNode *firstChild ;  //第一个孩子
}CTBox;
typedef struct {                     //存放结点的顺序表
    CTBox nodes[MAXSIZE];
    int n,r;               //结点数和根的位置
}CTree;

优点：查指定结点的孩子很方便

缺点：查指定结点的父节点只能从头遍历

孩子兄弟表示法（链式存储）

其定义和二叉树一模一样，不过是指针域指向的对象不一样

1
2
3
4
typedef struct CSNode {
    ElemType data;
    struct CSNode  *firstchild,*nextsibling;   //第一个孩子和右兄弟
}CSNode,*CSTree;

关键在于，这种表示法可以将树转化为二叉树，从而可以用熟悉的二叉树的操作来操作树

image-20220511171632428

而对森林来说，则可以将几颗树的头结点相连，再用孩子兄弟表示法表示即可

树的遍历

先根遍历

如果树非空，先访问根节点，然后依次访问其子树，对树的先根遍历和对其转换二叉树的先序遍历结果是一样的

后根遍历

若树非空，先依次对每棵树进行后根遍历，最后再访问根节点，对树的后根遍历和对其转换二叉树的中序遍历结果是一样的

层序遍历

按照层次访问树，可以看做对树的广度优先遍历（BFS）

image-20220511184038119

哈夫曼树

定义

当有 n 个结点（都做叶子结点且都有各自的权值）构建一棵树时，如果构建的这棵树的带权路径长度(WPL)最小，称这棵树为“最优二叉树”，有时也叫“哈夫曼树“

权值可以理解为是访问频率，而带权路径长度=权值 x 该节点到树根的路径长度

树的带权路径长度=所有叶节点的带权路径之和WPL(Weighted Path Length)

构建

  1. 选取并合并：选取取值最小的两个结点合并成一棵树（根节点为权值之和）

  2. 删除并加入：从序列中删除上述选取的两个两个最小结点，加入新合并的树，新合并的树权值为两结点之和

  3. 加入：选择两个结点，和第2步合并的结点，一共三个节点，选择其中最小的两个结点合并，组成新合并的树

  4. 继续重复上述操作即可得到哈夫曼树

    image-20220512161945398

哈夫曼树并不唯一，但是WPL的值肯定是唯一的

哈夫曼编码

即任一一个编码不能是其他编码的前缀，将字符集中的每个字符作为一个叶子结点，各个字符出现的频率作为结点的权值，可用于数据压缩

并查集

逻辑结构

并指合并操作，查指查找操作，集指采用集合这种逻辑结构，并查集就是可以进行合并和查找的集合

image-20220523195741382

森林就将各个元素划分为若干个互不相交的子集

在森林中，查指在森林中查找某一结点属于那个集合，并指两棵树的合并

存储结构

存储结构采取双亲表示法可以方便地实现并查

image-20220523200019796

用一个数组就可以表示集合关系

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
26
#define SIZE 13
int UFSets[SIZE];
// 初始化并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++){
    S[i]=-1;         
    }
}

//Find 查操作
int Find(int S[],int x){ 
    while(S[x]>=0)   ////循环查找x的根
    {   
    x=S[x];
    return x;
     }
}
//Union 并操作  将两个集合合并成一个
void Union(int S[],int Root1,int Root2){
    if(Root1==Root2){
          return ;
    }else{
       S[Root2]=Root1
    }
}

并操作给出了两棵树的根节点，合并的时间复杂度只需要O(1)

查操作的时间复杂度在O(n)

查操作的时间复杂度和树的高度有关，可以优化并的操作，让小树成为大树的子树，从而尽量不增加树的高度

优化思路：在每次Union操作构建树的时候，用根的绝对值表示树的结点总数

1
2
3
4
5
6
7
8
9
10
11
12
13
//Union 并操作  将两个集合合并成一个
void Union(int S[],int Root1,int Root2){
    if(Root1==Root2){
          return ;
    }
    if(S[Root2]>S[Root1]{  //Root2结点数更少
       S[Root1]+=S[Root2];  //累加结点总数
       S[Root2]=Root1;     //合并
    }else{
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
}

优化后find操作的最坏时间复杂度为$O(log_2n)$

Find操作可以继续优化，如果不考虑保持树的结构，可以将尽可能多的树挂靠在根节点之下，从而可以更快查到根节点

image-20220523202958232

压缩路径可以将被查找节点到根节点路径中的所有结点都挂靠在根节点之下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Find 查操作 压缩路径
int Find(int S[],int x){ 
    int root =x;
    while(S[root]>=0)   ////循环查找x的根
    {   
    root =S[root];
    }
    while(x!=root){   //压缩路径
        int t=S[x];   //t指向x的父节点
        S[x]=root;    //x挂到根节点下
        x=t;          //回到x的父节点
    }
    return root;
}