分别用1~9顺序输入的方法和随机方式构造二叉排序树
时间: 2024-03-08 16:45:01 浏览: 22
1. 顺序输入法构造二叉排序树:
首先将1作为根节点,然后依次将2、3、4、5、6、7、8、9插入二叉排序树中。
插入2时,由于2比1大,所以作为1的右子节点;
插入3时,由于3比1大,所以从1的右子节点开始比较,由于右子节点为空,所以3作为1的右子节点的左子节点;
插入4时,由于4比1大,所以从1的右子节点2开始比较,由于4比2大,所以从2的右子节点开始比较,由于右子节点为空,所以4作为2的右子节点;
插入5时,由于5比1大,所以从1的右子节点2开始比较,由于5比2大,所以从2的右子节点4开始比较,由于5比4大,所以从4的右子节点开始比较,由于右子节点为空,所以5作为4的右子节点的左子节点;
插入6时,由于6比1大,所以从1的右子节点2开始比较,由于6比2大,所以从2的右子节点4开始比较,由于6比4大,所以从4的右子节点开始比较,由于右子节点为空,所以6作为4的右子节点的右子节点;
插入7时,由于7比1大,所以从1的右子节点2开始比较,由于7比2大,所以从2的右子节点4开始比较,由于7比4大,所以从4的右子节点6开始比较,由于右子节点为空,所以7作为6的右子节点;
插入8时,由于8比1大,所以从1的右子节点2开始比较,由于8比2大,所以从2的右子节点4开始比较,由于8比4大,所以从4的右子节点6开始比较,由于8比6大,所以从6的右子节点开始比较,由于右子节点为空,所以8作为6的右子节点的右子节点;
插入9时,由于9比1大,所以从1的右子节点2开始比较,由于9比2大,所以从2的右子节点4开始比较,由于9比4大,所以从4的右子节点6开始比较,由于9比6大,所以从6的右子节点8开始比较,由于右子节点为空,所以9作为8的右子节点。
最终构造出的二叉排序树如下所示:
1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9
2. 随机方式构造二叉排序树:
随机构造二叉排序树的过程中,首先将1作为根节点,然后随机生成2~9的排列顺序,依次将这些数字插入二叉排序树中。
插入顺序假设为:5、3、6、4、2、7、9、1、8
插入5时,由于5比1大,所以作为1的右子节点;
插入3时,由于3比5小,所以作为5的左子节点;
插入6时,由于6比5大,所以作为5的右子节点;
插入4时,由于4比5小,所以从5的左子节点3开始比较,由于4比3大,所以作为3的右子节点;
插入2时,由于2比5小,所以从5的左子节点3开始比较,由于2比3小,所以从3的左子节点开始比较,由于左子节点为空,所以2作为3的左子节点;
插入7时,由于7比5大,所以从5的右子节点6开始比较,由于7比6大,所以作为6的右子节点;
插入9时,由于9比5大,所以从5的右子节点6开始比较,由于9比6大,所以从6的右子节点开始比较,由于右子节点为空,所以9作为6的右子节点的右子节点;
插入1时,由于1比5小,所以从5的左子节点3开始比较,由于1比3小,所以从3的左子节点2开始比较,由于1比2小,所以作为2的左子节点;
插入8时,由于8比5大,所以从5的右子节点6开始比较,由于8比6大,所以从6的右子节点9开始比较,由于8比9小,所以作为9的左子节点。
最终构造出的二叉排序树如下所示:
1
\
5
/ \
3 6
/ \ \
2 4 9
/
8
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)