DS博客作业03--树

0.PTA得分截图

1.本周学习总结（0-5分）

1.1 总结树及串内容

串

• 定义：n个或多个字符组成的有限序列。
• 定长顺序存储表示
  顺序串：用一组地址连续的存储单元存储串值的字符序列可以用一个数组表示
  定义：

typedef struct
{
   char data[MaxSize];/*存字符串，其中MaxSize为最大长度*/
   int length;/*存字符串长度*/
}SqString;

• 堆分配存储表示
  不同：它的存储空间是在执行程序过程中动态分配的。
  定义：

typedef struct
{
   char *ch;/*为空是NULL，不为空，按串长度分配存储区域*/
   int length;/*存字符串长度*/
}HString;

• 基本运算：
  • StrAssign(&s,cstr):将字符串常量cstr赋给串s，即生成其值等于cstr的串s。
  • StrCopy(&s,t):串的复制。将串t赋给串s。
  • StrEqual(s,t):判断串是否相等。如果相等返回真，不等返回假。
  • StrLength(s):求串的长度。返回串s中字符的个数。
  • Concat(s,t):串的连接。返回由串s和串t连接在一起形成的新串。
  • SubStr(s,i,j):求子串。返回串s中从第i个（1≤i≤n）字符开始的、由连续j个字符组成的子串。
  • InsStr(s1,i,s2):插入。将串s2插入到串s1的第i个字符中（1≤i≤n+1），即将s2的第一个字符作为s1的第i个字符，并返回产生的新串。
  • DelStr(s,i,j):删除。从串s中删去第i个字符（1≤i≤n）开始的长度为j的子串，并返回产生的新串。
  • RepStr(s,i,j,t):替换。在串s中，将第i个字符（1≤i≤n）开始的第j个字符构成的子串用串t替换，并返回产生的新串。
  • DispStr(s):输出。输出串s的所有元素的值。
• 链式:没有顺序串操作灵活，它比较复杂
  • 节点定义：

typedef struct snode
{
   char data;
   struct snode *next;
}LiString;

string类(C++)

• 优点：不必担心内存是否足够、字符串长度等，它包含了很多实用的函数
• 头文件：#include<string>
• 声明：string 字符串名
• 输入区别：getline(cin,s):读取一行字符串；cin>>s:读取空格前的字符

串的BFKMP算法

• 功能：找到主串中子串第一次出现的位置。

BF算法

• 思路：

定义i和j分别表示主串和子串中字符的下标
while i<主串长度且j<子串长度
  if i所表示的主串中的字符与j所表示的子串字符相等
    下标i和j分别自增1
  end if
  else 
    重新开始新的匹配，i从初始匹配的下一个开始，即i=i-j+1;
    j从初始位置开始，即j=0；
  end else
end while
if j>=子串长度
  返回初始位置即i-子串长度
end if
else 
  说明未找到，返回对应数字表示寻找失败
end else

• 具体代码：
  

• 图示：
  
  注：最后那个是“第六次趟”。

• 最坏情况，时间复杂度O(n)=子串长度*主串长度；空间复杂度为O(1)

KMP算法

• 改进：主串指针i不需要回溯

• 思路：对BF算法的改进，增加了一个next数组，存放匹配失败时，模式串下一次匹配的位置。

• 求next：
  

• 图示：
  
  

• 代码：
  

• 对next的改进：（nextval）
  

• 改进后的图示：
  
  

二叉树

• 定义：每个结点最多有两个子树的树结构。
• 性质：
  • 在非空二叉树中，第i层的结点总数不超过 2^(i-1),(其中i>=1)；
  • 深度为h的二叉树最多有(2^h)-1个结点(其中h>=1)，最少有h个结点；
  • 对于任意一棵二叉树，如果其叶结点数为N₀，而度数为2的结点总数为N₂，则N₀=N₂+1
  • 具有n个结点的完全二叉树的深度为（log₂n）+1
• 类型：
  • 完全二叉树：若设二叉树的高度为h，除最后一层外，其它各层 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
  • 满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

二叉树存储结构

• 顺序存储：首先对该树中的每个结点进行编号，编号作为下标，把各结点的值对应下标存储到一个数组中。比如说，树根结点的编号为1，接着按照从上到下和从左到右的次序编号。（要补齐空结点）
  
• 特点：
  • 各个结点的关系可以根据下标求出来，比如下标为i的结点，左孩子是2i，右孩子是2i+1，双亲是i/2
  • 它用于存完全二叉树是很好的，这样可以最大限度地利用空间，不需要补齐那么多的空结点；但是如果遇到单分支很多的树，会浪费很多空间。
• 链式存储：
• 定义：

typedef struct BiTNode {
	char data;/*结点的数据*/
	struct BiTNode* lchild, *rchild;/*左右孩子的指针*/
}BTNode,*BTree;

• 特点：
  • 用指针对应关系，以上的定义便于寻找左右孩子，但是不好找双亲，当然，也可以加一个parent的指针，便于寻找双亲。结构体定义还是需要根据具体情况具体要求来定义。

二叉树的建法

• 层次建：
  
• 先序建：
  
• 根据先序和中序建：（后序类似）
  

二叉树的遍历及应用

• 分类：先序遍历、中序遍历、后序遍历；

  • 先序：根左右；
  • 中序：左根右；
  • 后序：左右根。

• 先序:
  

• 中序：
  

• 后序：
  

• 求树的高度
  

树的结构、操作、遍历及应用

• 定义：它是由n（n>=0）个有限结点组成一个具有层次关系的集合。
• 存储：（根据具体情况选择适合的存储结构）
• 双亲存储结构：便于寻找双亲，不利于找孩子

 typedef struct 
{　 ElemType data;/*结点数据*/
　   int parent;/*指向双亲*/
} PTree[MaxSize];

• 孩子链：孩子的数量不确定，可能大可能小，如果空结点过多，很浪费空间。便于找孩子，不利于找双亲.

typedef struct node
{      ElemType data;/*结点数据*/
        struct node *sons[MaxSons];/*存孩子*/
}  TSonNode;

• 孩子兄弟链：便于找孩子，不利于找父亲，但是比孩子链好在不会浪费太多空间。

typedef struct tnode 
{      ElemType data;/*结点数据*/
        struct tnode *son;/*指向孩子*/
        struct tnode *brother;  2/*指向兄弟，同层的结点*/
} TSBNode;

• 遍历分类：先序遍历、中序遍历、后序遍历；
  • 先序：根左右；
  • 中序：左根右；
  • 后序：左右根。

线索二叉树

• 定义：在二叉树的结点上加上线索的二叉树称为线索二叉树。每个节点有两个指针域，n个结点总共有2n个指针域，非空链域为n-1个，空链域有n+1个
• 结构体定义：

typedef struct BiTNode {
	char data;
	int ltag ;/*标记是否有左孩子,0表示有孩子，1表示没有孩子（有线索）*/
	int rtag;/*标记是否有右孩子*/
	struct BiTNode* lchild, *rchild;
}BTNode,*BTree;

• 操作：
  • 若结点有左子树，则lchild指向其左孩子，没有则指向它的前驱(线索)；
  • 若结点有右子树，则rchild指向其右孩子，没有则指向其后继(线索) 。
• 根据顺序的不同，分为先序线索二叉树、中序线索二叉树、后序线索二叉树。
• 如：（先序线索二叉树）
  

哈夫曼树、并查集

• 定义：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。
• 结点的带权路径长度：从根结点到该结点之间的路径长度（所在层数-1）与该结点的权的乘积。
• 原则：权值越大越靠近根结点，越小越远离根结点。
• 构造过程：
  • 找到权值最小的两个结点组合成一个二叉树，这个二叉树的根节点的权值为两个结点权值的和。
  • 删除原来的那两个结点，把二叉树根结点放入。
  • 重复以上操作直到构成一颗树。
• 如：
  
• 结构体定义：

typedef struct
{
    char data;/*节点值*/
    float weight;/*权重*/
    int parent;/*双亲节点*/
    int lchild;/*左孩子节点*/
    int rchild;/*右孩子节点*/
}HTNode;

并查集：

• 结构体定义：

typedef struct node
{
    int data;/*结点对应人的编号*/
    int rank;/*结点秩：子树的高度，用于合并*/
    int parent;/*结点对应的双亲下标*/
}UFSTree;   

• 并查集树的初始化：

void MAKE_SET(UFSTree t[]，int n)/*初始化并查集树*/
{
	int i;/*循环计数*/
	for (i = 1; i <= n; i++)
	{
		t[i].data = i;/*数据为该人的编号*/
		t[i].rank = 0;/*秩初始化为0*/
		t[i].parent = i;/*双亲初始化指向自已*/
	}
}

• 查找一个元素所属的集合

int FIND_SET(UFSTree t[], int x)
{
	if (x != t[x].parent)    /*双亲不是自己*/
	{
		return(FIND_SET(t, t[x].parent));/*递归在双亲中找x*/
	}
	else
	{
		return(x);    /*双亲是自己，返回x*/
	}
}

• 两个元素各自所属的集合的合并

void UNION(UFSTree t[]，int x，int y)/*将x和y所在的子树合并*/
{
	x = FIND_SET(t，x);/*查找x所在分离集合树的编号*/
	y = FIND_SET(t，y);/*查找y所在分离集合树的编号*/
	if (t[x].rank > t[y].rank)/*y结点的秩小于x结点的秩*/
	{
		t[y].parent = x; /*将y连到x结点上，x作为y的双亲结点*/
	}
	else/*y结点的秩大于等于x结点的秩*/
	{
		t[x].parent = y; /*将x连到y结点上，y作为x的双亲结点*/
		if (t[x].rank == t[y].rank)/*x和y结点的秩相同*/
		{
			t[y].rank++;/*y结点的秩增1*/
		}
	}
}

1.2.谈谈你对树的认识及学习体会。

在最开始学习它的时候，它其实是很抽象的。在之前解决迷宫问题的时候，我就有过类似的念头，那会儿虽然还不知道树到底是什么，但是它这个名字其实还是很形象的。迷宫问题，它有每走一步，都要面临选择，这其实也可以用树来表示。每一个格子接下来可以走的方向都是它的孩子，这应该也能够建成一棵树，然后根据迷宫出口位置所在树的深度来判断最短路径。当然，我现在可能对树的应用还不是很熟练。就感觉课件上老师的代码好像就很简洁、很方便，然后我自己想的就很麻烦，还容易错。有时候知道思路，但是体现在代码上，却不太能够表达出我的想法。还是需要再理解和练习啊。

2.阅读代码（0--5分）

2.1 题目及解题代码

• 题目：
  
• 代码：
  

2.1.1 该题的设计思路

• 分析与思路：根据题目可以知道，它所给的树的序列，左子树比根节点小，右子树比根节点大，三者都小于双亲结点，如果按照中序来看，就是从小到大的有序序列，所以说，按照中序数到对应的树节点即可。
• 
• 时间复杂度：最坏情况，寻找的是第n个最小的数（即最大数），O(n);
• 空间复杂度：最坏情况，寻找的是第n个最小的数（即最大数），O(n).

2.1.2 该题的伪代码

定义一个函数dfs用于寻找第k个最小的数，形参i为第i小的数
 if 树为空或是已找到 
	 直接return
 end if
 调用dsf函数，在左子树中寻找第k个最小值
 if 找到
	 根节点对应数据赋值给res
	 更改find，令它为true
	 直接返回
 end if
调用dsf函数，在右子树中寻找第k个最小值

2.1.3 运行结果

2.1.4分析该题目解题优势及难点。

• 优势：我们学过中序，这道题只要知道它与中序有关，有迹可循，就基本得到了答案。
• 难点：难也是难在要发现它是按照中序输出来排列大小的顺序的。但是这题它其实给了我们图，就比较容易发现。

2.2 题目及解题代码

可截图，或复制代码，需要用代码符号渲染。题目截图后一定要清晰。

• 题目：
  

• 代码：
  

2.2.1 该题的设计思路

• 思路：类似于层次遍历，但是不同的是，它需要转变方向。用了两个栈，先存一层到一个栈中，然后这个栈的节点出栈，在输出之后，把它的孩子存入另外一个栈中，栈的特点是先进后出，它的这个特性刚刚好解决了题目所要求的一层转换一次顺序。
  

• 时间复杂度:树节点为n，进栈一次出栈一次，O(2n);

• 空间复杂度:因为需要栈存放每层结点，需要2个栈。如果树每层最大结点树m，最坏情况，O(2m).

2.2.2 该题的伪代码

定义两个栈s1，s2
判断树是否为空，为空直接返回
将树的根节点入s1栈
while s1或s2中有一个不为空
   while s1不为空
	   取s1栈顶，然后出栈栈顶元素，并将其输出，（代码中是存入输出序列out）
	   如果这个栈顶左子树不空，将左子树入s2栈；右子树也一样
   end while
  （参考代码中在这输出了out）
   while s2不为空
	   与上述操作一样，不过是存入栈s1中
   end while
end while

2.2.3 运行结果

2.2.4分析该题目解题优势及难点。

• 优势：这题与层次遍历类似，但又略有不同。但是我们学过栈和队列，利用好它们作为暂时存储的工具，对解题有很大帮助。
• 难点：怎样做到一层转换一次输出的方向是这题的主要难点。

2.3 题目及解题代码

• 题目：
  

• 代码：
  

2.3.1 该题的设计思路

• 思路：找到每一层不为空的第一个节点和不为空的最后一个节点，记住二者下标然后二者下标相减的结果加上1，每层的宽度与最大值相比取较大值；
  

• 时间复杂度：遍历一次，O(n);

• 空间复杂度：树节点数n,O(n)。

2.3.2 该题的伪代码

定义队列q存树的结点
将树的根节点入队
while 队列不为空
  取队列长度size和队首的下标pos
  for 0 to size
	  取当前队首curr
	  if 当前队首的左子树不空
		  左子树入队，下标为2*队首下标-pos
	  end if
	  if 当前队首的右子树不空
		  右子树入队，下标为2 * 队首下标+1 - pos
      end if
	  比较当前队首-pos和width的值取较大值赋给width
end while

返回值为width

2.3.3 运行结果

2.3.4分析该题目解题优势及难点。

• 优势：有点类似于求树的深度，思路上可以参考。
• 难点：如何确定最后不为空的那个结点的位置。

2.4 题目及解题代码

• 题目：
  
• 代码：
  

2.4.1 该题的设计思路

• 思路：遍历整个树，如果某个结点值为0且子树中没有一个为1，则需要将这个结点置为0；
  

• 时间复杂度:O(n),n为树结点个数；

• 空间复杂度:O(h),h为树的高度。

2.4.2 该题的伪代码

定义一个函数Pruning来将不符合题意的结点去掉
if 树为0
   返回错误（即false）
end if
令a1和a2分别为左右子树调用Pruning函数所得结果
if a1为假
 将左节点置为null
end if
if a2为假
 将右节点置为null
end if
返回值为判断语句（结点对应数据是否为1或者a1为真或者a2为真）

2.4.3 运行结果

2.4.4分析该题目解题优势及难点。

• 优势：顺序输入需要层次建树，这是我们学过的，对树的遍历没有要求，只是最后输出需要层次遍历。
• 难点：我认为递归函数出口怎么写是这题的难点，其他的还是比较基础的。