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

3.1 树与树的表示

什么是树

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

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

3.1.1 引子(顺序查找)

查找(Searching)

查找：根据某个给定关键字K，从集合R中找出关键字与K相同的记录

   静态查找：集合中记录是固定的

       没有插入和删除操作，只有查找(例如查字典)

   动态查找：集合中记录是动态变化的

       除查找，还可能发生插入和删除

静态查找

方法1：顺序查找

intSequentialSearch (ListTbl,ElementTypeK)

{

   //  在Element[1]~Element[n]中查找关键字为K的数据元素

   inti;

   Tbl->ElementP[0] =K;//建立哨兵

   for(i=Tbl->Length;Tbl->Element[i] !=K;i--);//倒过来做的，从下标大的地方开始往前循环

   returni;//查找成功返回所在单元下标;不成功不返回0

}

typedefstructLNode{

   ElementTypeElement[MAXSIZE];//决定了放的元素有多少个

   intLength;

};

顺序查找的一种实现(无"哨兵")

   intSequentialSearch (ListTbl ,ElementTypeK)

{

   //在Element[1]~Element[n]中查找关键字为K的数据元素

   inti;

   

   for(i=Tbl->Length; i>0&&Tbl->Element[i] !=K;i--);

   returni;//查找成功返回所在单元下标，不成功返回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 引子(二分查找实现)

二分查找算法

intBinarySearch(ListTbl,ElementTypeK)//List Tbl是结构的指针，包含了数组Element和它的大小Length

{

   //在表Tbl中查找关键字为K的数据元素

   intleft,right,mid,NoFound=-1;

   

   left=1;//初始左边界

   right=Tbl->Length//初始右边界

       while(left<=right)

       {

           mid= (left+right)/2//计算中间元素坐标

           if(K<Tbl->Element[mid])   right=mid-1;//调整右边界

           elseif(K>Tbl->Element[mid]) left=mid+1;//调整左边界

           elsereturnmid;//查找成功，返回数据元素下标

       }

   returnNotFound;//查找不成功，返回-1

}

所以我们就returnNotFound

在二分查找的程序实现中，如果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. 网络异常，图片无法展示

   |
   
   

二叉树及存储结构

3.2.1 二叉树的定义及性质

二叉树的定义

   二叉树T:一个有穷的结点集合

•       这个集合可以为空

       若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成(L和R是下标)

二叉树具体五种基本形态

二叉树的子树有左右之分

特殊的二叉树

斜二叉树(Skewed Binary Tree)

1. 只有左边或者只有右边，相当于一个链表
   
2. 网络异常，图片无法展示

   |
   
   

完美二叉树(Perfect Binary Tree)

或者叫做满二叉树(Full Binary Tree)

特点：一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。 满二叉树

完全二叉树(Complete Binary Tree)

有n个结点的二叉树，对树种结点按从上到下，从左到右的顺序进行编号，编号为i(1 <= i <= n)结点与满二叉树中编号为i结点在二叉树中位置相同

跟上方的区别就是除了最底下一层可以右边缺一点，上面跟满二叉树是一样的。最底下一层左边顺序不能乱

二叉树的几个重要性质

叶结点的总数等于有两个儿子的结点的总数加1

有一颗二叉树，其两个儿子的结点个数为15个，一个儿子的结点个数为32个，问该二叉树的叶结点个数是多少？

16

二叉树的抽象数据类型定义

类型名称：二叉树

数据对象集：一个有穷的结点集合。

   若不为空，则由根结点和其左、右二叉子树组成。

   

操作集：BT属于BinTree,Item属于ElementType

重要操作有：

1.BooleanIsEmpty(BinTreeBT)：判别BT是否为空;

2.voidTraversal(BinTreeBT)：遍历，按某顺序访问每个结点;(重要)

3.BinTreeCreateBinTree():创建一个二叉树

常用的遍历方法

1.voidPreOrderTraversal(BinTreeBT)://先序--根、左子树、右子树

2.voidInOrderTraversal(BinTreeBT)://中序--左子树、根、右子树

3.voidPostOrderTraversal(BinTreeBT)://后序--左子树、右子树、根

4.voidLevelOrderTraversal(BinTreeBT)://层次遍历(层序遍历,从上到下、从左到右

3.2.2 二叉树的存储结构

1.顺序存储结构

完全二叉树：按从上至下，从左到右顺序存储n个结点的完全二叉树的结点父子关系;

//这个树最适合数组方式解决

1. 非根结点(序号 i > 1)的父节点的序号是[i/2]

1. 这句话的意思就是说假设我们目前知道M结点时6，如果想知道它的父节点就是6/2=3，Q结点就是7/2=3.5，把小数去掉，父节点一样是3
   

2. 结点(序号为i)的左孩子结点的序号是2i，(若2i <= n,否则没有左孩子)

1. 举例：意思就是B左孩子是C,O的左孩子是M
   

3. 结点(序号为i)的右孩子结点的序号是2i+1，(若2i+1 <= n,否则没有右孩子)

1. 举例：类似上方的意思B右孩子是S...
   

一般二叉树也可以采用这种结构，缺点：但会造成空间浪费....(将缺少的结点补上一个空结点)

问题：

如果参照完全二叉树的表示方法用数组存储下面这棵二叉树，那么结点e所对应的数组下标是多少（树根下标为1）？

答案：6

2.链表存储

typedefstructTreeNode*BinTree;

typedefBinTreePosition;

structTreeNode{

   ElementTypeData;

   BinTreeLeft;

   BinTreeRight;

}