1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。
2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A．15 B．16 C．17 D．47
3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。
4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。
5. 深度为5的二叉树至多有____个结点。
6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ ___。
7. 对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。
8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。
A.不发生改变 B.发生改变 C.不能确定 D.以上都不对
10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。 A. 正确 B. 错误
11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。
12. 在一非空二叉树的中序遍历序列中，根结点的右边____。
A. 只有右子树上的所有结点 B. 只有右子树上的部分结点
C. 只有左子树上的部分结点 D. 只有左子树上的所有结点
13. 如图6.1所示二叉树的中序遍历序列是____。

14. 一棵二叉树如图6.2所示，其中序遍历的序列为__ __。
15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。
A．a在b的右方 B．a在b的左方
C．a是b的祖先 D．a是b的子孙
17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。
A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构
18. 如图6.3所示的4棵二叉树，____不是完全二叉树。

19. 如图6.4所示的4棵二叉树，____是平衡二叉树。

20. 在线索化二叉树中，t所指结点没有左子树的充要条件是____。
21. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。 A. 正确 B. 错误
22. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。 A. 正确 B. 错误
23. 具有五层结点的二叉平衡树至少有____个结点。
24. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
25. 树最适合用来表示____。
A. 有序数据元素 B. 无序数据元素
C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据
6.2 填空题（将正确的答案填在相应的空中）
1. 有一棵树如图6.5所示，回答下面的问题：
⑴ 这棵树的根结点是____；
⑵ 这棵树的叶子结点是____；
⑷ 这棵树的度是____；
⑸ 这棵树的深度是____；
⑹ 结点k3的子女是____；
⑺ 结点k3的父结点是____；

2. 指出树和二叉树的三个主要差别____、____、____。
3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是___ _。

4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为__ __。
5. 深度为k的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是____。
6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=____。
7. 一棵二叉树的第i（i≥1）层最多有____个结点；一棵有n（n>0）个结点的满二叉树共有____个叶子和____个非终端结点。
8. 结点最少的树为____，结点最少的二叉树为____。
9. 现有按中序遍历二叉树的结果为abc，问有____种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。
10. 由如图6.7所示的二叉树，回答以下问题：
⑴ 其中序遍历序列为____；
⑵ 其前序遍历序列为____；
⑶ 其后序遍历序列为____；

1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。
3. 由如图6.7所示的二叉树，回答以下问题：
（1）画出该二叉树的中序线索二叉树；
（2）画出该二叉树的后序线索二叉树；
（3）画出该二叉树对应的森林。
4. 已知一棵树如图6.8所示，转化为一棵二叉树，表示为____。

5. 以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。
6. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?
7. 证明:一棵满k叉树上的叶子结点数n 和非叶子结点数n 之间满足以下关系:
1. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。
2．试编写算法，对一棵二叉树,统计叶子的个数。
3．试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。
使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。
8. 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。
2. 树的结点个数至少为1(不同教材规定不同)，而二叉树的结点个数可以为0；
树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
树的结点无左、右之分，而二叉树的结点有左、右之分；
3. 树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解决树的有关问题。
8. 只有一个结点的树；空的二叉树
2. 二叉树如图6.12所示。

3. 中序线索二叉树如图6.13（左）所示；后序线索二叉树如图6.13（右）所示；
该二叉树转换后的的森林如图6.14所示。

4. 图6.8的树转化为一棵二叉树如下，图6.15：

5. 画出构造Huffman树如图6.16所示，计算其带权路径长度为 。

6. 一棵含有N个结点的k叉树,可能达到的最大深度 h=N-k+1 ，

11．已知一有向图的邻接表存储结构如图7.2所示。

⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
12．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。
A. 求关键路径的方法 B. 求最短路径的Dijkstra方法
C. 宽度优先遍历算法 D. 深度优先遍历算法
15．关键路径是事件结点网络中 。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
C.最长的回路 D.最短的回路
16．下面不正确的说法是 。
（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小；
（2）AOE网工程工期为关键活动上的权之和；
（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。
17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。
A.逆拓朴有序的 B.拓朴有序的 C.无序的
18．在图7.3所示的拓朴排列的结果序列为 。

19．一个有n个顶点的无向连通图，它所包含的连通分量个数为 。
20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。
21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。
7.2 填空题（将正确的答案填在相应饿空中）
1．n个顶点的连通图至少____条边。
2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。
4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。

图7.4 图G的邻接表
5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。
6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。
7．如果含n个顶点的图形成一个环，则它有 棵生成树。
8．一个非连通无向图，共有28条边，则该图至少有 个顶点。
9．遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ，DFS遍历图的时间复杂度为 ，两者不同之处在于 ，反映在数据结构上的差别是 。
10．一个图的 表示法是唯一的，而 表示法是不唯一的。
11．有向图中的结点前驱后继关系的特征是 。
12．若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。
13．根据图的存储结构进行某种次序的遍历，得到的顶点序列是 的。
1．已知如图7.5所示的有向图，请给出该图的:
（1）每个顶点的入/出度；

2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树：

3．试列出图7.8中全部的拓扑排序序列。

4．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。

5．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：
(2)计算完成整个计划需要的时间。
(3)求出该AOE网的关键路径。
∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝

(2)完成整个计划需要18天。

1.顺序查找法适合于存储结构为____的线性表。
A. 散列存储 B. 顺序存储或链接存储
C. 压缩存储 D. 索引存储
2.对线性表进行二分查找时，要求线性表必须____。
A. 以顺序方式存储 B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排序
D. 以链接方式存储，且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.
4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。
5.二分查找和二叉排序树的时间性能____。
6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。
如用二次探测再散列处理冲突，关键字为49的结点的地址是____。
8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。
9．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为 。
A.从第0个元素往后查找该数据元素
B.从第1个元素往后查找该数据元素
C.从第n个元素往开始前查找该数据元素
10．解决散列法中出现的冲突问题常采用的方法是 。
A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法
11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址 。
A.必须大于等于原散列地址
B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址
D.地址大小没有具体限制
12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。
A.静态查找表 B.动态查找表
C.静态查找表与动态查找表 D两种表都不适合
13.散列表的平均查找长度 。
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法有关而与表的长度有关
D.与处理冲突方法无关而与表的长度无关
8.2 填空题（将正确的答案填在相应的空中）
1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。
2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。
3.折半查找的存储结构仅限于____，且是____。
4. 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。
5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____；
6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 次查找可确定成功；查找47时，需进行 次查找成功；查找100时，需进行 次查找才能确定不成功。
7．二叉排序树的查找长度不仅与 有关，也与二叉排序树的 有关。
8．一个无序序列可以通过构造一棵 树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。
9．平衡二叉排序树上任一结点的平衡因子只可能是 、 或 。
10． 法构造的哈希函数肯定不会发生冲突。
12．在散列存储中，装填因子 的值越大，则____； 的值越小，则____。
1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
2.含九个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？
3.试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20,30,50,52,60,68,70.如果此后删除50和68，画出每一步执行后2-3树的状态。
4. 选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。
5. 已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树，注意边插入边平衡。

3. 顺序存储结构、有序的
（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12）
7．结点个数n、生成过程
12．存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小

1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____。
A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用____排序法。
3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。
A. 插入排序 B. 选择排序

数据结构查找练习题及答案

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为(C )。

2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )

3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（D）,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（C）。 在此假定N为线性表中结点数，且每次查找都是成功的。

4. 下面关于二分查找的叙述正确的是 ( D )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储

B. 表必须有序且表中数据必须是整型，实型或字符型

C. 表必须有序，而且只能从小到大排列

D. 表必须有序，且表只能以顺序方式存储 

5. 用二分（对半）查找表的元素的速度比用顺序法( D )

6. 具有12个关键字的有序表，二分查找的平均查找长度（ A ）

7. 二分法查找的时间复杂性为（ D ）。

8．当采用分快查找时，数据的组织方式为 ( B )

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ D ）个记录。

10. 下面关于哈希(Hash，杂凑)查找的说法正确的是( C )

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B．除留余数法是所有哈希函数中最好的 

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 

11. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (A) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (C)

1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ √ ）

2．在散列(哈希)检索中，“比较”操作一般也是不可避免的。（ √ ）

3．哈希函数越复杂越好，因为这样随机性好，冲突概率小. （ × ）

4．哈希函数的选取平方取中法最好。 （ × ）

5．Hash表的平均查找长度与处理冲突的方法无关。 （ × ）

6．负载因子 (装填因子)是哈希表的一个重要参数，它反映哈希表的装满程度。（ √ ）

7. 哈希法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（ √ ）

8. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 （ × ）

9．查找相同结点的效率二分查找总比顺序查找高。 （ × ）

10．用数组和单链表表示的有序表均可使用二分查找方法来提高查找速度。 （ × ）

11. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ √ ）

12. 顺序查找法适用于存储结构为顺序或链接存储的线性表。 （ √ ）

13. 二分查找法的查找速度一定比顺序查找法快 。（ × ）

14. 就平均查找长度而言，分块查找最小，二分查找次之，顺序查找最大。（ × ）

15．对无序表用二分法查找比顺序查找快。（× ）

1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为n次；当使用监视哨时，若查找失败，则比较关键字的次数为n+1。

3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为6,9,11,12。

4. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是5

5. 高度为4的3阶b-树中，最多有26（第4层是叶子结点，每个结点两个关键字）个关键字。

6. 在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是1,3,6,8,11,13,16,19

7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为5 ，带权路径长度WPL的值为96。

9．哈希表是通过将查找码按选定的哈希函数和解决冲突的方法，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是选择好的哈希函数和处理冲突的方法。一个好的哈希函数其转换地址应尽可能均匀，而且函数运算应尽可能简单。

答：概念是基本知识的主要部分，要牢固掌握。这里只列出一部分，目的是引起重视，解答略。 

（1）哈希表存储的基本思想是什么？

答：散列表存储的基本思想是用关键字的值决定数据元素的存储地址 

（2）哈希表存储中解决冲突的基本方法有哪些？其基本思想是什么？

答：散列表存储中解决碰撞的基本方法：

    ① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：

       a．di =1，2，…，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

       b．di =12，-12，22，-22，… ，k2（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。

   ② 再散列法 Hi=RHi（key） i=1，2，…，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

    ③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。

3. 如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。

答：评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面2题。 

4．HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？

答：哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.65~0.9。解决冲突方法见上面2题。 

5．在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？

答：不一定相邻。哈希地址为i（0≤i≤m-1）的关键字，和为解决冲突形成的探测序列i的同义词，都争夺哈希地址i。 

1．在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。

答：[题目分析]首先计算关键字的散列地址，若该地址为空，则空操作；若该地址有关键字，但与给定值不等，则用解决冲突的方法去查找给定值；若该地址有关键字且与给定值相等，则实行删除。题目要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不断裂。由于用线性探测解决冲突，设被删除元素的散列地址为i，则其余m-1（m为表长）个位置均可能是同义词。查找同义词的操作直到碰到空地址或循环一圈回到i才能结束。为了提高算法效率，减少数据移动，应将最后一个同义词前移填充被删除关键字。

     //在以除余法为散列函数、线性探测解决冲突的散列表HS中，删除关键字K

    //在散列表HS中，删除关键字K，K的散列地址是i，因解决冲突而将其物理地置于表中j。算法查找关键字K的同义词，将其最后一个同义词移到位置j，并将其同义词的位置置空。

    [算法讨论] 由于用线性探测解决冲突，可能发生“二次聚集”（两个第一哈希地址不同的记录争夺同一后继哈希地址）。象上面这样处理后，对于哈希地址为i的记录没有问题了，但由于将地址j置空，有可能截断了其它记录的探测通路。最明显的是哈希地址为j的记录就查不到了。解决的办法是继续调整，直到当前哈希表中的每个记录的查找都是正确的为止。这里不再深入讨论。 

2．设排序二叉树中结点的结构为下述三个域构成: 

    data: 给出结点数据的值；left: 给出本结点的左儿子结点的地址；right: 给出本结点的右儿子结点的地址

    设data 域为正整数，该二叉树树根结点地址为T。 现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除掉。

答：[题目分析]利用二叉排序树的性质，从根结点开始查找，若根结点的值小于等于x，则根结点及其左子树均应删除，然后以右子树的根结点为树根，重新开始查找。若根结点的值大于x，则顺左子树向下查找，直到某结点的值小于等于x，则该结点及其左子树均应删除。下面设计一查找算法，确定被删除子树的根结点，再设计一删除算法，删除以被删结点为根的子树。