数据结构第三周笔记——树(上)(慕课浙大版本--XiaoYu)

3.1 树与树的表示

什么是树

1. 人类社会家谱，社会组织结构，图书信息管理都是树的一种体现(层次型的组织结构)
2. 分层次组织在管理上具有更高的效率

1. 数据管理的基本操作之一：查找

3.1.1 引子(顺序查找)

查找(Searching)

查找：根据某个给定关键字K，从集合R中找出关键字与K相同的记录
  静态查找：集合中记录是固定的
    没有插入和删除操作，只有查找(例如查字典)
  动态查找：集合中记录是动态变化的
    除查找，还可能发生插入和删除

静态查找

方法1：顺序查找

int SequentialSearch (List Tbl,ElementType K)
{
  //  在Element[1]~Element[n]中查找关键字为K的数据元素
    int i;
    Tbl->ElementP[0] = K;//建立哨兵
    for(i = Tbl->Length;Tbl->Element[i] != K;i--);//倒过来做的，从下标大的地方开始往前循环
    return i;//查找成功返回所在单元下标;不成功不返回0
}
typedef struct LNode{
    ElementType Element[MAXSIZE];//决定了放的元素有多少个
    int Length;
};
顺序查找的一种实现(无"哨兵")
    int SequentialSearch (List Tbl ,ElementType K)
{
    //在Element[1]~Element[n]中查找关键字为K的数据元素
    int i;
    for(i=Tbl->Length; i>0 && Tbl->Element[i] != K;i--);
    return i;//查找成功返回所在单元下标，不成功返回0
}
在顺序查找中,如果把下列程序中的循环条件"i>0"去掉，会发生什么后果？
    答案：要查找的元素不存在时发生数组越界（i指向小于0的位置）
    "哨兵"的作用:可以在数组的最后或者边界上面设一个值，不用每次去判断它的下标是不是达到我的边界。根据for循环，当碰到我们放置的那个值的时候，循环就该退出来了。这样我们在写判断的时候就可以少写一个判断的分支
        我的理解是这个哨兵通常放置在下标0的地方，然后循环从大往小循环，循环到1如果都没有我们需要的值的时候，放在下标0的地方的哨兵是等于我们需要的值来退出循环，代替了for条件中的不能小于0，防止for循环陷入死循环或者说越界跑到下标负数的地方去了。然后返回值如果是0的话我们就心知肚明没有找到我们想要的值了
        这种顺序查找算法的时间复杂度为O(n)，平均数是n/2

3.1.2 引子(二分查找例子)

方法3：二分查找(Binary Search)

使用前提：有序存放

例子：假设有13个数据元素，按关键字由小到大顺序存放，二分查找关键字为444的数据元素过程如下：

两个边界分别是left跟right
具体过程数据就不展示了，用图片展示出来了，减少我的工作量
在13个元素的二分查找中，找第10个元素比找第8个元素快?对

例子2：仍然以上面13个数据元素构成的有序线性表为例，二分查找关键字为43的数据元素如下：

3.1.3 引子(二分查找实现)

二分查找算法

int BinarySearch(List Tbl,ElementType K)//List Tbl是结构的指针，包含了数组Element和它的大小Length
{
  //在表Tbl中查找关键字为K的数据元素
    int left,right,mid,NoFound = -1;
    left = 1;//初始左边界
    right = Tbl->Length//初始右边界
        while(left <= right)
        {
            mid = (left + right)/2 //计算中间元素坐标
            if(K < Tbl->Element[mid])   right = mid - 1;//调整右边界
            else if(K > Tbl->Element[mid]) left = mid + 1;//调整左边界
            else return mid;//查找成功，返回数据元素下标
        }
    return NotFound;//查找不成功，返回-1
}
所以我们就return NotFound
在二分查找的程序实现中，如果left和right的更新不是取mid+1和mid-1而是都取mid，程序也是正确的?当然是错误的啦
//List定义: List是stl实现的双向链表,与向量(vectors)相比, 它允许快速的插入和删除,但是随机访问却比较慢。使用时需要添加头文件 #include

二分查找算法具有对数的时间复杂度O(logN)

11个元素的二分查找判定树

二分查找的启示：

1. 判定树上每个结点需要的查找次数刚好为该结点所在的层数
2. 查找成功时的查找次数不会超过判定树的深度
3. n个结点的判定树的深度是[log2n]+1 (这里的2是下标)
4. ASL（平均成功查找次数） = (4 4 + 4 3 + 2 * 2 +1)/11 = 3

3.1.4 树的定义和术语

当在树里面插入结点 删除结点的时候比在数组里面方便得多

树的定义

树(Tree)：n(n >= 0)个结点构成的有限集合。

当n = 0时，称为空树;

对于任一棵非空树(n > 0)，它具备以下性质：

1. 树中有一个称为"根(Root)"的特殊结点，用r表示;
2. 其余结点可分为m(m>0)个互不相交的有限集T1，T2,....,Tm,其中每个集合本身又是一颗树，称为原来树的"子树(SubTree)"
3. 网络异常，图片无法展示

   |

树与非树

不是树的例子

1. 网络异常，图片无法展示

   |
2. 子树是不相交的;
3. 除了根结点外，每个结点有且只有一个父结点;
4. 一颗N个结点的树有N-1条边
5. 树是保证结点联通的最小的一种连接方式(边最少)
6. 有一个m棵树的集合（也叫森林）共有k条边，问这m颗树共有多少个结点？k+m

树的一些基本术语

1. 结点的度(Degree)：结点的子树个数
2. 树的度：树的所有结点中最大的度数
3. 叶结点(Leaf):度为0的结点
4. 父结点(Parent)：有子树的结点是其子树的根节点的父节点
5. 子结点(Child)：若A结点是B结点的父节点，则称B结点是A结点的子结点;子节点也称孩子结点
6. 兄弟结点(Sibling)：具有同一父节点的各结点彼此是兄弟结点
7. 网络异常，图片无法展示

   |
8. 祖先结点(Ancestor)：沿着树根到某一结点路径上的所有结点都是这个结点的祖先结点
9. 子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙
10. 结点的层次(Lever)：规定根节点在1层，其他任一结点的层数是其父节点的层数加1
11. 树的深度(Depth)：树的所有结点中的最大层次是这颗树的深度

3.1.1 树的表示

数组实现：把这些结点按顺序存储在数组里面

链表表示：

这样树的结构：每个结点的结构的样子是不一样的。有的结点有3个指针，有的结点有1个指针，有的没有指针。这样整个这个结构的形式都不一样，会给后面的程序实现带来困难(因为访问之前没办法确认会带来多少个儿子)

//另外的构想：能不能为了保持结构的统一，我将每个指针都跟结点中最多的对齐，其他结点不需要的指针就当空指针用。这样的好处就是所有树结点结构是统一的，程序处理起来方便。但同样会带来问题：
//如果这个树有n个结点，那意味着每个结点有3个指针域，整个树会有3n个指针域，而实际上我们的边只有n-1条,这样就会有2n+1个指针域是空的，造成空间上的浪费

儿子-兄弟表示法

这样可以将整颗树的结点把它串起来

实现效果如下：

这种方法的优点:
1.树种的每个结点结构都是统一的，都是两个指针域，同时它的空间浪费也不大
  n个结点2n个指针域 其中n-1条边。
  意味着n-1个域是非空的，真正空的域是n+1
  问题：在用“儿子-兄弟”法表示的树中，如果从根结点开始访问其“次子”的“次子”，所经过的结点数与下面哪种情况一样？(注意:比较的是结点数,而不是路径)
  答案：从根结点开始访问其“长子”的“长子”的“长子”的“长子”

二叉树的图

二叉树特点：

1. 链表实现方法：旋转45度
2. 每个结点都有两个指针，一个指向左边一个指向右边，每个结点最多是两个儿子
3. 二叉树就是度为2的一种树
4. 网络异常，图片无法展示

   |