数据结构第四周笔记——树(中)(慕课浙大版本--XiaoYu)-阿里云开发者社区

4.1 二叉搜索树

4.1.1 二叉搜索树及查找

查找问题：

1.静态查找与动态查找

2.针对动态查找，数据如何组织

什么是二叉查找树：直接把元素放在树上，不要放在数组里面。

好处：树的动态性比较强，要插入删除比在线性里面做要方便

二叉搜索树(BST)

BST=>Binary Search Tree

也称为二叉排序树或者二叉查找树

二叉搜索树：一颗二叉树，可以为空;如果不为空，满足以下性质：

1.非空左子树的所有键值小于其根结点的键值。

2.非空右子树的所有键值大于其根结点单独键值

3.左、右子树都是二叉搜索树

网络异常，图片无法展示

二叉搜索树操作的特别函数：

网络异常，图片无法展示

插入(新结点x)删除(x这个结点)

网络异常，图片无法展示

二叉搜索树的查找操作：Find

查找从根结点开始，如果树为空，返回NULL

若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：

1.若X小于根结点赋值，只需在左子树中继续搜索;

2.如果X大于根结点的键值，在右子树中进行继续搜索;

3.若两者比较结果是相等，搜索完成，返回指向此结点的指针

代码实现

PositionFind(ElementTypeX,BinTreeBST)

{

if(!BST) returnNULL;//查找失败

if( X>BST->Data)//这是尾递归，下面的两个Find的也是同理

returnFind(X,BST->Right);//在右子树中继续查找

Elseif(X<BST->Data)

returnFind(X,BST->Left);//在左子树中继续查找

else//X == BST->Data

returnBST;//查找成功，返回结点的找到结点的地址

}

//由于非递归函数的执行效率高，可将"尾递归"函数改为迭代函数

PositionIterFind(ElementTypeX,BinTreeBST)

{

while(BST){

if(X>BST->Data)

BST=BST->Right;//向右子树中移动，继续查找

elseif(X<BST->Data)

BST=BST->Left;//向左子树中移动，继续查找

else//X == BST ->Data

returnBST;//查找成功，返回结点的找到结点的地址

}

returnNULL;//查找失败

}

//查找的效率决定于树的高度

查找最大和最小元素

1.最大元素一定是在树的最右分枝的端结点上

2.最小元素一定是在树的最左分枝的端结点上

对于搜索树的最大元素结点,下面哪个说法是正确的?

一定是叶结点

一定没有左儿子

一定没有右儿子

是后序遍历的最后一个结点

答案是：C

查找最小元素的递归函数

PositionFindMin( BinTreeBST)

{

if(!BST) returnNLULL;//空的二叉树，返回NULL

elseif(!BST->Left)

returnBST;//找到最左结点并返回

else

returnFindMin(BST->Left);//沿左分支继续查找

}

查找最大元素的迭代函数

PositionFindMax( BinTreeBST)

{

if( BST )

while( BST->Right ) BST=BST->Right;//沿右分支继续查找，直到最右叶结点

returnBST;

}

4.1.2 二叉搜索树的插入

【分析】关键是要找到元素应该插入的位置，可以采用与Find类似的方法

网络异常，图片无法展示

二叉搜索树的插入算法

BinTreeInsert(ElementTypeX,BinTreeBST)

{

if(!BST){

//若原树为空，生成并返回一个结点的二叉搜索树

BST=malloc(sizeof(structTreeNode));

BST->Data=X;

BST->Left=BST->Right=NULL;

}else//开始找要插入元素的位置

if(X<BST->Data )

BST->Left=Insert(X,BST->Left);//递归插入左子树

elseif(X>BST->Data)

BST->Right=Insert(X,BST->Right);//递归插入右子树

//else X已经存在，什么都不做

returnBST;

}

网络异常，图片无法展示

4.1.3 二叉搜索树的删除

考虑三种情况：

要删除的是叶结点：直接删除，并再修改其父节点指针---置为NULL
要删除的结点只有一个孩子结点：

将其父节点的指针指向要删除结点的孩子结点
网络异常，图片无法展示
|
网络异常，图片无法展示
|

要删除的结点有左、右两颗子树：

用另一结点代替被删除结点：右子树的最小元素或者左子树的最大元素
网络异常，图片无法展示
|

取右子树中的最小元素替代
网络异常，图片无法展示
|
网络异常，图片无法展示
|
代码实现

BinTreeDelete (ElementTypeX,BinTreeBST)

{

PositionTmp;

if(!BST) printf("要删除的元素未找到");

elseif(X<BST->Data)

BST->Left=Delete(X,BST->Left);//左子树递归删除,返回左子树删除了x这个结点之后，新的左子树根结点的地址

elseif(X>BST->Data)

BST->Right=Delete( X,BST->Right);//右子树递归删除

else//找到要删除的结点

if(BST->Left&&BST->Right ){//被删除结点有左右两个子节点

Tmp=FindMin(BST->Right);//在右子树中找最小的元素填充删除结点

BST->Data=Tmp->Data;

BST->Right=Delete(BST->Data,BST->Right);//在删除结点的右子树中删除最小元素

}else{//被删除结点有一个或无子结点

Tmp=BST;

if(!BST->Left)//有右孩子或无子结点

BST=BST->Right;

elseif(!BST->Left)//有左孩子或无子结点

BST=BST->Left;

free(Tmp);

}

returnBST;

4.2 平衡二叉树

4.2.1 什么是平衡二叉树

网络异常，图片无法展示

怎么样子算基本上平衡：1.左右结点差不多2.左右高度差不多

平衡因子：

网络异常，图片无法展示

平衡因子是对结点来说的，左右的一个高度差我们就称为平衡因子

平衡二叉树(Balanced Binary Tree)(AVL树) AVL是提出这个的科学家名字的第一个字母

空树，或者任一结点左、右子树高度差的绝对值不超过1，即|BF(T)|<=1

网络异常，图片无法展示

画画看，至少需要多少个结点才能构造出一棵4层（h=3)的平衡二叉树？7个

网络异常，图片无法展示

4.2.2 平衡二叉树的调整

RR旋转

网络异常，图片无法展示

LL旋转

网络异常，图片无法展示

LR旋转

网络异常，图片无法展示

RL旋转

网络异常，图片无法展示

小测试

网络异常，图片无法展示

小白专场：是否同一棵二叉搜索树 - C实现

题意理解及搜索树表示

是否是同一棵二叉搜索树

求解思路

两个序列是否对应相同搜索树的判别

分别建两棵搜索树的判别方法：根据两个序列分别建树，再判别树是否一样
不建树的判别方式

网络异常，图片无法展示
|
先看根结点也就是第一个数一样吗？再把比根结点小的放左边(顺序不动)，比根结点大的放右边(顺序不动)，然后再进行对比左右树，上图就是一样的，下图为反面例子
网络异常，图片无法展示
|

建一颗树，再判别其他序列是否与该树一致

求解思路
搜索树表示
建搜索树T
判别一序列是否与搜索树T一致

搜索树表示

typedefstructTreeNode*Tree;

structTreeNode{

intv;//v来表示基本信息

TreeLeft,Right;

intflag;//flag是一个阈(用来判别一个序列是不是跟树一致，实际效果就是如果这个结点没有被访问过flag设为0，被访问过了就设为1)

};

程序框架及建树

程序框架搭建

intmain()

{

对每组数据

1.读入N和L

2.根据第一行序列建树T

3.依据树T分别判别后面的L个序列是否能与T形成同一搜索树并输出结果//分别读入L个序列来跟T做比较，看是不是一致的，如果说一致的，他所对应的搜索树是一样的，一样输出yes，不一样输出no

return0;

}

根据上方框架，我们需要设计的主要函数：

1.读数据建搜索树T//读入N个数据来建我们的搜索树，将来所有序列都会跟这个T去比较，所以以T基准

2.判别一序列是否与T构成一样的搜索树

intmain()

{

intN,L,i;

TreeT;

scanf("%d",&N);

while(N){//N如果为0输出就结束了

scanf("%d",&L);

T=MakeTree(N);//读入后面N个数来建我们的树T

for(i=0; i<L;i++ ){//比较是不是跟T一致的这样的序列

if(Judge(T,N))printf("Yes\n");//用函数Judge读入后面的N个数然后跟T去做比较，所以这样Judge有两个参数，一个是树T，一个是序列的个数。通过Judge来判别，如果一致就print yes 反之print no

elseprintf("No\n");

ResetT(T);//清除T中的标记flag

}

FreeTree(T);//释放掉树占有的空间，因为已经处理完了准备处理下一组数据了，下一组数据需要的空间可能不需要这么多也可能远远不够

scanf("%d",&N);

}

return0;

}

如何建搜索树

TreeMakeTree(intN)

{

TreeT;

inti,V;

scanf("%d",&V);//读入第一个数，然后把数放到V里面去

T=NewNode(V);//为V构造一个对应的节点，然后赋给T，T只含一个节点

for(i=1;i<N;i++){//这里是循环N-1次噢

scanf("%d",&V);

T=Insert(T,V);//将V一个个插到T里面去

}

returnT;

}

TreeNewNode(intV)

{

TreeT= (Tree)malloc(sizeof(structTreeNode));

T->v=V;

T->Left=T->Right=NULL;

T->flag=0;

returnT;

}

怎么把树插到T里面去呢？引用insert这个函数

TreeInsert(TreeT, intV)

{

if(!T)T=NewNode(V);//如果T空了，那就调用NewNode来产生这样一个节点

else{

if(V>T->v)//如果不空就做比较

T->Right=Insert(T->Right,V);

else

T->Left=Insert(T->Left,V);

}

returnT;

}

搜索树是否一样的判别

网络异常，图片无法展示

方法:在树T中按顺序搜索序列

1.如果每次搜索所经过的结点在前面均出现过，则一致

2.否则(某次搜索中遇到前面未出现的结点)，则不一致

去在T中搜索我们序列中的每一个整数，实际上就是个查找过程

intcheck(TreeT,intV)

{

if(T->flag){

if(V<T->v)returncheck(T->Left,V);

elseif(V->T->v)returncheck(T->Right,V);

elsereturn0;

}

else{

if(V==T->v ){

T->flag=1;

return1;

}

elsereturn0;

}

如何辨别

//有bug版本

intJudge(TreeT,intN)

{

inti,V;

scanf("%d",&V);

if(V!=T->v)return0;

elseT->flag=1;

for(i=1;i<N;i++){

scanf("%d",&V);

if(!check(T,V))return0;

}

return1;

}

//当发现序列中的某个数与T不一致的时候，必须把序列后面的数都读完。这样才能保证我们下一个要求的序列是我们真正想要的序列，这个有bug的程序就是不能把后面的数都读完

以下是修改版本，对整个程序的一个标记而不是对结点的标记

intJudge(TreeT,intN)

{

inti,V,flag=0;//flag：0代表目前还一致，1代表已经不一致

scanf("%d",&V);

if(V!=T->v)flag=1;

elseT->flag=1;//T->flag是结点上的标记，flag是整个的标记，是不一样的

for(i=1;i<N;i++){

scanf("%d",&V);

if((!flag)&&(!check(T,V)))flag=1;

}

if(flag)return0;

elsereturn1;

}

voidResertT(TreeT)//清除T中各结点的flag标记

{

if(T->Left) ResetT(T->Left);

if(T->Right) ResetT(T->Right);

T->flag=0;

}

voidFreeTree(TreeT)//释放T的空间

{

if(T->Left) FreeTree(T->Left);

if(T->Right)FreeTree(T->Right);

free(T);//递归方法

}

线性结构之习题讲选[陈越]：Reversing Linked List

线性结构习题1：什么是抽象的链表

链表是一个抽象的数据结构

有块地方存数据
有块地方存指针——下一个结点的地址(一个抽象的指针指向的就是地址，任何一种形式去存了下一个结点的位置这东西就叫做指针)
网络异常，图片无法展示
|
网络异常，图片无法展示
|

线性结构习题2：链表逆转算法

单链表的逆转

网络异常，图片无法展示

第一个加上头结点虽然会浪费一个空间，但是会使后面的操作变为更加简单

逆序之后如下：

网络异常，图片无法展示

接下来是逆序的过程：

首先需要对图中定义的词汇进行解释

new：指的是新的已经逆转好的链表，他的头结点的位置
old：指的是旧的还没有逆转好的老链表，他的头结点位置

我们首先想要把2跟1进行逆转，但是在逆转之前需要先把3这个位置记住，所以设定一个tmp指针去指向3。否则当2的指针一转向，2后面的链表就丢失了

网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|

以下是伪代码实现

PtrReverse(Ptrhead,)//head是一个指针

{

cnt=1

new=head->next;//刚开始指向1的

old=new->next;//还没有逆转的那个头结点

while(cnt<K){

tmp=old->next;//记住下一个的位置

old->next=new;//指针逆转指向新的结点

new=old;old=tmp;//往前位移一段

cnt++;

}

head->next->next=old;//把开头那个空结点指向结尾的(因为逆转了，最开头的现在变为最末尾的了)

returnnew;

}

//取巧：用顺序表存储，先排序，再直接逆序输出

线性结构习题3：测试数据

有尾巴不反转
地址取到上下界
正好全反转
K = N是全反转
K = 1不用反转
最大(最后剩K-1不反转)、最小N
有多余结点

2-6是属于边界测试

边界测试

意思就是给你一个数值，你就一定要取到那个范围上界和下界

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

4.1 二叉搜索树

4.1.1 二叉搜索树及查找

二叉搜索树(BST)

二叉搜索树操作的特别函数：

插入(新结点x)删除(x这个结点)

二叉搜索树的查找操作：Find

查找最大和最小元素

查找最小元素的递归函数

查找最大元素的迭代函数

4.1.2 二叉搜索树的插入

二叉搜索树的插入算法

4.1.3 二叉搜索树的删除

4.2 平衡二叉树

4.2.1 什么是平衡二叉树

平衡因子：

4.2.2 平衡二叉树的调整

RR旋转

LL旋转

LR旋转

RL旋转

小测试

小白专场：是否同一棵二叉搜索树 - C实现

题意理解及搜索树表示

是否是同一棵二叉搜索树

程序框架及建树

程序框架搭建

如何建搜索树

搜索树是否一样的判别

如何辨别

线性结构之习题讲选[陈越]：Reversing Linked List

线性结构习题1：什么是抽象的链表

线性结构习题2：链表逆转算法

单链表的逆转

线性结构习题3：测试数据

2-6是属于边界测试

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

4.1 二叉搜索树

4.1.1 二叉搜索树及查找

二叉搜索树(BST)

二叉搜索树操作的特别函数：

插入(新结点x)删除(x这个结点)

二叉搜索树的查找操作：Find

查找最大和最小元素

查找最小元素的递归函数

查找最大元素的迭代函数

4.1.2 二叉搜索树的插入

二叉搜索树的插入算法

4.1.3 二叉搜索树的删除

4.2 平衡二叉树

4.2.1 什么是平衡二叉树

平衡因子：

4.2.2 平衡二叉树的调整

RR旋转

LL旋转

LR旋转

RL旋转

小测试

小白专场：是否同一棵二叉搜索树 - C实现

题意理解及搜索树表示

是否是同一棵二叉搜索树

程序框架及建树

程序框架搭建

如何建搜索树

搜索树是否一样的判别

如何辨别

线性结构之习题讲选[陈越]：Reversing Linked List

线性结构习题1：什么是抽象的链表

线性结构习题2：链表逆转算法

单链表的逆转

线性结构习题3：测试数据

2-6是属于边界测试

热门文章

最新文章

相关课程

相关电子书