用1234567建一棵AVL二叉树
时间: 2024-05-26 22:09:32 浏览: 18
首先,AVL树是一种自平衡的二叉搜索树,它保证了每个节点的左子树和右子树的高度差不超过1。
现在我们来介绍如何使用 1, 2, 3, 4, 5, 6, 7 建立一棵AVL树:
1. 首先,我们以1为根节点,将2插入到右子树中,树变成了:
```
1
\
2
```
2. 接着,我们将3插入到右子树中,树变成了:
```
1
\
2
\
3
```
3. 再将4插入到右子树中,树变成了:
```
1
\
2
\
3
\
4
```
4. 此时,我们发现节点4的插入导致右子树的高度比左子树高2,不满足AVL树的要求。因此,需要对节点2进行旋转。
5. 我们以节点2为支点进行右旋,树变成了:
```
1
\
3
/ \
2 4
```
6. 此时,我们发现根节点的右子树高度比左子树高1,符合AVL树的要求。现在将5插入到左子树中,树变成了:
```
1
\
3
/ \
2 4
/
5
```
7. 接着,将6插入到左子树中,树变成了:
```
3
/ \
2 5
/ / \
1 4 6
```
8. 最后,将7插入到左子树中,树变成了:
```
3
/ \
2 5
/ / \
1 4 6
\
7
```
至此,我们成功地用1234567建立了一棵AVL二叉树。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)