给定关键字序列{55,25,6,95,76,12,124,32} (1)构造一棵二叉排序树。 (2)查找13的查找路径。(结点用逗号分隔,如:40,60,90,120)
时间: 2024-05-13 18:20:18 浏览: 69
数据结构与算法练习题Exercise6.doc
回答:好的,我会尽力回答你的问题。
针对问题1:
(1) 构造一棵二叉排序树:
首先选取第一个关键字55作为根节点,然后将剩下的关键字分别与根节点比较:
25小于55,所以将25插入根节点的左子树;
6小于55,所以将6插入根节点的左子树的左子树;
95大于55,所以将95插入根节点的右子树;
76大于55,所以将76插入根节点的右子树的左子树;
12小于55,所以将12插入根节点的左子树的右子树;
124大于55,所以将124插入根节点的右子树的右子树;
32小于55,所以将32插入根节点的左子树的左子树的右子树。
最终构造出的二叉排序树如下图所示:
```
55
/ \
25 95
/ \ / \
6 12 76 124
\
32
```
(2) 查找13的查找路径:
在二叉排序树中查找关键字13的查找路径如下:
当前节点为根节点55,13小于55,所以向左子树查找。
当前节点为25,13小于25,所以向左子树查找。
当前节点为6,13大于6,所以向右子树查找。
当前节点为12,13小于12,但是12无右子树,查找到了叶节点,停止查找。
因此,找不到关键字为13的查找路径。
阅读全文