当关键字相同,但出现的顺序不同时,按照二叉排序树的创建方法,将创建出形态不同的二叉排序树。当关键字相同,但出现的顺序不同时,第一颗二叉树顺序是25,60,18,5,36,49,88.第二棵二叉树顺序是:5,18,25,36,49,60,88按照二叉排序树的创建方法,将创建出形态不同的二叉排序树。
时间: 2023-12-13 20:03:19 浏览: 41
是的,按照二叉排序树的创建方法,当关键字相同但出现的顺序不同时,将创建出形态不同的二叉排序树。以第一棵二叉树顺序为例,按照创建方法,可以得到如下的二叉排序树:
```
25
/ \
18 60
/ \ \
5 36 88
\
49
```
以第二棵二叉树顺序为例,按照创建方法,可以得到如下的二叉排序树:
```
5
\
18
\
25
/ \
36 60
/ \
49 88
```
可以看到,两棵二叉排序树的形态不同,尽管它们的关键字相同。这也说明了关键字出现的顺序对于二叉排序树的形态有很大的影响。
相关问题
用c语言实现二叉排序树创建
二叉排序树是一种特殊的二叉树,它的左子树上所有结点的关键字均小于根结点的关键字,右子树上所有结点的关键字均大于根结点的关键字。在C语言中,可以通过结构体和指针来实现二叉排序树的创建。具体实现方法如下:
1.定义二叉排序树结点的结构体:
```
typedef struct BSTNode{
int key;
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
```
2.在二叉排序树中查找值为key的结点:
```
BSTNode *BST_Search(BSTree T, int key){
while(T!=NULL && key!=T->key){
if(key<T->key)
T=T->lchild;
else
T=T->rchild;
}
return T;
}
```
3.在二叉排序树中插入关键字为k的新结点:
```
int BST_Insert(BSTree &T, int k){
if(T==NULL){
T=(BSTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
return 1;
}
else if(k==T->key)
return 0;
else if(k<T->key)
return BST_Insert(T->lchild, k);
else
return BST_Insert(T->rchild, k);
}
```
4.按照str[]中的关键字序列建立二叉排序树:
```
void Creat_BST(BSTree &T, int str[], int n){
T=NULL;
int i=0;
while(i<n){
BST_Insert(T,str[i]);
i++;
}
}
```
掌握顺序查找、折半查找;二叉排序树的创建、查找、插入、删除。
一、顺序查找
顺序查找,也称为线性查找,是一种简单的查找方法。其基本思想是从表的一端开始,逐个比较关键字,直到找到为止,或查找到最后一个记录为止。
顺序查找的时间复杂度为O(n)。
二、折半查找
折半查找,也称为二分查找,是一种高效的查找方法。其基本思想是在有序表中,将待查找的关键字与中间位置的关键字进行比较,如果相等,则查找成功;否则根据比较结果确定继续查找左半部分还是右半部分,直至查找成功或查找失败为止。
折半查找的时间复杂度为O(log2n)。
三、二叉排序树
二叉排序树,也称为二叉查找树,是一种特殊的二叉树。其特点是左子树上的所有节点的关键字小于根节点的关键字,右子树上的所有节点的关键字大于根节点的关键字。因此,对于每个节点,它的左子树和右子树也都是二叉排序树。
二叉排序树的基本操作包括创建、查找、插入和删除。
(1)创建二叉排序树
创建二叉排序树的方法是依次插入节点。对于每个节点,如果根节点为空,则将该节点作为根节点;否则,将该节点插入到左子树或右子树中。
(2)查找节点
查找节点的方法与折半查找相似,即从根节点开始,比较待查找节点的关键字与当前节点的关键字的大小关系,如果相等则查找成功;否则,根据比较结果确定继续查找左子树还是右子树,直至查找成功或查找失败为止。
(3)插入节点
插入节点的方法与创建二叉排序树相似,即从根节点开始,比较待插入节点的关键字与当前节点的关键字的大小关系,如果待插入节点的关键字小于当前节点的关键字,则将该节点插入到左子树中;否则,将该节点插入到右子树中。
(4)删除节点
删除节点分为三种情况:
① 待删除节点没有子节点
直接删除该节点即可。
② 待删除节点只有一个子节点
将该节点的子节点与该节点的父节点相连,然后删除该节点。
③ 待删除节点有两个子节点
将该节点的前驱节点(或后继节点)的值赋给该节点,然后删除该前驱节点(或后继节点)。
二叉排序树的时间复杂度与树的深度相关,最坏情况下的时间复杂度为O(n),但在平均情况下时间复杂度为O(log2n),因此它是一种高效的查找方法。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)